编译原理及实现课后习题答案(一).pdf

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

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

2、abcbabcb|(xy)31=122.3 设有文法GS：S：=SS*|SS+|a,写出符号串aa+a*规范推导，并构造语法树。S=SS*=Sa*=SS+a*=Sa+a*=aa+a*2.4 已知文法 GZ：Z：=UO I V I、U：=Z1|1、V：=ZO|O,请写出全部由此文法描述的只含有四个符号的句子。Z=U0=Z10=U010=1010Z=U0=Z10=V110=0110Z=Vl=Z01=U001=1001Z=Vl=Z01=V101=01012.5 已知文法GS：S：=AB A：=aA|e B：=bBc|be,写出该文法描述的语言。A：=aA|e描述的语言：口加王。B：=bBc|be 描

3、述的语言：bncn|n=lL(GS)=anbmcm|n=O,rn=l2.6 已知文法 E：=T I E+T I E-T、T：=F|T*F|T/F、F：=(E)|i,写出该文法的开始符号、终结符号集合VT、非终结符号集合VN。开始符号：EVt=+,(,),i)Vn=E,F,T)2.7 对 2.6题的文法，写出句型T+T*F+i的短语、简单短语以及句柄。短语：T+T*F+i T+T*FTT*F简单短语：i T*FT句柄：T2.8 设有文法GS：S：=S*S|S+S|(S)|a,该文法是二义性文法吗？根据所给文法推导出句子a+a*a,画出了两棵不同的语法树，所以该文法是二义性文法。2.9 写一文法，

4、使其语言是奇正整数集合。A:=1|3|5|7|9|NAN:=0|l|2|3|4|5|6|7|8|92.10 给出语言 anbm|n,mNl 的文法。GS:S:=ABA:=aA|aB:=bB|b3.1 有正则文法 GZ：Z:=Ua|Vb,U:=Zb|b,V:=Za|a,画出该文法的状态图，并检查句子abba是否合法。解：该文法的状态图如下：句子abba合法。3.2 状态图如图3.35所示，S 为开始状态，Z 为终止状态。写出相应图3-35状态图解：左线性文法GZJ:Z:=Ab|bA:=Aa|aV=Z,A,a,bVn=Z,AVt=a,b右线性文法Gqsj：S:=aA|bA:=aA|bV=S,A,a

5、,bV=S,AVt=a,b3.3 构 造下列正则表达式相应的NFA：1(1|0)*|01(1010*11(010)*1)*0解：正则表达式：1(1|0)*|014、图3.36状态图解：DFA:abq0=00,11ql=O,l0511q2=l0图3.37 DFA状态图解:划分ab0,112,4234,51,3,0,53,5,2,4划分ab0,112,42,40,13,53,53,52,4qO=O,l ql=2,4 q2=3,5化简后的DFA：4.1 对下面文法，设计递归下降分析程序。S-aAS|(A),A-Ab|c解：首先将左递归去掉，将规则A f A b|c改 成 Afcb非终结符号S 的分析

6、程序如下：非终结符号A 的分析程序如下:4.2 设有文法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）,在分析过程中，将造成回溯。改写文法可避免回溯：将 规 则

7、B：=Aab代入规则A：=a|Bb得：A：=a|Aabb,再转换成：A：=aabb,可避免回溯。4.3 若有文法如下，设计递归下降分析程序。语句 语句 赋值语句|e 赋值语句 一巾=表达式 表达式 f v 项|表达式+项|表达式 一 项项f 因子|项*因子|项/因子）因子f ID|NUM|（表达式）解：首先，去掉左递归语句f 语句赋值语句|e改为：语句 赋值语句 表达式 一 项|表达式+项|表达式-项 改为：表达式礴 （+|-）项 项 一 因子|项*因子|项/因子）改为：项 V 因子 （*|/）因子 则文法变为:语句 V赋值语句 赋值语句f ID=表达式 表达式-v 项 (+|-)v 项 项T

