清华大学第二版编译原理答案
D→bB|aA E→aB|bF F→bD|aE|b
构造相应的最小的DFA。 答案：
先构造其NFA： S a A a Z Q b B D a E b F b b a b a a b b b b a b
用子集法将NFA 确定化： a b S A Q A A BZ Q Q DZ BZ Q D DZ A B D A B B Q D
将S、A、Q、BZ、DZ、D、B 重新命名，分别用0、1、2、3、4、5、6 表示。因为3、 4 中含有z，所以它们为终态。 a b 0 1 2 1 1 3
清华大学第二版编译原理答案
2 2 4 3 2 5 4 1 6 5 1 6 6 2 5
DFA 的状态图： 0 a a 5 2 b 3 a a b 4 1 6 b a a b b b a b
令P0＝（｛0,1,2,5,6｝,｛3,4｝）用b进行分割： P1＝（｛0,5, 6｝,｛1,2｝,｛3,4｝）再用b进行分割： P2＝（｛0｝,｛5, 6｝,｛1,2｝,｛3,4｝）再用a、b 进行分割，仍不变。 再令｛０｝为A，｛1，2｝为B，｛3，4｝为C，｛5，6｝为D。 最小化为： A a , b D C a a B b a b b
第８题
给出下述文法所对应的正规式：
清华大学第二版编译原理答案
S→0A|1B A→1S|1 B→0S|0 答案：
解方程组S 的解： S=0A|1B A=1S|1 B=0S|0
将A、B 产生式的右部代入S 中
S=01S|01|10S|10=（01|10）S|（01|10） 所以：S= (01|10)*(01|10) 第9 题
将下图的DFA 最小化，并用正规式描述它所识别的语言。 1 a 2 6 c 3 c b 5 4 7 b b a b b b d d a
答案： 令P0＝（｛1,2,3,4,5｝,｛6,7｝）用b进行分割： P1＝（｛1,2｝,｛3,4｝,｛5｝,｛6,7｝）再用a、b、c、d进行分割，仍不变。 再令｛1,2｝为A，｛3，4｝为B，｛5｝为C，｛6，7｝为D。 最小化为： A a C D b d B b c
清华大学第二版编译原理答案
a b
r=b*a(c|da)*bb*=b*a(c|da)*b+
《编译原理》课后习题答案第五章 第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) (((a,a),∧,(a)),a) (2) 改写文法为： 0) S→a 1) S→∧
清华大学第二版编译原理答案
2) S→( T ) 3) T→S N 4) N→, S N 5) N→ε
非终结符 FIRST 集 FOLLOW 集 S {a,∧,(} {#,,,)} T {a,∧,(} {)}.... N {,,ε}. {)}....
对左部为N 的产生式可知： FIRST （→, S N）={，} FIRST （→ε）={ε} FOLLOW （N）={)}
由于SELECT(N →, S N)∩SELECT(N →ε) ={，}∩ { )}= 所以文法是LL(1)的。
预测分析表（Predicting Analysis Table） a ∧ ( ) , #
S →a →∧ →(T) T →S N →S N →S N N →ε →, S N
也可由预测分析表中无多重入口判定文法是LL(1)的。 (3) 对输入串（a,a）#的分析过程为： 栈（STACK） 当前输入符 （CUR_CHAR） 剩余输入符
（INOUT_STRING） 所用产生式 （OPERATION） #S #)T( #)T #)NS #)Na #)N #)NS, #)NS #)Na #)N #) # ( ( a a