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

资源描述

《1编译原理及实现课后题及答案.docx》由会员分享，可在线阅读，更多相关《1编译原理及实现课后题及答案.docx（58页珍藏版）》请在三一办公上搜索。

1、编译原理及实现2.1设字母表A=a,符号串x=aaa，写出下列符号串及其长度：x,xx,x5 以及 A+和 A*.X0=(aaa) 0= e| x0|=0xx=aaaaaa|xx|=6x5=aaaaaaaaaaaaaaa| xs|=15A+ =Ai UA2U . UA nU =a,aa,aaa,aaaa,aaaaaA* = A0 U Ai UA2 U .U A n U = e ,a,aa,aaa,aaaa,aaaaa2.2 令 = &, b, c,又令x=abc, y=b, z=aab,写出如下符号串及它们的长度：xy, xyz, (xy) 3xy = abcbI xy 1= 4xyz = a

2、bcbaabI xyz I= 7(xy)3 = (abcb)3 = abcbabcbabcbI (xy)31= 122.3 设有文法GS: S：=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语法树。S = SS* = Sa* = SS+a* = Sa+a* = aa+a*2.4 已知文法 GZ:Z：=U0 | V1、 U：=Z1|1 、 V：=Z0|0,请写出全部由此文法描述的只含有四个符号的句子。Z = U0 = Z10 = U010 = 1010Z = U0 = Z10 = V110 = 0110Z = V1 = Z01 = U001 = 1001Z = V1 = Z01 =

4、+i的短语、简单短语以及句柄。短语：T+T*F+iIT简单短语：iTT+T*FiT*FT*F句柄：T2.8设有文法GS: S：=S*S|S+S|(S)|a，该文法是二义性文法吗？根据所给文法推导出句子a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。2.9写一文法，使其语言是奇正整数集合。A:=1|3|5|7|9|NAN:=0|1|2|3|4|5|6|7|8|92.10给出语言anbm|n,mN1的文法。GS: S:=ABA:=aA|aB:=bB|b3.1 有正则文法 GZ: Z:=Ua|Vb, U:=Zb|b, V:=Za|a，画出该文法的状态图，并检查句子abba是否合法。解

6、FA:3.5将图3.37的DFA化简。图3.37 DFA状态图解:划分ab0,112,42,3,4,51,3,0,53,5,2,4划分ab0,112,42,40,13,53,53,52,4q0=0,1q1 = 2,4化简后的DFA:q2=3,54.1对下面文法，设计递归下降分析程序。STaAS|(A) , AfAb|c解：首先将左递归去掉，将规则AAb|c改成ATcb非终结符号S的分析程序如下：非终结符号A的分析程序如下:4.2设有文法GZ:Z：=(A) , A：=a|Bb , B：=Aab若采用递归下降分析方法，对此文法来说，在分析过程中，能否避免回溯？为什么？解：若采用递归下降分析方法，

7、对此文法来说，在分析过程中不能避免回朔。因为规则A：=a|Bb和规则B：=Aab构成了间接左递归，不满足实现没有回溯的递归下降分析方法的条件(1)(书P67),且规则 A: := a|Bb, FIRST(a) = a, FIRST(Bb) = a，即此规则候选式的首符号集有相交，不满足实现没有回溯的递归下降分析方法的条件 (2)(书P67)，在分析过程中，将造成回溯。改写文法可避免回溯：将规则B：=Aab代入规则A：=a|Bb得：A：=a|Aabb，再转换成：A :=aabb，可避免回溯。4.3若有文法如下，设计递归下降分析程序。语句语句赋值语句1 8赋值语句T ID =表达达表达

10、法的 LL(1)分析表为:aeb#APOP ,PUSH（eBAa）POPPOPBPOP ,PUSH（B，b）B，POPPOP ,PUSH（B，b）aPOP, NEXTSYMePOP, NEXTSYMbPOP, NEXTSYM#ACCEPT更常用且简单的LL(1)分析表:aeb#AATaABeATATBBTbBB，B*BTbB4.5若有文法AT (A)A| E(1) 为非终结符A构造FIRST集合和FOLLOW集合。(2) 说明该文法是LL(1)的文法。解：(1) FIRST(A)= (, eFOLLOW(A) =), #(2)该文法不含左递归；FIRST (A)A) =(, FIRST (e)

