南京邮电大学编译原理课后习题答案和讲解2.doc

编译原理习题解答P38-39 8、设有文法GS：SaAbABcA | BBidt | 试问下列符号串（1）aidtcBcAb （3）ab （5）aidtcidtcidtb 是否为该文法的句型或句子。（1）SaAbaBcAbaidtcAbaidtcBcAb 句型但不是句子；（3）SaAbaBbabab 是句型也是句子；（5）SaAbaBcAbaidtcAbaidtcBcAbaidtcidtcBbaidtcidtcidtb句型也是句子。P39 10、给定文法：SaB | bAAaS | bAA | aBbS | aBB|b 该文法所描述的语言是什么？L(G)相同个数的a与b以任意次序连接而成的非空符号串。P39 11、试分别描述下列文法所产生的语言（文法开始符号为S）：（1） S0S | 01（2） SaaS | bc（3） S: =aSd | aAdA: =aAc | bc（4） S: =ABA: =aAb | abB: =cBd | （1） L(G)0n1| n1； （2） L(G)a2nbc | n0；（3） L(G)aibcjdk | i, j, k1, i=j+k-1；或者 L(G)aj+k-1bcjdk | j, k1；（4） L(G)anbncmdm | m0, n1。P39 15. 设文法G规则为：S：=ABB：=a|SbA：=Aa|bB对下列句型给出推导语法树，并求出其句型短语，简单短语和句柄。（2）baabaab （2） S A B A a S b b B A B a b B a a句型baabaab的短语a, ba, baa, baab, baabaab，简单短语a，句柄 aP40 19. 证明下述文法是二义的1) S:=iSeS|iS|i3) S:=A|BA:=aCbA|aB:=BCC|aC:=ba (最简单的就是a为句型)1) 对于句子iiieii可构造两棵不同的语法树，所以证明该文法是二义的。 P41 24. 下面文法那些是短语结构文法，上下文有关文法，上下文无关文法，及正规文法？1.S:=aB B:= cB B:=b C:=c2.S:=aB B:=bC C:=c C:=3.S:=aAb aA:=aB aA:=aaA B:=b A:=a4.S:=aCd aC:=B aC:=aaA B:=b5.S:=AB A:=a B:=bC B:=b C:=c6. S:=AB A:=a B:=bC C:=c C:=7. S:=aA S:= A:=aA A:=aB A:=a B:=b8. S:=aA S:= A:=bAb A:=a正规文法 1 2 7 上下文无关文法 5 6 8 上下文有关文法 3 短语结构文法 4P42 29. 用扩充的BNF表示以下文法规则：1 Z:=AB|AC|A2 A:=BC|BCD|AXZ|AXY3 S:=aABb|ab4 A:=Aab|解:1Z:=A（B|C|）:=AB|C2A:=BC（|D）X（Z|Y）:= BCD X（Z|Y）3A:=a(AB|)b) := aABb4A:=abP74 4. 画出下列文法的状态图：Z：=Be B：=Af A：=e|Ae 并使用该状态图检查下列句子是否该文法的合法句子：f, eeff, eefe。由状态图可知只有eefe是该文法的合法句子。P74 5. 设右线性文法G=(S, A, B, a, b, S, P)，其中P组成如下：S：=bA A：=bB A：=aA A：=b B：=a画出该文法的状态转换图。P74 8. 设 (NFA) M = ( A, B, a, b, M, A, B )，其中M定义如下：M (A, a) = A, B M (A, b) = B M (B, a) = M (B, b) = A, B请构造相应确定有穷自动机(DFA) M。解：构造一个如下的自动机(DFA) M， (DFA) M=K, a, b, M, S, ZK的元素是A B A, B由于M（A, a）=A, B，故有M（A, a）=A, B同样 M（A，b）=BM（B，a）= M（B，b）=A，B由于M（A，B，a）= M（A，a）U M（B，a）= A，BU = A，B故 M（A，B，a）= A，B由于M（A，B，b）= M（A，b）U M（B，b）=BU A，B = A，B故 M（A，B，b）= A，BS=A，终态集Z=A，B，B重新定义：令0=A 1=B 2=A, B，则DFA如下所示：P74 10. 已知正规文法G = (S, B, C, a, b, c, P, S)，其中P内包含如下产生式： S:=aS | aB B:=bB | bC C:=cC | c 请构造一个等价的有穷自动机。解：M=(S, B, C, T, a, b, c, M, S, T)M (S, a)=S M (S, a)=B M (S, b)= M (S, c)=M (B, a)= M (B, b)=B M (B, b)=C M (B, c)=M (C, a)= M (C, b)= M (C, c)=T M (C, c)=CP74 11. 构造下列正规式相应的DFA： （1）1(0|1)*101 解：先构造该正规式的转换系统：SZ1(0|1)*101S1534Z1101(0|1)*S1534Z1101201由上述转换系统可得状态转换集K=S, 1, 2, 3, 4, 5, Z，状态子集转换矩阵如下表所示：II0I1K0 1S1, 2, 30 11, 2, 32, 32, 3, 41 2 32, 32, 32, 3, 42 2 32, 3, 42, 3, 52, 3, 43 4 32, 3, 52, 32, 3, 4, Z4 2 52, 3, 4, Z2, 3, 52, 3, 45 4 3其对应的DFA状态转换图为：051123100114001100511, 23401111000现在对该DFA进行化简，最终得到下列化简后的状态转换图（先将其分成两组终态组5和非终态组0, 1, 2, 3, 4，再根据是否可继续划分来确定最后的组数）：P74 12. 将图3.24非确定有穷自动机NFA确定化和最少化。10aa, ba图3.24 NFA状态转换图解：设(DFA)M = K, VT, M, S, Z，其中，K=0, 0, 1, 1，VT =a, b，M：M (1, a) =0 M (1, b) = M (0, 1, a) =0, 1 M (0, 1, b) =1M (0, a) =0, 1 M (0, b) =1S=1，Z=0, 0, 110abaa2b令0, 1=2，则其相应的状态转换图为：现在对该DFA进行化简，先把状态分为两组：终态组 0, 2 和非终态组 1，易于发现 0, 2不可以继续划分，因此化简后的状态转换图如下：10, 2abaP74 18. 根据下面正规文法构造等价的正规表达式：S:=cC | a A:=cA | aB B:=aB | c C:=aS | aA | bB | cC | a 解：由式可得 B= aB + c B=a*c 由式可得 A= cA + aB A= c*aa*c 由式可得 S= cC + a 由式可得 C= aS + aA + bB + cC + a C= c*( aS + aA + bB + a) C= c*( aS + ac*aa*c + ba*c + a) S= cc*( aS + ac*aa*c + ba*c + a) + a = cc*aS+ cc*( ac*aa*c + ba*c + a) + a = (cc*a)*( cc*( ac*aa*c + ba*c + a) + a) = (cc*a)*( cc*( ac*aa*c | ba*c | a) | a) P142 1. 试分别消除下列文法的直接左递归（采用两种方法重复法和改写法）（1）GE:E:=T | EAT T:=F | TMF F:=(E) | i A:=+ | - M:=* | / 解：先采用“重复法”： 再采用“改写法”：E:=TAT E:=TET:=FMF E:= ATE | F:=(E) | i T:=FTA:=+ | - T:=MFT | M:=* | / F:=(E) | i A:=+ | - M:=* | /（4）GZ:Z:=V1 V1:=V2 | V1iV2 V2:=V3 | V2+V3 V3:=)V1* | ( 解：先采用“重复法”： 再采用“改写法”：Z:=V1 Z:=V1V1:=V2 iV2 V1:=V2 V1V2:=V3 +V3 V1:=i V2 V1 | V3:=)V1* | ( V2:=V3 V2 V2:=+V3 V2 | V3:=)V1* | (P142 2. 试分别消除下列文法的间接左递归（2）GZ:Z:=AZ | b A:=Z A | a 解(一)：将式代入式可得，Z:=ZAZ | aZ | b 消除左递归后得到： Z:=(aZ | b)Z Z:=AZZ | A:=ZA | a解(二)：将式代入式可得，A:= AZA | bA | a 消除左递归后得到： Z:= AZ | b A:=bAA | aA A:=ZAA |P143 5. 对下面的文法GE: E:=TE E:=+E | T:=FTT:=T | F:=PFF:=*F | P(E) |a |b |（1）计算这个文法的每个非终结符号的FIRST和FOLLOW；（2）证明这个文法是LL（1）文法；（3）构造它的LL（1）分析表并分析符号串a*b+b;解:（1）构造FIRST集：FIRST(E)=+, FIRST(F)=*, FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P) = (，a，b，FIRST(T)= (，a，b, ，构造FOLLOW 集：规则一FOLLOW(E) FOLLOW(E)=#规则二)FOLLOW(E) FOLLOE(E)= )，#FIRST(E)-FOLLOW(T) FOLLOW(T)=+FIRST(T)-FOLLOW(F) FOLLOW(F)= (，a，b，FIRST(F)-FOLLOW(P) FOLLOW(P)=*规则三FOLLOW(E)FOLLOW(E) FOLLOW(E)=#，)FOLLOW(E)FOLLOW(T) FOLLOW(T)=，）FOLLOW(T)FOLLOW(T) FOLLOW(T)= ，）FOLLOW(T)FOLLOW(F) FOLLOW(F)= (，)，a，b，FOLLOW(F)FOLLOW(F) FOLLOW(F)= (，)，a，b，FOLLOW(F)FOLLOW(P) FOLLOW(P)= (，)，a，b，,*最后结果为：FIRST(E)=+, FIRST(F)=*, FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P) = (，a，b，FIRST(T)= (，a，b, ，)FOLLOE(E)= ), FOLLOW(E)=，)FOLLOW(T)=，）FOLLOW(T)= ，）FOLLOW(F)= (，)，a，b，FOLLOW(F)= (，)，a，b，FOLLOW(P)= (，)，a，b，,*（2）证明该文法是LL（1）文法：证明：对于规则E:=+E |，T:=T |，F:=*F | （仅有一边能推出空串）有FIRST(+E)=+FIRST()= ，FIRST(T)=(, a, b, FIRST()= FIRST(*F)=*FIRST()= ，FIRST(+E)=+FOLLOW(E)= #, )= FIRST(T)=(, a, b, FOLLOW(T)= +, #, )=FIRST(*F)=*FOLLOW(F)= (，)，a，b，=所以该文法是LL（1）文法。（3）构造文法分析表ab+*()#EETEETEETEETEEE+EEETTFTTFTTFTTFTTT TT TT T TT T TT FFPFFPFFPFFPFFF F F F*FF F F F PP aP bP (E)P 下面分析符号串a*b+b步骤 分析栈 余留输入串 所用的产生式1 #E a*b+b# ETE2 #ET a*b+b# TFT3 #ETF a*b+b# FPF4 #ETFP a*b+b# P a5 #ETFa a*b+b# 6 # ETF *b+b# F*F7 # ETF* *b+b#8 # ETF b+b# F 9 # ET b+b# T T10 # ET b+b# TFT11 # ETF b+b# FPF12 # ETFP b+b# P b13 #ETFb b+b#14 #ETF +b# F 15 #ET +b# T 16 #E +b# E+E17 #E+ +b# 18 #E b# ETE19 #ET b# TFT20 #ETF b# FPF21 # ETFP b# P b22 # ETFb b# 23 # ETF # F 24 # ET # T 25 #E # E26 # # 成功所以符号串a*b+b是该文法的句子；P145 13. 利用表4.6文法GE的优先关系矩阵，来分析符号串#b(aa)a)a)b#和#(aa)a)#。(1) 是文法的句子步骤符号栈关系输入串规则1#b(aa)a)a)b#2#b(aa)a)a)b#3#b(aa)a)a)b#4#b(aa)a)a)b#5#b(a)a)a)b#7#b(M=a)a)a)b#M=a8#b(Ma=)a)a)b#9#b(Ma)a)a)b#10#b(La)a)b#L=Ma)11#b(M=a)a)b#M=(L12#b(Ma=)a)b#13#b(Ma)a)b#14#b(La)b#L=Ma)15#b(M=a)b#M=(L16#b(Ma=)b#17#b(Ma)b#18#b(Lb#L=Ma)19#bM=b#M=(L20#bMb#21#Z#Z=bMb(2) 不是文法的句子步骤符号栈关系输入串规则1#(aa)a)#2#( (aa)a)#3#(a)a)#5#(M=a)a)#M=a6#(Ma=)a)#7#(Ma)a)#8#(La)#L=Ma)9#(M=a)#M=(L10#(Ma=)#11#(Ma)#12#(L#L=Ma)13#M#M=(LP146 17. 设已给文法GS: EE+T | TTT*F | FFPF | P P(E) | i（1） 用迭代法构造优先函数；（2） 用优先函数表分析符号串i+i*ii解：(i*+)(=*+（1）用迭代法构造优先函数若R=S则f(R）=g(S)若RS则f(R）S则f(R）g(S) 初始值*()if111111g111111根据的优先关系修改f和g值*()if333133g222212根据=的优先关系修改f和g值*()if333133g244414重复*()if355155g244414*()if355155g246616*()if355177g246616最终结果：*()if355177g246616（2）用优先函数表分析字符串i+i*ii符号栈关系输入串最左素短语f(#)g(+)+i*ii#if(#) g(+)+i*ii#f(+)g(*)*ii#if(+) g(*)*ii#*f(*)g()i#i*f(*) g()i#*f()g(#)#i*f() g(#)#*f(*) g#)#*f(+) g(#)#成功P146 19. 证明下面文法不是算符优先文法: SA | AaA | BBaS证明： SA AaAA AaA aAA BB a a 和a 矛盾，所以该文法非算符优先文法P146 21. 利用表4.8文法GE优先关系矩阵分析下列句子: i, i+i, i*i+i, i*(i*i)以及i*(i+i*i)+(i+i)*i解：以i*i+i为例，其余类似：符号栈关系输入串最左素短语*i+i#i*i+i#*+i#i*+i#*+i#+#i+#+#成功i*i+i是文法GE的句子；再以i*(i*i)为例：符号栈关系输入串最左素短语*(i*i)#i*(i*i)#*(i*i)#*(*i)#i*(*i)#*(*)#i*(*)#*()#*()#()*#*#成功i*（i*i）是文法GE的句子；P146 22. 设有文法GZ: ZA | BAaAb | cBaBb | d（1） 试构造能识别此文法的全部活前缀DFA；（2） 试构造LR(0)分析表；（3） 试分析符号串aacbb是否为此文法的句子。解：在上述文法中引入新的开始符号Z，并将Z:=Z作为第0个规则，从而得到所谓的拓广文法G，则其LR（0）项目有：Z := Z Z := Z Z:= A Z:= A Z := B Z := B A := aAb A := aAb A:= aA b A :=aAb B := aBb B := aBb B :=aB b B := aBb B:= d B:= d A:=c A:= c(1)ZI0: Z := Z Z:= A Z := B A := aAbA:=c B := aBbB:= d I1: Z := ZI5: A:= cI4: A := aAb A := aAb A:=cB := aBb B := aBb B:= dI3: Z := BI2: Z:= AI6: B:= dI7:A:= aAbI8:B :=aBbI10:B:= aBbI9:A:= aAbbABacdacdAbB(2)构造LR（0）分析表状态 ACTIONGOTOa b c d #Z A B0S4S5S61 2 3 7 8 1acc2r1r1r1r1r13r2r2r2r2r24S4S5S65r4r4r4r4r46r6r6r6r6r67S98S109r3r3r3r3r310r5r5r5r5r5规则顺序：r1：ZA r2：ZB r3: AaAb r4: AC r5: BaBb r6: Bd(3)分析符号串aacbb是否为该文法的句子步骤状态栈符号栈输入串分析动作下一状态10aacbbS44204aacbbS443044aacbbS5540445aacbbr4GOTO4,A=750447aaAbbS99604479aaAbbr3G