8、因子 (*|/)V 因子 V 因子 f ID|NUM|(V表达式)非终结符号 因子 的分析程序如下:因子f ID|NUM|(表达式)4.4 有文法 GA：A:=aABe|,B:=Bb|b(1)求每个非终结符号的FOLLOW集。(2)该文法是LL(1)文法吗？(3)构造LL(1)分析表。解：(1)FOLLOW(A)=First(B)U#=b,#FOLLOW(B)=e,b(2)该文法中的规则B:=Bb|b为左递归，因此该文法不是LL(1)文法(3)先消除文法的左递归(转成右递归)，文法变为：A:=aABe|,B:=bB B，:=bB,该文法的LL分析表为:aeb#APOP,PUSH(eBAa)PO

9、PPOPBPOP,PUSH b)B，POPPOP,PUSH(B9b)aPOP,NEXTSYMePOP,NEXTSYMbPOP,NEXTSYM#ACCEPT更常用且简单的LL(1)分析表:aeb#AA-aABeA f A f BB-bB，B，B f B f bB4.5 若有文法A-(A)A|e(1)为非终结符A 构造FIRST集合和FOLLOW集合。(2)说明该文法是LL(1)的文法。解：(1)FIRST(A)=(,e)FOLLOW(A)=),#(2)该文法不含左递归；FIRST(A)A)=(,FIRST(e)=e ,FIRST(A)A)D FIRST(e)=0,且 FOLLOW(A)=),#,

10、FIRST(A)A)0 FOLLOW(A)=,因此，该文法满足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(E9T)E-TE2#E?Ti+i*i+i#POP,PUSH(T9F)T-F T，3#E9T Pi+i*i+i#POP,PUSH(i)F f4#E T il+i*i+l#POP,NEXTSYM5#E T+i*i+i#POPT f 6#E+i*i+i#POP,PUSH(E,T+)Ef+TE

11、7#E9T+i*i+i#POP,NEXTSYM8#E，Ti*i+i#POP,PUSH(TT)TFT9#E T Fi*i+i#POP,PUSH(i)F-i10#E T ii*i+i#POP,NEXTSYM11#E T*i+i#POP,PUSH(TT*)*FT，12#ETF*i+i#POP,NEXTSYM13#E T Fi+i#POP,PUSH Fi14#E T ii+i#POP,NEXTSYM(2)i*(i+i+i)15#E T+i#POPT f e16#E，+i#POP,PUSH(E,T+)E-+TE17#E9T+i#POP,NEXTSYM18#ETi#POP,PUSH(TT)TFT，19#E

12、 T Fi#POP,PUSH(i)Fi20#E T ii#POP,NEXTSYM21#E T#POPT f e22#E,#POPE f e23#ACCEPT4.7 考虑下面简化了的C 声明文法:步骤分析栈余留输入串分析表元素所用产生式1#Ei*(i+i+i)#POP,PUSH(E，T)E T E，2#E，Ti*(i+i+i)#POP,PUSH(T9F)T3#E T Fi*(i+i+i)#POP,PUSH F f i4#E T il*(i+i+i)#POP,NEXTSYM5#E T*(i+i+i)#POP,PUSH(TT*)T，*FT，6#ETF*(i+i+i)#POP,NEXTSYM7#E T

13、 F(i+i+i)#POP,PUSH0E()F-(E)8#E T)E(i+i+i)#POP,NEXTSYM9#E T )Ei+i+i)#POP,PUSH(E,T)E-TE?10#E T)E叮i+i+i)#POP,PUSH(TT)TFT，11#E T)E T Fi+i+i)#POP,PUSH(i)F f i12#E T)E T ii+i+i)#POP,NEXTSYM13#ET)ET+i+i)#POPT 14#E T)E，+i+i)#POP,PUSH(E9T+)Ef+T E，15#E T)E T+i+i)#POP,NEXTSYM16#E T)E，Ti+i)#POP,PUSH(TT)T f FT17

14、#E T)E T Fi+i)#POP,PUSH(i)F-*i18#E T)E T ii+i)#POP,NEXTSYM19#E T)E T+i)#POPT f 20#E T)E，+i)#POP,PUSH T+)E+TE21#ET)ET+i)#POP,NEXTSYM22#E T)E，Ti)#POP,PUSH(TT)TFT23#E T)E T Fi)#POP,PUSH(i)F f24#ET)E Tii)#POP,NEXTSYM25#E T)E，r)#POPT f e26#E T)E，)#POPE f e27#E T)#POP,NEXTSYM28#E T#POPT e29#E，#POPE f e30#

