内容发布更新时间 : 2025/6/18 16:00:10星期一 下面是文章的全部内容请认真阅读。
《编译原理与技术》练习题 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 |