编译原理及实现课后习题答案.docx

《编译原理及实现课后习题答案.docx》由会员分享，可在线阅读，更多相关《编译原理及实现课后习题答案.docx（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2.1设字母表人=匕,符号串x=aaa,写出下列符号串及其长度：x。, xx, x5以及A+和A*.x= (aaa)= e|. x|=0xx=aaaaaa|xx|=6x5=aaaaaaaaaaaaaaa| x5|=15A+ =A1 U A2 U . U A nU aa, aaa, aaaa, aaaaa*A* = A0 U A1 U A2 U . U A n U = e , a, aa, aaa, aaaa, aaaaa* 2. 2 令工=匕，b, c),又令x二abc, y=b, z=aab,写出如下符号串及它们的长度：xy, xyz, (xy) 3xy=abcb.|xy|=4xyz=abc

2、baab|xyz|=7(xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=122.3 设有文法GS： S：=SS*|SS+|a,写出符号串aa+a*规范推导，并构造语法树。S = SS* 二Sa* 二 SS+a* = Sa+a* = aa+a*4已知文法GZ： Z：=UO | VI U： ：=Z1 | 1 V：=ZO | 0 ,请写出全部由此文法描述的只含有四个符号的句子。Z=U0=Z10=U010=1010Z=UO=Z1O=V110=0110Z=Vl=Z01=U001=1001Z=Vl=Z01=V101=01012.5 已知文法GS： S：=AB A：=aA | e

3、B：=bBc | be ,写出该文法描述的语言。A： ：=aA | 描述的语言：an|n=0B：=bBc | be 描述的语言：bncn|n=lL (G S) = anbmcm | n=0, m=l已知文法E：hI E+T | E-T、T：=F | T*F | T/F、F： = (E) | i,写出该文法的开始符号、终结符号集合Vt、非终结符号集合Vn。（1） 考虑下面简化了的C声明文法：声明语句一类型X变量表）；类型-int | float | char变量表f ID,变量表 | ID（1） 在该文法中提取左因子。（2） 为所得的文法的非终结符构造FIRST集合和FOLLOW集合。（3） 说

4、明所得的文法是LL文法。（4） 为所得的文法构造LL分析表。（5） 假设有输入串为“char x, y, z； ”，写出相对应的LL分析过程。解：（2） 规则变量表f ID,变量表| ID提取公因子如下：变量表ID （，变量表| ） 增加新的非终结符变量表1,规则变为：变量表f ID变量表1变量表lf,变量表| .C声明文法改变为：声明语句一类型X变量表；类型f int | float | char变量表-ID变量表1变量表1一,变量表| （3） FIRST（声明语句）=FIRST（类型）=int, float, char）FIRST （变量表 ）=IDFIRST（变量表 1）= , e FO

5、LLOW （声明语句 ）=#FOLLOW （类型 ）=FIRST （变量表 ）=IDFOLLOW （ 变量表）=FOLLOW （变量表 1 = ；（4） 所得文法无左递归，且FIRST （int） nFIRST （float） nFIRST （char） =OFIRST （,变量表）DFIRST （ ） =（DFIRST （,变量表）AFOLLOW（变量表 1）=因此，所得文法为LL文法。（4） 所得的文法构造LL（1）分析表如下所示:9intfloatcharID#声明 语句POP , PUSH（；变量 表X类型）POP , PUSH（； 变量 表X类型）POP , PUSH（； 变量 表X

6、类型） 类 型POP , PUSH (int)POP , PUSH(float)POP , PUSH(char)变量 表POP , PUSH变量表 DID)变量 表1POPPOP ,PUSH变量表，） 9POPNEX TSYMintPOP,更常用且简单的LL(1)分析表:NEXTSYMfloatPOP, NEXTSYMcharPOP, NEXTSYMIDPOP, NEXTSYMPOP, NEXTSYM#ACCEPT 9intfloatcharID9ft声明 语句声明语句一 类型X变量 表；声明语句一 类型 变量 表；声明语句一 类型X变量 表； 类 型类型)f int 类型f float 类型

