《编译原理与技术》练习题 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]