11、 = e , FIRST (A)A) AFIRST (e)=e,且 FOLLOW(A) =), #, FIRST (A)A)A FOLLOW(A) =0,因此，该文法满足LL(1)文法的条件，是LL(1)文法。4.6利用分析表4-1,识别以下算术表达式，请写出分析过程。(1) i+i*i+i(2) i*(i + i + i)解：(1) i+i*i+i步骤分析栈余留输入串分析表元素所用产生式1#Ei+i*i+i#POP,PUSH(E T)ETTE2#E Ti+i*i+i#POP,PUSH(TF)1 FT3#E T Fi+i*i+i#POP,PUSH(i)FTi4#E T ii+i*i+i#POP

12、,NEXTSYM5#E T+i*i+i#POPT*6#E+i*i+i#POP,PUSH(E T+)ET+TE7#E T+i*i+i#POP,NEXTSYM8#E Ti*i+i#POP,PUSH(TF)TTFT9#E T Fi*i+i#POP,PUSH(i)FTi10#E T ii*i+i#POP,NEXTSYM11#E T*i + i#POP,PUSH(TF*)Ti*FT12#E T F*i + i#POP,NEXTSYM13#E T Fi + i#POP,PUSH(i)FTi14#E T ii + i#POP,NEXTSYM15#E T+ i#POPT*16#E+ i#POP,PUSH(E

13、T+)Ei+TE17#E T+ i#POP,NEXTSYM18#E Ti#POP,PUSH(TF)1 FT19#E T Fi#POP,PUSH(i)FT i20#E T ii#POP,NEXTSYM21#E T#POPT*22#E#POPE*23#ACCEPT(2) i*(i + i + i)步骤分析栈余留输入串分析表元素所用产生式1#Ei*(i + i + i)#POP,PUSH(E T)ETTE2#E Ti*(i + i + i)#POP,PUSH(TF)TTFT3#E T Fi*(i + i + i)#POP,PUSH(i)FTi4#E T ii*(i + i + i)#POP,NEXT

14、SYM5#E T*(i + i + i)#POP,PUSH(TF*)TT*FT6#E T F*(i + i + i)#POP,NEXTSYM7#E T F(i + i + i)#POP, PUSH()E()FT (E)8#E T )E(i + i + i)#POP,NEXTSYM9#E T )Ei + i + i)#POP,PUSH(E T)ETTE10#E T ) ETi + i + i)#POP,PUSH(TF)1 FT11#E T ) ET Fi + i + i)#POP,PUSH(i)FTi12#E T ) ET ii + i + i)#POP,NEXTSYM13#E T ) ET+

15、i + i)#POPT*14#E T ) E+ i + i)#POP,PUSH(E T+)ET+TE15#E T ) ET+ i + i)#POP,NEXTSYM16#E T ) ETi + i)#POP,PUSH(TF)1 FT17#E T ) ET Fi + i)#POP,PUSH(i)FTi18#E T ) ET ii + i)#POP,NEXTSYM19#E T ) ET+ i)#POPT*20#E T ) E+ i)#POP,PUSH(E T+)ET+TE21#E T ) ET+ i)#POP,NEXTSYM22#E T ) ETi)#POP,PUSH(TF)1 FT23#E T )

16、 ET Fi)#POP,PUSH(i)li24#E T ) ET ii)#POP,NEXTSYM25#E T ) ET)#POPT*26#E T ) E)#POPE*27#E T )#POP,NEXTSYM28#E T#POPT*29#E#POPE*30#ACCEPT4.7考虑下面简化了的C声明文法:声明语句类型变量表；类型int|float|char变量表TID,变量表|ID(1) 在该文法中提取左因子。(2) 为所得的文法的非终结符构造FIRST集合和FOLLOW集合。(3) 说明所得的文法是LL(1)文法。(4) 为所得的文法构造LL(1)分析表。(5) 假设有输入串为“char x