7、f char变量 表变量表 f ID变 量表1变量 表1变 量表1 一8变量 表 D f , 变 量表)(5) 输入串“char x, y, z； ”相对应的LL(1)分析过程如下:步骤分析栈余留输入串分析表元素所用产生式1#声明语句char x, y, z； #POP , PUSH(；变量表 类型)声明语句一 类型X变量 表)；2#;变量表X类 型char x, y, z； #POP , PUSH(char)类型 f char3#;变量表 charchar x, y, z； #POP, NEXTSYM4变量表x, y, z； #POP , PUSH变量表 DID)变量表-ID 变量表15#;

8、 变量表Dxx, y, z； #POP, NEXTSYM6#; 变量表1,y, z； #POP ,PUSH(变量表,)变量表1一， 变量表7#;变量表，,y, z； #POP, NEXTSYM8#; 变量表y，z； #POP , PUSH变量表 DID)变量表-ID 变量表19#； 变量表lyy，z； #POP,NEXTSYM10#; 变量表1，Z； #POP ,PUSH（变量表,）变量表, 变量表11#; 变量表，z； #POP, NEXTSYM12机变量表Z; #POP ,PUSH变量表DID）变量表f id 变量表i13#;变量表lzZ; #POP, NEXTSYM14#; 变量表1PO

9、P变量表lf 15#;#POP, NEXTSYM16#ACCEPT5.1 考虑以下的文法：S-S;T|TTf a1.1 为这个文法构造LR (0)的项目集规范族。1.2 这个文法是不是LR(0)文法？如果是，则构造LR(0)分析表。1.3 对输入串进行分析。解：(1)拓广文法GS0： S fS1： S-S;T2： ST3： Ta构造LR(0)项目集规范族(2)该文法不存在“归约一归约”和“归约一移进”冲突，因此是LR(0)文法。LR(0)分析表如下:状态项目集转换函数0S f S Sf S;T ST T一 aG00, S=lG00, S=lG00, T=2G00, a =31S fSSfS ;

10、TACCEPTG0l, ;=42S-TR23Ta R34SS;TT aGO4, T=5GO4, a =35S-S;TRI状态ACTIONGOTOa#ST0S3121S4ACCEPT2R2R2R23R3R3R34S355RIRIRI(3)对输入串“a;a”进行分析如下:步骤状态栈符号栈输入符号栈ACTIONGOTO00#a; a#S3103#a;a#R32302#T;a#R21401#S;a#S45014#S;a#S360143#S;a#R3570145#S;T#RI1801tts#ACCEPT5.2 证明下面文法是SLR(l)文法，但不是LR(O)文法。S-AA-Ab |bBaBf aAc |

11、 a | aAb解：文法GS：0： Sf A1： A-Ab2： A-bBa3： Bf aAc4： Bf a5： Bf aAb构造LR(0)项目集规范族:状态项目集转换函数0S AG00, A = lA AbG00, A=lA bBaG00, b=21SAACCEPTAA bG0l, b=32Af b BaGO2, B=4Bf aAcGO2, a =5B一 aGO2, a =5B aAbGO2, a =53Af Ab RI4AbB aGO4, a =65Bf a AcGO5, A =7Ba R4B-a AbGO5, A =7A AbGO5, A =7Af bBaGO5, b=26A-bBa R2

12、7Bf aA cGO7, c=8BaA bGO7, b=9AA bGO7, b=98Bf aAc R39BaAb R5AAb RI状态5存在“归约一移进”冲突，状态9存在“归约一归约”冲突，因此该文法不是LR(O)文法。状态5：FOLLOW(B) = a,因此,FOLLOW(B) n b =0状态9：FOLLOW (B) = a, FOLLOW (A) = #, b, c),因此 FOLLOW (B) n FOLLOW (A)=状态5和状态9的冲突均可用SLR(l)方法解决，构造SLR(l)分析表如下：状态ACTIONGOTOabcAB0S211S3ACCEPT2S543RIRIRI4S65R

13、4S276R2R2R27S9S88R39R5RIRIRI该SLR(1)分析表无重定义，因此该文法是SLR(1)文法，不是LR(O)文法。5.3 证明下面文法是LR文法，但不是SLR(l)文法。SAaAb |BbBaA- Bf e解：拓广文法GS0： S -s1： SAaAb2： SfBbBa3： A- e4： B- e构造LR(O)项目集规范族:状态项目集转换函数0S 一 SS AaAbSf BbBaA一 Bf GOEO, S=l G00, A =2 GOE0, B=3 R3 R41S -SACCEPT2Sf A aAbG0E2, a =43Sf B bBaG0E3, b=54S-Aa AbA