15、ACCEPT 声明语句一V 类型 变量表；类型-*int|float|char 变量表 f ID,变量表|ID(1)在该文法中提取左因子。(2)为所得的文法的非终结符构造FIRST集合和FOLLOW集合。(3)说明所得的文法是LL(1)文法。(4)为所得的文法构造LL(1)分析表。(5)假设有输入串为“char x,y,z；”,写出相对应的LL(1)分析过程。解：(1)规贝k 变量表 一ID,变量表|ID提取公因子如下：变量表 *ID(,变量表|e)增加新的非终结符 变量表1,规则变为：变量表 f ID 变量表1v 变量表l f,变量表|eC 声明文法改变为：声明语句f类型 变量表；类型-in

16、t|float|char 变量表 f l D 变量表1 变 量 表,变量表|e(2)FIRST(声明语句)=FIRST(类型)=int,float,charFIRST(变量表 )=IDFIRST(变量表 1)=,e)FOLLOW(声明语句)=#FOLLOW()=FIRST(变量表)=IDFOLLOW&变量表)=FOLLOW()=；(3)所得文法无左递归，且FIRST(int)D FIRST(float)C l FIRST(char)=0FIRST(,变 量 表 )C l FIRST(e)=)QFOLLOW()=4因此，所得文法为LL(1)文法。(4)所得的文法构造LL(1)分析表如下所示:in

17、tfloatcharID9#V 声明语句POP,PUSH(；变 量 表 x类型刁POP，PUSH(；v 变量 表 类型)POP，PUSH(；变量 表 类型)类型POP,PUSH(int)POP,PUSH(float)POP,PUSH(char)变量表POP,PUSH(ID)变量表 1POPPOP,PUSH(f ；声明语句 一V 类型 变量表；声明语句类型 变量表；类型,v 类型 f intv 类型 f floatv 类型*char 变量表 变 量 表 f 1D 变量表 1 变量表1f eV 变量表1-*,变量表(5)输入串“charx,y,z；”杵对应的LL(1)分析过程如下：步骤分析栈余留输

18、入串分析表元素所用产生式1#声明语句char x,y,z；#POP,PUSH(；变量表x 类型,)声明语句 f f char3#;变 量 表 char x,y,z；#POP,charNEXTSYM4#；V 变量表x,y,z；#POP,PUSH（ID）变量表 f ID5#;v 变量表1Xx,y,z；#POP,NEXTSYM6#;变量表1，y,z；#POP,PUSH（变 量表，）y z；#POP,PUSH（ID）变量表变量表19#；变量表lyy,z；#POP,NEXTSYM10#5 V 变量表1，z；#POP,PUSH（,v 变量表11#;变量表，z；#POP,NEXTSYM12#；V 变量表z；

19、#POP,PUSH（ID）变量表 f ID13#；V 变量表1Zz；#POP,NEXTSYM14#;V 变量表1;#POPb B a3：B-a Ac4：B f a5：B f a Ab构造L R(O)项目集规范族:状态项目集转换函数0S AG 00,A=lA f AbG 00,A=lA f b B aG 00,b =21S f A AC C E P TAA bG 0l,b =32A f b B aG O 2,B =4B f a AcG O 2,a =5B aG O 2,a =5B f a AbG O 2,a =53A-Ab R I4Ab B aG O 4,a =65B a -AcG O 5,A

20、=7B f a R 4B f a AbG O 5,A =7A-AbG O 5,A =7A b B aG O 5,b =26A-*b B a R 27B f a A,cG O 7,c =8B f a A bG O 7,b =9A-A-bG O 7,b =98B a Ac R 39B f a Ab R 5A f Ab R I状 态 5 存 在“归约一移进”冲突，状态9 存 在“归约一归约”冲突，因此该文法不是L R(O)文法。状态5：F O L L O W(B)=a ,因此，F O L L O W(B)D b =L状态9：F O L L O W (B)=a ,F O L L O W (A)=#,b