17、, y, z;,写出相对应的LL(1)分析过程。解：(1) 规则变量表-ID,变量表| ID提取公因子如下：变量表-ID (，变量表| E )增加新的非终结符变量表1,规则变为：变量表TID变量表1变量表1W,变量表| EC声明文法改变为：声明语句-K类型X变量表；类型- i nt | f I oat | char变量表ID变量表1变量表1W,变量表| e(2) FIRST声明语句=FIRST类型)=( int, float, charFIRST变量表)=( IDFIRST 变量表 1 = , e FOLLOW()=#FOLLOW()=FIRST()=IDFOLLOW(变量表)=FOLLOW

18、()=; (3)所得文法无左递归，且FIRST (int)AFIRST (float)nFIRST (char)=OFIRST (, )nFIRST (e)=FIRST (, )nFOLLOW() = 因此，所得文法为LL(1)文法。(4)所得的文法构造LL(1)分析表如下所示:.;intfloatcharID9#声明语句POP ,PUSH(; 类型)POP ,PUSH(; 类型)POP ,PUSH(; 类型)类型POP , PUSH(in t)POP , PUSH(flo at)POP , PUSH(cha r)变量POP ,PUSH(ID）POPPOP ,PUSH（yNEXTSYM1

19、0#; 变量表1,z; #POP ,PUSH（变量表，）变量表1T, 变量表11# ; 变量表，,z; #POP, NEXTSYM12#;变量表z; #POP ,PUSH（ID）变量表 TID变量表113#; zz; #POP, NEXTSYM14#; 变量表1;#POP变量表1Te15#;#POP, NEXTSYM16#ACCEPT5.1考虑以下的文法：STS;T|Tla(1) 为这个文法构造LR(0)的项目集规范族。(2) 这个文法是不是LR(0)文法？如果是，则构造LR(0)分析表。(3) 对输入串“a;a”进行分析。解：(1)拓广文法GS :0: SS1: SS;T2: ST3: Ta

20、构造LR(0)项目集规范族状态项目集转换函数0S SS S;TSTTaGO0, S=1GO0, S=1GO0, T=2GO0, a =31SS*SS - ;TACCEPTGO1, ;=42ST R23Ta R34STS; TTaGO4, T=5GO4, a =35STS;T R1(2) 该文法不存在“归约一归约”和“归约一移进”冲突，因此是LR(0)文法。LR(0)分析表如下：状态ACTION;a0S31S42R2R23R3R34S35R1R11GOTO#ST12ACCEPTR2R35R1(3) 对输入串“a;a”进行分析如下:步骤状态栈符号栈输入符号栈ACTIONGOTO00#a;a#S31

21、03#a;a#R32302#T;a#R21401#S;a#S45014#S;a#S360143#S;a#R3570145#S;T#R11801#S#ACCEPT5.2证明下面文法是SLR(1)文法，但不是LR(0)文法。STAATAb|bBaBTaAc|a|aAb解：文法GS:0: ST A1: AT Ab2: AT bBa3: BT aAc4: BTa5：BTaAb构造LR(0)项目集规范族:状态项目集转换函数0ST-AAT-AbAT bBaGO0, A=1GO0, A=1GO0, b=21STAATA bACCEPTGO1,b=32Ab BaGO2,B =4B aAcGO2,a =5BaG

22、O2,a =5B aAbGO2,a =53AAb R14AbB aGO4,a =65Ba AcGO5,A =7BaR4Ba AbGO5,A =7A AbGO5,A =7A bBaGO5,b=26AbBa R27BaA cGO7,c =8BaA bGO7,b =9AA bGO7,b =98BaAc R39BaAb R5AAb R1状态5存在“归约一移进”冲突，状态9存在“归约一归约”冲突, 因此该文法不是LR(0)文法。状态5:FOLLOW(B)=a，因此，FOLLOW(B) nb=0状态9:FOLLOW(B)=a, FOLLOW(A) =#, b, c,因此 FOLLOW(B) n FOLLO

23、W(A)=e状态5和状态9的冲突均可用SLR(1)方法解决，构造SLR(1)分析表如下:状态ACTIONGOTOabc#AB0S211S3ACCEP2S543R1R1R14S65R4S276R2R2R27S9S88R39R5R1R1R1该SLR(1 )分析表无重定义，因此该文法是SLR(1 )文法，不是LR(0)文法。5.3证明下面文法是LR(1 )文法，但不是SLR(1)文法。ST AaAb|BbBaA*B*解：拓广文法GS :0: STS1: STAaAb2: STBbBa3: ATe4： BTe构造LR(0)项目集规范族:状态项目集转换函数0ST SST AaAbST BbBaAT-BT

24、GO0, S=1GO0, A =2GO0, B=3R3R41STSACCEPT2STA aAbGO2, a =43STB bBaGO3, b=54STAa AbATGO4, A =6R35STBb BaBTGO5, B=7R46STAaA bGO6, b=87STBbB aGO7, a =98STAaAb R19STBbBa R2状态0存在“归约一归约”冲突，且FOLLOW(A) =a,b, FOLLOW(B)= a,b,即 FOLLOW(A) nFOLLOW(B) =a,b0，所以该文法不是SLR(1)文法。构造11?项目集规范族:状态项目集转换函数0ST S, #ST AaAb, #ST

25、 BbBa, #AT，aBT，bGO0, S=1GO0, A =2GO0, B=3R3R41STS，#ACCEPT2STA aAb, #GO2, a =43STB bBa, #GO3, b=54STAaAb, #AT，bGO4, A =6R35STBbBa, #BT，aGO5, B=7R46STAaAb, #GO6, b=87STBbBa, #GO7, a =98STAaAb，#R19STBbBa，#R2LR(1)分析表:5.4考虑以下的文法:ETEE+ETEE*ETa(1) 为这个文法构造LR(1 )项目集规范族。(2) 构造LR(1)分析表。(3) 为这个文法构造LALR(1 )项目集规范

26、族。(4) 构造LALR(1)分析表。(5) 对输入符号串“aa*a+ ”进行LR和LALR(1)分析。解：(1)拓广文法GS:0: STE1: ETEE+2: ETEE*3: ETa构造LR项目集规范族：状态项目集转换函数0ST* E , #GO0,曰=1ET EE+ , a:#GO0,曰=1ET EE* , a:#GO0,曰=1ET a , a:#GO0, a =21STE,#ACCEPTETEE+ , a:#GO1, E=3ETE E* , a:#GO1, E=3ET EE+ , *: +GO1, E=3ET EE* , *: +GO1, E=3ET a , *: +GO1, a =42

27、ETa , a:#R33ETEE + , a:#GO3 , +=5ETEE * , a:#GO3 , *=6ETE E+ , *: +GO3 ,曰=7ETE E* , *: +GO3 ,曰=7ET EE+ , *: +GO3 ,曰=7ET EE* , *: +GO3 ,曰=7ET a , *: +GO3 , a =44ETa , *: +R35ETEE+,a:#R16ETEE* , a:#R27ETEE + , *: +GO7 , +=8ETEE * , *: +GO7 , *=9ETE E+ , *: +GO7 ,曰=7ETE E* , *: +GO7 ,曰=7ET EE+ , *: +GO

28、7 ,曰=7ET EE* , *: +ET a , *: +GO7, E=7GO7, a =48ETEE+,*: +R19ETEE* , *: +R2(2)构造LR(1)分析表状态ACTIONGOT+*a#E0S211S4ACCEP32R3R33S5S6S474R3R35R1R16R2R27S8S9S478R1R19R2R2(3)构造LALR(1)项目集规范族:状态项目集转换函数0ST E , #GO0 , E=1ET EE+ , a:#GO0 , E=1ET EE* , a:#GO0 , E=1E a , a:#GO0 , a =21STE,#ACCEPTETE E+ , a:#GO1,曰=

29、3ETE E* , a:#GO1,曰=3ET EE+ , *: +GO1,曰=3ET EE* , *: +GO1,曰=3ET a , *: +GO1, a =22ETa , a:#:*: +R33ETEE + , a:#:*: +GO3 , +=4ETEE * , a:#:*: +GO3 , *=5ETE E+ , *: +GO3 ,曰=3ETE E* , *: +GO3 ,曰=3ET EE+ , *: +GO3 ,曰=3ET EE* , *: +GO3 ,曰=3ET a , *: +GO3 , a =24ETEE+,a:#:*: +R15ETEE* , a:#:*: +R2(4)构造LALR

30、(1)分析表。状态ACTIONGOT+*a#E0S211S2ACCEP32R3R3R3R33S4S5S234R1R1R1R15R2R2R2R2(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+#R111101#E#ACCEPT对输入符号串“aa*a+”进行LALR(1)分析:步骤状态栈符号栈输入串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+#R111101#E#ACCEPT5.5说明以下的文法是LR(1)文法，但不是LALR(1)文法。

展开阅读全文