14、f G0E4, A =6R35Sf Bb BaB一 G0E5, B=7R46Sf AaA bG0E6, b=87Sf BbB aG07, a =98Sf AaAb RI9Sf BbBa R2状态 0 存在“归约一归约”冲突,且 FOLLOW (A) = a, b。FOLLOW (B) = a, b。即 FOLLOW (A) A FOLLOW (B) = a,b W，所以该文法不是SLR(l)文法。构造LR项目集规范族：状态项目集转换函数0SS, # Sf AaAb, # Sf BbBa, # A , a Bf , bG00, S=lG00, A =2G00, B=3R3R41S -s , #A

15、CCEPT2SAaAb, #GO2, a =43SBbBa, #GO3, b=54S-AaAb, #Af , bGO4, A =6R35S-Bb Ba, #B , aGO5, B=7R46S-AaAb, #GO6, b=87S-BbBa, UGO7, a =98S-AaAb , itRI9S-BbBa，#R2LR分析表:分析表无重定义，说明该文法是LR文法，不是SLR(1)文法。状态ACTIONGOTOab#SAB0R3R41231ACCEPT2S43S54R365R476S87S98RI9R25.4 考虑以下的文法：E-EE+EEE*Ea(1)为这个文法构造LR项目集规范族。(2)构造LR分

16、析表。.(3)为这个文法构造LALR项目集规范族。(4)构造LALR分析表。(5)对输入符号串“aa*a+”进行LR和LALR 分析。解：(1)拓广文法GS：0： S-E1： E-EE+2： EEE*3： Ea构造LR项目集规范族:状态项目集转换函数0S- E , #G00, E=lEf EE+ , a:#G00, E=lEf EE* , a:#G00, E=lEf a , a:#G00, a =21S-E，#ACCEPTEEE+ , a:#GO El, E=3EE E* , a:#G0l, E=3Ef EE+ , *: +G0l, E=3E EE* , *: +G0l, E=3Ef a ,

17、*: +G0l, a =42Ef a , a:#R33E-EE + , a:#G03, +=5EEE * , a:#G03, *=6EE E+ , *: +GO3, E=7EE E* , *: +GO3, E=7Ef EE+ , *: +GO3, E=7E EE* , *: +G03, E=7E a , *: +GO3, a =44Ef a , *: +R35EEE+ , a:#RI6Ef EE* , a:#R27Ef EE +,*: +G07, +=8Ef EE * , *: +GO7, *=9EE E+ , *: +GO7, E=7Ef E E* , *: +GO7, E=7Ef EE+

18、, *: +G07, E=7Ef EE* , *: +G07, E=7E a , *: +GO7, a =48EEE+ , *: +RI9Ef EE* * , *: +R2（2）构造LR分析表状态ACTIONGOTO+*a#E0S211S4ACCEPT32R3R33S5S6S474R3R35RIRI6R2R27S8S9S478RIRI9R2R2(3)构造LALR项目集规范族:状态项目集转换函数0S- E , #E EE+ , a:#Ef EE* , a:#Ef a , a:#G00, E=lG00, E=lG00, E=lG00, a =21S-E,#E-E E+ , a:# EE E* ,

19、a:# Ef EE+ , *: + E EE* , *: + E a , *: +ACCEPTGO1, E=3GO1, E=3G0E1, E=3G0l, E=3G0l, a =22Ef a , a:#:*: +R33EEE + , a:#:*: + EEE * , a:#:*: + Ef E E+ , *: + Ef E E* , *: + E EE+ , *: + E EE* , *： + E a , *: +GO 3, +=4GO 3, *=5GO 3, E=3GO 3, E=3G03, E=3G03, E=3 GO3, a =24EfEE+ , a:#:*: +RI5E-EE* , a:

20、#:*: +R2(4)构造LALR分析表。状态ACTIONGOTO+*a#E0S211S2ACCEPT32R3R3R3R33S4S5S234RIRIRIRI5R2R2R2R2(5)对输入符号串“aa*a+”进行LR分析:步骤状态栈符号栈输入串ACTIONGOTO10#aa*a+#S2202#aa*a+#R31301#Ea*a+#S44014#Ea*a+#R335013#EE*a+#S660136#EE*a+#R21701#Ea+#S48014#Ea+#R339013#EE+#S5100135#EE+RI11101#E#ACCEPT对输入符号串“aa*a+”进行LALR分析:步骤状态栈符号栈输入

