《编译原理与技术》练习题 5
(5) S→ aSS S→a
(6) A → 0B | 1C
B → 1 | 1A | 0BB C → 0 | 0A | 1CC
3.7 设已给文法G3.31=(VN,VT,P,S)，其中：
VN = {S}
VT = {a1,a2,…,an,∨,∧, ~, [,]}
P = {S→ai| i=1,2,…,n}∪{S→ ~S, S→[ S∨S］, S → [ S∧S］}， 试指出此文法所产生的语言。
3.8 已知文法G3.32=({A,B,C},{a,b,c},A,P)，其中P由以下产生式组成：
A ?abc A ?aBbc Bb ?bB Bc ?Cbcc bC ?Cb aC ?aaB aC ?aa
问：此文法表式的语言是什么？ 3.9 已知文法 G3.33 [P]:
P → aPQR |abR RQ → QR bQ → bb
bR → bc cR → cc
证明 aaabbbccc 是该文法的一个句子。
3.10 构造一个文法，使其产生的语言是由算符+, *, (, ) 和运算对象a构成的算术表达式的集合。 3.12 已知语言L={anbbn| n≥1}, 写出产生语言L的文法。 3.13 写一文法，使其语言是偶正整数的集合。 要求：
(1) 允许0打头。 (2) 不允许0打头。 3.14 文法G3.34 [S]为：
S→ Ac|aB, A→ ab B→ bc
该文法是否为二义的？为什么？（提示：找一个句子，使之有两棵不同的分析树。） 3.15 证明下述文法G3.35［〈表达式〉］是二义的：
〈表达式〉→ a | (〈表达式〉) |〈表达式〉〈运算符〉〈表达式〉 〈运算符〉→ + | - | * | /
3.16 下面的文法产生a的个数和b的个数相等的非空a、b串
S→ aB | bA B→ bS | aBB | b
A→ aS | bAA | a
其中非终结符B推出b比a的个数多1个的串，A则反之。
(1) 证明该文法是二义的。
(2) 修改上述文法，不增加非终结符，使之成为非二义文法，并产生同样的语言。
《编译原理与技术》练习题 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$ 的分析过程。