21、,c ,因此 F O L L O W (B)D F O L L O W (A)=状态5 和状态9 的冲突均可用S L R (1)方法解决，构造S L R (1)分析表如下：状态AC T I O NG O T Oabc#AB0S 211S 3AC C E P T2S 543R IR IR I该 SLR(1)分析表无重定义，因此该文法是SLR(1)文法，不是LR(O)文法。4S65R4S276R2R2R27S9S88R39R5RIRIRI5.3 证明下面文法是LR 文法，但不是SLR(l)文法。S-*AaAb|BbBaA f eB f e解:拓广文法G S ：0：S f S1：S-AaAb2：S-

22、*BbBa3：A f e4：B f e构造LR(0)项目集规范族:状态项目集转换函数0S f sS f AaAbS f BbBaA-B f G00,S=lG00,A=2G00,B=3R3R41S-S ACCEPT2SA aAbGO 2,a=43S f B bBaGO3,b=54S f Aa AbA f GO4,A=6R35S f Bb BaB G05,B=7R46SAaA bGO6,b=87S-*BbB aG O 7,a=98S f AaAb RI9S f BbBa R2状态 0 存在“归约一归约”冲突，且 FOLLOW (A)=a,b,FOLLOW (B)=a,b ,即 FOLLOW (A)

23、A FOLLOW(B)=a,b W，所以该文法不是SLR(1)文法。构造LR项目集规范族：状态项目集转换函数LR分析表:0S f S,#S f AaAb,#S-*BbBa,#A f,aB f ,bG00,S=lG00,A=2GOO,B=3R3R41S-S，#ACCEPT2S-A aAb,#GO 2,a=43S-B bBa,#GO3,b=54S-Aa Ab,#A f,bG04,A=6R35SBb Ba,#B f,aGO5,B=7R46S-A aA b,#G06,b=87S-BbB a,#GO 7,a=98S f AaAb,#RI9S f BbBa,#R2分析表无重定义，说明该文法是LR(1)文法

24、，不是SLR(1)文法。状态ACTIONGOTOab#SAB0R3R41231ACCEPT2S43S54R365R476S87S98RI9R25.4考虑以下的文法：E-*EE+E f EE*E fa(1)为这个文法构造LR(1)项目集规范族。(2)构造LR分析表。(3)为这个文法构造LALR(l)项目集规范族。(4)构造LALR(l)分析表。(5)对输入符号串“aa*a+”进行LR 和LALR(l)分析。解：(1)拓广文法GS：0：S-*E1：EfEE+2：E-EE*3：E f a构造LR项目集规范族:状态项目集转换函数0S一 E,#G00,E=lE f *EE+,a:#G00,E=lE f

25、EE*,a:#G00,E=lE f a,a:#G00,a=21S E,#ACCEPTE f E E+,a:#GO1,E=3EE E*,a:#GO1,E=3E f EE+,*：+GO1,E=3E f EE*,*:+GO1,E=3E-a,*:+G0l,a=42E f a ,a:#R33E-EE +,a:#GO 3,+=5E f EE *,a:#GO3,*=6E f E E+,*:+GO3,E=7EE E*,*:+GO3,E=7E f EE+,*:+GO3,E=7E EE*,*:+GO3,E=7E f a,*:+GO3,a=44E f a ,*:+R35E fE E+-,a:#RI6E f EE*,

26、a:#R27E-EE +,*:+GO 7,+=8E f EE *,*:+GO7,*=9E f E E+,*:+GO7,E=7E-*E E*,*:+GO7,E=7E EE4-,*:+GO7,E=7E-EE*,*:+GO7,E=7E f a,*:+GO7,a=48E-*EE+,*:+RI9E f EE*,*:+R2(2)构造LR 分析表状态ACTIONGOTO+*a#E0S211S4ACCEPT32R3R33S5S6S474R3R35R1R16R2R27S8S9S478R1R19R2R2(3)构造LALR(l)项目集规范族:状态项目集转换函数0S f E,#E f -EE4-,a:#E f EE*