21、串ACTIONGOTO10#aa*a+#S2202#aa*a+#R31301#Ea*a+#S24012#Ea*a+#R335013#EE*a+#S560135#EE*a+#R21701#Ea+#S28012#Ea+#R339013#EE+#S4100134#EE+RI11101#E#ACCEPT5.5 说明以下的文法是LR(1)文法，但不是LALR(l)文法。Sf aAd | bBd | aBe | bAeAf cBf c解：拓广文法：0： S fS1： Sf aAd2： S-bBd3： Sf aBe4： SbAe5： Af c6： Bf c构造LR项目集规范族状态项目集转换函数0S 一S,

22、#G00, S=lS aAd, #G00, a =2Sf bBd, ttG00, b=3Sf aBe, #G00, a =2S bAe, #G00, b=31S fS,ttACCEPT2S-aAd, #GO2, A =4Sf a Be, #GO2, B=5A c, dGO2, c=6Bf c, eGO2, c=63S-b Bd, #GO3, B=7S-b Ae, #GO 3, A =8A c, eGO3, c=9Bf c, dGO3, c=94SaAd, ttGO 4, d=105Sf aB e, #G05, e=ll6Ac , dR5Bc , eR67S-bBd, #GO 7, d=128S

23、bAe, #GO 8, e=139Af c , eB-c , dR5R610SaAd* , #RI11SaBe , #R312SiBd,#R213S-bAe,#R4构造LR分析表:状态ACTIONGOTOabcde#SAB0S2S311ACCEPT2S6453S9874S105Sil6R5R67S128S139R6R510RI11R312R213R4同核项目集合并，构造LALR(l)项目集规范族:状态项目集转换函数0S 一 S, #G00, S=lS aAd, #G00, a =2S bBd, #G00, b=3Sf aBe, #G00, a =2Sf bAe, #G00, b=31S#ACC

24、EPT2SaAd, #GO2, A =4Sf a Be, #GO2, B=5Af c, dG02, c=6Bf c, eG02, c=63SiBd, #G03, B=7SbAe, #G03, A =8A c, eGO3, c=6Bf c, dGO3, c=64S-aAd, #GO4, d=95Sf aB e, #GO 5, e=106Ac , d:eBf c , d:eR5R6开始符号：EVt= +,i)Vn=E , F , T2.1 对2. 6题的文法，写出句型T+T*F+i的短语、简单短语以及句柄。短语：T+T*F+iT+T*F11TT*F简单短语：iT*FT句柄：T .2.8 设有文法

25、GS： S：=S*S|S+S| (S) | a,根据所给文法推导出句子a+a*a,画出了两棵不同的语法树，所以该文法是二义性文法。2. 9写一文法，使其语言是奇正整数集合。A:=1|3|5|7|9|NAN:=0|l|2|3|4|5|6|7|8|9 2. 10给出语言anbm|n,m21的文法。GS: S:=ABA:=aA|aB:=bB|b有正则文法GZ： Z:=Ua|Vb, U:=Zb|b, V:=Za|a ,画出该文法的状态图，并检查句子abba是否合法。 解：该文法的状态图如下：句子abba合法。3.1 状态图如图3. 35所示，S为开始状态，Z为终止状态。写出相应的正则文法以及V, k和

26、。7SiBd, #GO7, d=ll8S-bAe, #GO 8, e=129SaAd,ttRI10SaBe , ttR311SbBd,#R212S-bAe,#R4构造LALR(l)分析表:从LR分析表可以看出，分析表无重定义，因此该文法是LR文法。状态ACTIONGOTOabcde#SAB0S2S311ACCEPT2S6453S9874S105Sil6R5/R6R5/R67S128S139RI10R311R212R4从LALR(l)分析表可以看出，分析表ACTION6, d和ACTI0N6, e存在重定义，因此该文法不是LALR(l)文法。图335状态图右线性文法Vn=S,AVt= a, b解

