编译原理与技术练习题汇总 下载本文

《编译原理与技术》练习题 6

3.17 考虑文法G3.36[R]

R→R '|' R | RR | R* | (R) | a | b

其中R '|' R表示R或R;RR表示R与R的连接;R*表示R的闭包。

(1) 证明此文法生成?={a, b}上的除了?和ε的所有正规表达式。 (2) 试说明此文法是二义性的。

(3) 构造一个等价的无二义性文法,该文法给出*、连接和|等运算符号的优先级和结合规则。 3.18 给出产生下述语言的上下文无关文法:

(1) { an bn am bm | n, m≥0}。 (2) { 1n 0m1m 0n | n, m≥0}。

(3) { ?c? | ?∈{a, b}*},其中?是?的逆。

+

(4) { w | w∈{a,b},且w中a的个数恰好比b多1 }。 (4) { w | w∈{a,b},且|a|≤|b|≤2|a| }。 (5) { w | w是不以0开始的奇数集 }。

3.19 设G=(VN,VT,P,S)为CFG,α1,α2,…,αn为V上的符号串,试证明:

若 α1α2…αn

β 则存在V上的符号串β1,β2,…,βn,使β=β1β2…βn,且有 ai

β,试证明:

βi (i=1,2,…,n)。

+

T

T

3.20 设G=(VN,VT,P,S)为CFG,α和β都是V上的符号串,且α

(1) 当α的首符号为终结符号时,β的首符号也必为终结符号; (2) 当β的首符号为非终结符号时,则α的首符号也必为非终结符号。 3.21 写出下列语言的3型文法:

(a) {an | n≥0}

(b) {anbm | n, m≥1} (c) {anbmck | n, m, k≥1} 3.22 已知文法G3.37 [S]:

S→ dAB A→ aA|a

B→ ε |Bb

给出相应的正规式和等价的正规文法。

3.23 给出下列文法G[A]消除左递归后的等价文法:

(1) A→ BaC | CbB B→ Ac | c C→ Bb | b (2) A → B a | A a | c B → B b | A b | d (3) S→ SA | A A→ SB | B | (S) | ( ) B→ [S] | [ ] (4) S→ AS | b

A→ SA | a (5) S→ (T) | a | ε

T→ S | T, S

《编译原理与技术》练习题 7

练习 4

4.1 证明:含有左递归的文法不是LL(1)文法。 4.2 对于文法G4.11[S]

S → uBDz B → Bv | w D → EF E → y | ? F → x | ?

(1) 计算文法G4.11各非终结符的FIRST集和FOLLOW集,以及各产生式的SELLECT集。 (2) 判断该文法是否是LL(1)文法。

(3) 若不是LL(1)文法,则修改此文法 , 使其成为能产生相同语言的 LL(1) 文法。 4.3 已知布尔表达式文法G4.12[bexpr]

bexpr→ bexpr or bterm | bterm bterm→ bterm and bfactor | bfactor bfactor→ not bfactor | (bexpr) | true | false

改写文法G4.12为扩充的巴克斯范式,并为每个非终结符构造递归下降分析子程序。 4.4已知用EBNF表示的文法G4.13[A]

A→ [ B B→ X ] {A} X→ (a | b) {a | b}

试用类 C 或类 PASCAL 语言写出其递归下降子程序。 4.5 已知文法G4.14[S]

S→ (L) | a L→ L, S | S

(1) 消除文法G4.14的左递归,并为每个非终结符构造不带回溯的递归子程序。 (2) 经改写后的文法是否是LL(1)文法?给出它的预测分析表。

(3) 给出输入串 (a, a)$ 的分析过程,并说明该符号串是否为文法G4.14的句子。 4.6 对于文法G4.15[R]

《编译原理与技术》练习题 8

R → R ' | ' T | T T → TF | F F → F* | C C → (R) | a | b (1) 消除文法的左递归。

(2) 计算文法G4.15各非终结符的FIRST集和FOLLOW集。 (3) 构造LL(1)分析表。 4.7 已知文法G4.16[A]

A→ aABe | a B→ Bb | d

(1) 判断该文法是否为LL(1) 文法。 (2) 写出输入串aade$ 的分析过程。

《编译原理与技术》练习题 9

练习 5

5.1 设文法G5.10[E]为 E → E+T | E-T | T T → T*F | T/F | F F → F↑P | P P → (E) | i

求以下句型的短语、直接短语、素短语、句柄和最左素短语: (1)E-T/F+i (2)E+F/T-P↑i (3)T*(T-i)+P (4)(i+i)/i-i

5.2 根据下列优先关系矩阵计算其优先函数,并说明优先函数是否存在。

5.3 对于文法G5.11[S] S → (R) | a | b R → T T → S; T | S

(1)计算G5.11 [S]的FIRSTTV和LASTTV;

(2)构造G5.11 [S]的优先关系表,并说明G5.11 [S]是否为算符优先文法; (3)计算G5.11 [S]的优先函数。

5.4 对于文法G5.12 [S] S → S;G | G G → G(T) | H H → a | (S) T → T+S | S

《编译原理与技术》练习题 10

(1)构造G5.12 [S]的算符优先关系表,并判断G5.12 [S]是否为算符优先文法; (2)给出句型a(T+S);H;S的短语、直接短语、句柄、素短语和最左素短语; (3)分别给出(a+a)和a;(a+a)的分析过程,并说明它们是否为G5.12 [S]的句子; (4)给出(3)中输入串的最右推导,分别说明它们是否为G5.12 [S]的句子; (5)从(3)和(4)说明算符优先分析的优缺点。

5.5 对于文法G5.13[P] P → LAd | cd L → c A→ aP | P | a

请证明它不存在优先函数。 5.6 给定文法G5.14 [S] S →AS | b A → SA | a

(1)构造它的LR(0)的项集;

(2)构造识别该文法所有活前缀的DFA;

(3)这个文法是SLR(1)吗?若是,构造出它的SLR(1)分析表。

5.7 给定文法G5.15[S] S →AS | ? A → aA | b

(1)构造它的LR(1)文法;

(2)构造识别该文法所有活前缀的DFA; (3)构造出它的SR(1)分析表; (4)给出字符串abab$的分析过程。 5.8 若有定义二进制数的文法G5.16[D] D → L . L | L L → LB | B B → 0 | 1

(1) 通过构造该文法的无冲突的分析表来说明它是哪类LR文法; (2) 给出输入串101.010的分析过程。 5.9 给定文法G5.17[S]