27、,a:#E f a,a:#G00,E=lG00,E=lG00,E=lG00,a=21SE,#E EE+,a:#E f E E*,a:#E f EE+,*：+E f EE*,*:+E-a,*:+ACCEPTGO1,E=3GO1,E=3GO1,E=3GO1,E=3GO1,a=22E f a ,a:#:*：+R33E-EE +,a:#:*:+E-EE *,a:#:*:+E-E E+,*:+EE E*,*:+E-EE+,*:+E-*EE*,*:+E-a,*:+GO 3,+=4G03,*=5GO 3,E=3GO3,E=3GO3,E=3G03,E=3GO 3,a=24E-E E+,a:#:*:+RI5E-

28、EE*,a:#:*:+R2(4)构造LALR(l)分析表。状态ACTIONGOTO+*a#E0S211S2ACCEPT32R3R3R3R33S4S5S234RIRIRIRI5R2R2R2R2(5)对输入符号串“aa*a+进行LR分析:步骤状态栈符号栈输入串ACTIONGOTO10#aa*a+#S2202#aa*a+#R 31301#Ea*a+#S 44014#E a*a+#R 335013#E E*a+#S 660136S E E*a+#R 21701#Ea+t tS 48014#E a+#R 339013#E E+#S 5100135#E E+#R I11101#E#AC C E P T对输

29、入符号串“a a*a+”进行L AL R 分析:步骤状态栈符号栈输入串AC T I O N G O T O10#a a*a+#S 2202#aa*a+#R 31301#Ea*a+#S 24012#E a*a+#R 335013#E E*a+#S 560135S E E*a+#R 21701#Ea+#S 28012#E a+#R 339013S E E+#S 4100134#E E+#R I11101#E#AC C E P T5.5 说明以下的文法是L R 文法，但不是L AL R 文法。S-a Ad|b B d|a B e|b AeA-*cB f c解：拓广文法：0：S f S1：S-*-a

30、Ad2：S-b B d3：S f a B e4：S b Ae5：A-*c6：B f c构造L R 项目集规范族状态项目集转换函数0S 一 s,#S f a Ad,#G 00,S =lG 00,a =2S f bBd,#G00,b=3S f aBe,#G00,a=2S f bAe,#G00,b=31S,#ACCEPT2S-a Ad,#G02,A=4S f a Be,#GO2,B=5A f c,dG02,c=6B一 c,eGO2,c=63S-b Bd,#GO3,B=7S-*b Ae,#GO3,A=8A c,eG03,c=9B f c,dGO3,c=94S-aA d,#G O 4,d=105S f

31、aB e,#GO5,e=ll6A f c ,dR5B f c ,eR67S-*bB d,#G O 7,d=128SbA e,#G O 8,e=139A-*c ,eR5Bc ,dR610S f aAd ,#RI11S f aBe ,#R312S-bBd ,#R213S-*bAe ,#R4构造LR分析表:状态ACTIONGOTOabcde#SAB0S2S311ACCEPT2S6453S9874S105Sil6R5R67S128S139R6R510RI11R312R213R4同核项目集合并，构造LALR(l)项目集规范族:状态项目集转换函数0S f S,#G00,S=lS f aAd,#G00,a=

32、2S f bBd,#G00,b=3S f aBe,#G00,a=2S f bAe,#G00,b=31S-S，#ACCEPT2S-a Ad,#GO2,A=4S f a Be,#G0E2,B=5A c,dGO2,c=6B-*c,eGO2,c=63S-b Bd,#GO3,B=7S f b Ae,#GO3,A=8A f c,eG03,c=6B f c,dGO3,c=64S-aA d,#GO4,d=95S f aB e,#G O 5,e=106A-*c ,d:eR5B f c ,d:eR67S-*bB d,#GO7,d=ll8S f bA e,#GO 8,e=129S f aAd ,#RI10S-aBe ,#R311S-bBd ,#R212S-*bAe ,#R4构造LALR(l)分析表:状态ACTIONGOTOabcde#SAB0S2S311ACCEPT2S6453S9874S105Sil6R5/R6R5/R67S128S139RI10R311R212R4从 LR(1)分析表可以看出，分析表无重定义，因此该文法是LR(1)文法。从 LALR(l)分析表可以看出，分析表ACTION6,d和 ACTION6,e存在重定义，因此该文法不是LALR(l)文法。