27、：左线性文法GZ:G，S:Z:=Ab|bS:=aA|b A:=Aa|aA:=aA|bV=Z, A, a, b, V= S, A, a, b) Vn=Z, A.Vt= a, b.3.2 构造下列正则表达式相应的NFA：1(1|0)*|01(1010*11(010)*1)*0解：正则表达式：1(1|0)*|04、 3正则表达式：1(1010*11(010)*1)*03.4 将右图的NFA M确定化1ql=0, 10,11q2=l0(DDFA:a.3.5 将图3.37的DFA化简。佟13.37 DFA斗犬态佟I ,4.1 对下面文法，设计递归下降分析程序。S-aAS| (A) , . A-Ab|c解

28、：首先将左递归去掉，将规则A-Ab|c改成A-cb 非终结符号S的分析程序如下：设有文法GZ：Z： = (A) A：=a|Bb B：=Aab若采用递归下降分析方法，对此文法来说，在分析过程中，能否避免回溯？为什么？解：若采用递归下降分析方法，对此文法来说，在分析过程中不能避免回朔。因为规则A：二a|Bb和规则B：=Aab 构成了间接左递归，不满足实现没有回溯的递归下降分析方法的条件(1)(书P67),且规则A:二a|Bb, FIRST (a) = a, FIRST (Bb) = a,即此规则候选式的首符号集有相交，不满足实现没有回溯的递归下降分析方法的 条件(2)(书P67),在分析过程中，将

29、造成回溯。.改写文法可避免回溯：将规则B：二Aab代入规则A：二a|Bb得：A：=a|Aabb,再转换成：A：=aabb,可避免回溯。4.2 若有文法如下，设计递归下降分析程序。语句一语句赋值语句| 赋值语句 -IDX表达式表达式一项|表达式+项)|表达式一项项一因子|项*因子|项/因子因子f ID|NUM| (表达式)解：首先，去掉左递归语句一语句X赋值语句| 改为：语句一赋值语句表达式一项 |表达式+项|表达式-项改为:表达式一项(+ | -)项项f因子 I 项 *因子I项/因子改为：项f因子 (* I /) 因子则文法变为：语句一 赋值语句赋值语句f 口=表达式)表达式一项 (+ I -

30、)项 项f因子 (* I /)因子 因子一加101|(表达式)4. 4 有文法 G法:A: :=aABe| , B: =Bb | b(1)求每个非终结符号的FOLLOW集。(2)该文法是LL文法吗？(3)构造LL分析表。.解：(1) FOLLOW (A)=First (B) U # = b, #FOLLOW (B) = e, b(2) 该文法中的规则B:=Bb|b为左递归，因此该文法不是LL文法(3) 先消除文法的左口匕,在毋十毋七、+计* a._adJ * B:=bB , B二bB | e ,该文法的LL用先头n复值语句的分析程序aeb#APOP , PUSH(eBAa)POPPOPBPOP

31、 , PUSH(B b)B，POPPOP , PUSH(B b)aPOP,更常用且简单的LL(1)分析表:NEXTSYMePOP, NEXTSYMbPOP, NEXTSYMACCEPTaeb#AA-aABeAf Af BBiBB，B，_ B -bB4. 5若有文法Af (A)A| e(1)为非终结符A构造FIRST集合和FOLLOW集合。(2)说明该文法是LL的文法。解：(1) FIRST (A) = (, e .FOLLOW (A) = ), #.(2)该文法不含左递归；FIRST (A)A) =(, FIRST ( e ) = e , FIRST (A)A) nFIRST ( e ) =O

32、, K FOLLOW (A) = ), #, FIRST (A) A) Cl FOLLOW (A)=， 因此，该文法满足LL(1)文法的条件，是LL(1)文法。4.6利用分析表4T,识别以下算术表达式，请写出分析过程。(1) i+i*i+i(2) i*(i+i+i)解：(1) i+i*i+i步骤分析栈余留输入串分析表元素所用产生式1#Ei+i*i+i#POP, PUSH(E, T)ETE2#E，Ti+i*i+i#POP, PUSH(T, F)T-FT3#E T Fi+i*i+i#POP, PUSH(i)FT4#E T, ii+i*i+i#POP, NEXTSYM5#E T+i*i+i#POP一 6#E+i*i+i#POP, PUSH(E, T+)E f+TE7#E T+i*i+i#POP, NEXTSYM8#E Ti*i+i#POP, PUSH(T, F)TfFT9#E T Fi*i+i#POP, PUSH(i)FT10#E T ii*i+i#POP, NEXTSYM11#E 丁i+i#POP, PUSH(T, F*)T *FT12#E 丁 F*i+i#POP, NEXTSYM13#EFi+i#POP, PUSH(i)Fi14T ii+i#POP, NEXTS