《编译原理》课后习题答案第四章
2 3
而对正规式(2)可画 NFA 图，如图所示。
a b X12 12 12Y 12 12 12Y 12Y 12 12Y 可化简得下表
a b 1 2 3 2 2 3 得 DFA 图
两图完全一样，故两个自动机完全一样，所以两个正规文法等价。 对相应正规文法,令 A 对应 1，B 对应 2 故为： A→aA|bB|b
B→aA|bB|b 即为 S→aS|bS|B,此即为所求正规文法。
问题 6：考虑正规表达式 r = a*b(a | b) ，构造可以生成语言 L(r) 的一个正规文法。 答案：
盛威网（www.snwei.com）专业的计算机学习网站
22
《编译原理》课后习题答案第四章
S → a*b(a | b) 变换为 S → aA, S → b(a | b) , A → aA , A → b(a | b) 变换为 S → aA, S → bB, B → (a | b) , A → aA , A → bC, C → (a | b) 变换为 S → aA, S → bB, B → a, B → b , A → aA , A → bC, C → a, C → b
所以，一个可能的正规文法为 G[S]：
S → aA, S → bB, B → a, B → b , A → aA , A → bC, C → a, C → b 或表示为：
S → aA | bB, B → a | b , A → aA | bC, C → a | b
（适当等价变换也可以，但要作说明，即要有步骤）
问题 7：
考虑下图所示的 NFA N，构造可以生成语言 L(N) 的一个正规文法。 答案： G[P]:
P → 0 P ?1 P ?1 Q Q → 0 R ?1 R R → ε
问题 8：考虑如下文法 G[S]：
S → 0S?1S?1A A→ 0B?1B B → ε
a)试构造语言为 L(G) 的一个正规表达式。
盛威网（www.snwei.com）专业的计算机学习网站
23
《编译原理》课后习题答案第四章
b) 试构造语言为 L(G) 的一个有限自动机。 答案： a)
由 A→ 0B ， B → ε 得 A→ 0 ; 由 A→ 1B ， B → ε 得 A→ 1 ; 由 A→ 0，A→ 1 得 A→ 0 ?1 ; 由 S→ 1A，A→ 0 ?1 得 S→ 1( 0 ?1 ) ; 由 S→ 1A，A→ 0 ?1 得 S→ 1( 0 ?1 ) ; 由 S→ 0S，S→ 1( 0 ?1 ) 得 S→ 0*1( 0 ?1 ) ; 由 S→ 1S，S→ 1( 0 ?1 ) 得 S→ 1*1( 0 ?1 ) ; 由 S→ 0*1( 0 ?1 )，S→ 1*1( 0 ?1 ) 得 S→ 0*1( 0 ?1 ) ? 1*1( 0 ?1 ) ; 所以，一个可能的正规表达式为：
0*1( 0 ?1 ) ? 1*1( 0 ?1 )
b)
盛威网（www.snwei.com）专业的计算机学习网站
24
《编译原理》课后习题答案第五章
第 5 章 自顶向下语法分析方法
第 1 题
对文法 G[S] S→a|∧|(T)
T→T,S|S
(1) 给出(a,(a,a))和(((a,a),∧,(a)),a)的 左推导。
(2) 对文法 G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。(3) 经改写后的文法是否是 LL(1)的?给出它的预测分析表。 (4) 给出输入串(a,a)#的分析过程，并说明该串是否为 G 的句子。 答案：
(1) 对(a,(a,a)的 左推导为： S(T) (T,S) (S,S) (a,S) (a,(T)) (a,(T,S)) (a,(S,S)) (a,(a,S)) (a,(a,a))
对(((a,a),∧,(a)),a) 的 左推导为： S(T)
(T,S) (S,S) ((T),S) ((T,S),S) ((T,S,S),S) ((S,S,S),S) (((T),S,S),S) (((T,S),S,S),S) (((S,S),S,S),S) (((a,S),S,S),S) (((a,a),S,S),S) (((a,a),∧,S),S) (((a,a),∧,(T)),S) (((a,a),∧,(S)),S) (((a,a),∧,(a)),S)
盛威网（www.snwei.com）专业的计算机学习网站
1
《编译原理》课后习题答案第五章
(((a,a),∧,(a)),a)
(2) 改写文法为：
0) S→a 1) S→∧ 2) S→( T ) 3) T→S N 4) N→, S N 5) N→ε 非终结符 S T N 对左部为 N 的产生式可知： FIRST （→, S N）={，}
FIRST （→ε）={ε} FOLLOW （N）={)}
由于 SELECT(N →, S N)∩SELECT(N →ε) ={，}∩ { )}= 所以文法是 LL(1)的。 预测分析表（Predicting Analysis Table） S T N
(3) 对输入串（a,a）#的分析过程为： 栈（STACK） 当前输入符 剩余输入符 （INOUT_STRING） 盛威网（www.snwei.com）专业的计算机学习网站
FIRST 集 {a,∧,(} {a,∧,(} {,,ε}. FOLLOW 集 {#,,,)} {)}.... {)}.... a →a →S N ∧ →∧ →S N ( →(T) →S N ) →ε , →, S N # 也可由预测分析表中无多重入口判定文法是 LL(1)的。 所用产生式 （OPERATION） 2
编译原理课后习题答案+清华大学出版社第二版
