编译原理及实现课后习题答案孙悦红

1、2.1 设字母表a=a，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及a+和a*.x0=(aaa)0= | x0|=0 xx=aaaaaa |xx|=6x5=aaaaaaaaaaaaaaa | x5|=15a+ =a1a2 . a n=a,aa,aaa,aaaa,aaaaa a* = a0 a1 a2 . a n =,a,aa,aaa,aaaa,aaaaa 2.2 令=a，b，c，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3xy=abcb |xy|=4xyz=abcbaab |xyz|=7(xy)3=(abcb)3 =abcbabcb

2、abcb | (xy)3 |=122.3 设有文法gs：s=ss*|ss+|a，写出符号串aa+a*规范推导，并构造语法树。s => ss* => sa* => ss+a* => sa+a* => aa+a*sss*ss+aaa2.4 已知文法gz：z=u0v1 、 u=z11 、 v=z00 ,请写出全部由此文法描述的只含有四个符号的句子。z=>u0=>z10=>u010=>1010z=>u0=>z10=>v110=>0110z=>v1=>z01=>u001=>1001z=>v1=&g

3、t;z01=>v101=>01012.5 已知文法gs： s=ab a=aa b=bbcbc , 写出该文法描述的语言。a=aa描述的语言: an|n>=0b=bbcbc描述的语言：bncn|n>=1l(gs)=anbmcm|n>=0,m>=12.6 已知文法e=te+te-t 、 t=ft*ft/f 、 f=(e)i，写出该文法的开始符号、终结符号集合vt、非终结符号集合vn。开始符号：evt=+, - , * , / ,（ , ）, ivn=e , f , tete+fte+ift*t2.7 对2.6题的文法，写出句型t+t*f+i的短语、简单短语以及句

4、柄。短语：t+t*f+i t+t*f i i t t*f简单短语：i t*f t句柄：t2.8 设有文法gs：s=s*s|s+s|(s)|a，该文法是二义性文法吗？sss*s+saaasss+s*saaa根据所给文法推导出句子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,m1的文法。 gs: s:=ab a:=aa|a b:=bb|b3.1 有正则文法gz：z:=ua|vb，u:=zb|b，v:=za|a ，画出该文法的状态图，并检查

5、句子abba是否合法。解：该文法的状态图如下：suvzaaabbb句子abba合法。3.2 状态图如图3.35所示，s为开始状态，z为终止状态。写出相应的正则文法以及v，vn和vt。sazabab图3-35状态图 解： 左线性文法gz: 右线性文法gs:z:=ab|bs:=aa|b a:=aa|aa:=aa|bv=z,a,a,bv=s,a,a,bvn=z,avn=s,avt=a,bvt=a,b3.3 构造下列正则表达式相应的nfa： 1(1|0)*|0 1(1010*|1(010)*1)*0解：正则表达式：1(1|0)*|01、sz1(1|0)*|02、sz1(1|0)*03、saz01014

6、、q0q1010,1q2正则表达式：1(1010*|1(010)*1)*00135462101010780101101a,baa3.4 将图3.36的nfa m确定化图3.36 状态图 解：abq0=00,11q1=0,10,11q2=10dfa:q0q1q2ababa3.5 将图3.37的dfa化简。014253aaaaaabbbbbb图3.37 dfa状态图 解：划分ab0,112,42,3,4,51,0,3,53,5,2,4划分ab0,112,42,40,13,53,53,52,4q0=0,1q1=2,4q2=3,5化简后的dfa：q0q1q2baaabb4.1 对下面文法，设计递归下降

7、分析程序。 saas|(a) , aab|c解：首先将左递归去掉，将规则aab|c 改成 acb非终结符号s的分析程序如下：非终结符号a的分析程序如下：过程s inputsym=ainputsym=下一个符号yninputsym=(inputsym=下一个符号yinputsym=)inputsym=下一个符号ynn出口错误错误过程a过程s过程a过程a inputsym=cinputsym=下一个符号yinputsym=bn错误inputsym=下一个符号y出口n4.2 设有文法gz： z=(a) , a=a|bb , b=aab若采用递归下降分析方法，对此文法来说，在分析过程中，能否避免回溯？

8、为什么？解：若采用递归下降分析方法，对此文法来说，在分析过程中不能避免回朔。因为规则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 若有文法如下，设计递归下降分析程序。 <语句><语句><赋值

9、语句>| <赋值语句>id=<表达式> <表达式><项>|<表达式><项>|<表达式><项> <项><因子>|<项>*<因子>|<项>/<因子> <因子>id|num|(<表达式>)解：首先，去掉左递归<语句><语句><赋值语句>|改为： <语句><赋值语句><表达式><项> | <表达式> + <

10、项> | <表达式> - <项> 改为：<表达式><项>（+ | -）<项><项><因子> | <项> * <因子> | <项> / <因子> 改为：<项><因子>（* | /）<因子>则文法变为：<语句><赋值语句> <赋值语句>id=<表达式> <表达式><项>（+ | -）<项> <项><因子>（* | /）&

11、lt;因子> <因子>id|num|(<表达式>)<语句><赋值语句>非终结符号 <语句> 的分析程序如下：first(<赋值语句>)=id语句inputsym=idny赋值语句出口<赋值语句>id=<表达式>非终结符号 <赋值语句> 的分析程序如下：赋值语句inputsym=id错误ninputsym=下一个符号inputsym=错误ninputsym=下一个符号y表达式出口<表达式><项>（+ | -）<项>非终结符号 <表达式>

12、 的分析程序如下：表达式inputsym=+ninputsym=-inputsym=下一个符号y出口项ny<项><因子>（* | /）<因子>非终结符号 <项> 的分析程序如下：项inputsym=*ninputsym=/inputsym=下一个符号y出口因子ny项<因子>id|num|(<表达式>)非终结符号 <因子> 的分析程序如下：复值语句的分析程序因子inputsym=idy出口inputsym=numinputsym=下一个符号nyninputsym=(inputsym=下一个符号y表达式inputs

13、ym=)错误ny错误n4.4 有文法ga：a:=aabe|，b:=bb|b（1）求每个非终结符号的follow集。（2）该文法是ll(1)文法吗？（3）构造ll(1)分析表。解：（1） follow(a)=first(b)#=b,# follow(b)=e,b（2） 该文法中的规则b:=bb|b为左递归，因此该文法不是ll(1)文法（3） 先消除文法的左递归（转成右递归），文法变为：a:=aabe|，b:=bb，b=bb|，该文法的ll(1)分析表为：aeb#apop ，push(ebaa)poppopbpop ，push(bb)bpoppop ，push(bb)apop,nextsymepo

14、p,nextsymbpop,nextsym#accept更常用且简单的ll(1)分析表：aeb#aaaabeaabbbbbbbbb4.5 若有文法a(a)a|（1）为非终结符a构造first集合和follow集合。（2）说明该文法是ll(1)的文法。解：（1）first(a)(, follow(a)，#（2）该文法不含左递归；first（(a)a）=(，first（）=，first（(a)a）first（）=，且follow(a)，#，first（(a)a） follow(a) =，因此，该文法满足ll(1)文法的条件，是ll(1)文法。4.6 利用分析表4-1，识别以下算术表达式，请写出分析

15、过程。（1）i+i*i+i（2）i*(i+i+i)解：（1）i+i*i+i步骤分析栈余留输入串分析表元素所用产生式1#ei+i*i+i#pop,push(et)ete2#eti+i*i+i#pop,push(tf)tft3#etfi+i*i+i#pop,push(i)fi4#etii+i*i+i#pop,nextsym5#et+i*i+i#popt6#e+i*i+i#pop,push(et+)e+te7#et+i*i+i#pop,nextsym8#eti*i+i#pop,push(tf)tft9#etfi*i+i#pop,push(i)fi10#etii*i+i#pop,nextsym11#e

16、t*i+i#pop,push(tf*)t*ft12#etf*i+i#pop,nextsym13#etfi+i#pop,push(i)fi14#etii+i#pop,nextsym15#et+i#popt16#e+i#pop,push(et+)e+te17#et+i#pop,nextsym18#eti#pop,push(tf)tft19#etfi#pop,push(i)fi20#etii#pop,nextsym21#et#popt22#e#pope23#accept（2）i*(i+i+i)步骤分析栈余留输入串分析表元素所用产生式1#ei*(i+i+i)#pop,push(et)ete2#eti*

17、(i+i+i)#pop,push(tf)tft3#etfi*(i+i+i)#pop,push(i)fi4#etii*(i+i+i)#pop,nextsym5#et*(i+i+i)#pop,push(tf*)t*ft6#etf*(i+i+i)#pop,nextsym7#etf(i+i+i)#pop, push()e()f(e)8#et )e(i+i+i)#pop,nextsym9#et )ei+i+i)#pop,push(et)ete10#et ) eti+i+i)#pop,push(tf)tft11#et ) e tfi+i+i)#pop,push(i)fi12#et ) e tii+i+i)

18、#pop,nextsym13#et ) e t+i+i)#popt14#et ) e +i+i)#pop,push(et+)e+te15#et ) et+i+i)#pop,nextsym16#et ) eti+i)#pop,push(tf)tft17#et ) etfi+i)#pop,push(i)fi18#et ) etii+i)#pop,nextsym19#et ) et+i)#popt20#et ) e+i)#pop,push(et+)e+te21#et ) e t+i)#pop,nextsym22#et ) e ti)#pop,push(tf)tft23#et ) e tfi)#pop

19、,push(i)fi24#et ) e tii)#pop,nextsym25#et ) e t)#popt26#et ) e)#pope27#et )#pop,nextsym28#et #popt29#e#pope30#accept4.7 考虑下面简化了的c声明文法：<声明语句><类型><变量表>；<类型>int|float|char<变量表>id,<变量表>|id（1） 在该文法中提取左因子。（2） 为所得的文法的非终结符构造first集合和follow集合。（3） 说明所得的文法是ll(1)文法。（4） 为所得的文法构

20、造ll(1)分析表。（5） 假设有输入串为“char x，y，z；”，写出相对应的ll(1)分析过程。解：（1） 规则<变量表>id,<变量表>|id提取公因子如下：<变量表>id（,<变量表>|）增加新的非终结符<变量表1>，规则变为：<变量表>id<变量表1><变量表1>，<变量表>| c声明文法改变为： <声明语句><类型><变量表>；<类型>int|float|char<变量表>id<变量表1><变量表

21、1>，<变量表>|（2） first(<声明语句>)first(<类型>)int，float，charfirst(<变量表>)idfirst(<变量表1>)，follow(<声明语句>)#follow(<类型>)first(<变量表>)idfollow(<变量表>)follow(<变量表1>)；（3） 所得文法无左递归，且first（int）first（float）first（char）first（，<变量表>）first（）first（，<变量表&g

22、t;）follow(<变量表1>)因此，所得文法为ll(1)文法。（4） 所得的文法构造ll(1)分析表如下所示：；intfloatcharid，#<声明语句>pop ，push(；<变量表><类型>)pop ，push(；<变量表><类型>)pop ，push(；<变量表><类型>)<类型>pop ，push(int)pop ，push(float)pop ，push(char)<变量表>pop ，push(<变量表1>id)<变量表1>poppop

23、 ，push(<变量表>，)；pop,nextsymintpop,nextsymfloatpop,nextsymcharpop,nextsymidpop,nextsym，pop,nextsym#accept更常用且简单的ll(1)分析表：；intfloatcharid，#<声明语句><声明语句><类型><变量表>；<声明语句><类型><变量表>；<声明语句><类型><变量表>；<类型><类型>int<类型>float<类型

24、>char<变量表><变量表>id<变量表1><变量表1><变量表1><变量表1>,<变量表>（5） 输入串“char x，y，z；”相对应的ll(1)分析过程如下：步骤分析栈余留输入串分析表元素所用产生式1#<声明语句>char x，y，z；#pop ，push(；<变量表><类型>)<声明语句><类型><变量表>；2#；<变量表><类型>char x，y，z；#pop ，push(char)<类型&g

25、t;char3#；<变量表> charchar x，y，z；#pop,nextsym4#；<变量表>x，y，z；#pop ，push(<变量表1>id)<变量表>id<变量表1>5#；<变量表1>xx，y，z；#pop,nextsym6#；<变量表1>，y，z；#pop ，push(<变量表>，)<变量表1>，<变量表>7#；<变量表>，y，z；#pop,nextsym8#；<变量表>y，z；#pop ，push(<变量表1>id)<

26、变量表>id<变量表1>9#；<变量表1>yy，z；#pop,nextsym10#；<变量表1>，z；#pop ，push(<变量表>，)<变量表1>，<变量表>11#；<变量表>，z；#pop,nextsym12#；<变量表>z；#pop ，push(<变量表1>id)<变量表>id<变量表1>13#；<变量表1>zz；#pop,nextsym14#；<变量表1>；#pop<变量表1>15#；#pop,nextsym16

27、#accept5.1 考虑以下的文法：ss;t|tta（1） 为这个文法构造lr(0)的项目集规范族。（2） 这个文法是不是lr(0)文法？如果是，则构造lr(0)分析表。（3） 对输入串“a;a”进行分析。解：（1）拓广文法gs： 0：ss 1：ss;t 2：st 3：ta构造lr(0)项目集规范族状态项目集转换函数0s·ss·s;ts·tt·ago0，s1go0，s1go0，t2go0，a31ss·ss·tacceptgo1，;42st·r23ta·r34ss;·tt·ago4，t5go4，

28、a35ss;t·r1（2）该文法不存在“归约归约”和“归约移进”冲突，因此是lr(0)文法。lr(0)分析表如下：状态actiongoto；a#st0s3121s4accept2r2r2r23r3r3r34s355r1r1r1（3）对输入串“a;a”进行分析如下：步骤状态栈符号栈输入符号栈actiongoto00#a;a#s3103#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)文法。saaab|bbabaac|a|aab

29、解：文法gs：0：sa1：aab2：abba3：baac4：ba5：baab构造lr(0)项目集规范族：状态项目集转换函数0s·aa·aba·bbago0，a1go0，a1go0，b21sa·aa·bacceptgo1，b32ab·bab·aacb·ab·aabgo2，b4go2，a5go2，a5go2，a53aab·r14abb·ago4，a65ba·acba·ba·aba·aba·bbago5，a7r4go5，a7go5，a7go5

30、，b26abba·r27baa·cbaa·baa·bgo7，c8go7，b9go7，b98baac·r39baab·aab·r5r1状态5存在“归约移进”冲突，状态9存在“归约归约”冲突，因此该文法不是lr(0)文法。状态5：follow(b)a，因此，follow(b)b状态9：follow(b)a，follow(a)#，b，c，因此follow(b)follow(a)状态5和状态9的冲突均可用slr(1)方法解决，构造slr(1)分析表如下：状态actiongotoabc#ab0s211s3accept2s543r1r1

31、r14s65r4s276r2r2r27s9s88r39r5r1r1r1该slr(1)分析表无重定义，因此该文法是slr(1)文法，不是lr(0)文法。5.3 证明下面文法是lr(1)文法，但不是slr(1)文法。saaab|bbbaab解：拓广文法gs：0：ss1：saaab2：sbbba3：a4：b构造lr(0)项目集规范族：状态项目集转换函数0s·ss·aaabs·bbbaa·b·go0，s1go0，a2go0，b3r3r41ss·accept2sa·aabgo2，a43sb·bbago3，b54saa

32、3;aba·go4，a6r35sbb·bab·go5，b7r46saaa·bgo6，b87sbbb·ago7，a98saaab·r19sbbba·r2状态0存在“归约归约”冲突，且follow(a) a,b，follow(b)a,b，即follow(a)follow(b)a,b，所以该文法不是slr(1)文法。构造lr(1)项目集规范族：状态项目集转换函数0s·s，#s·aaab，#s·bbba，#a·，ab·，bgo0，s1go0，a2go0，b3r3r41ss·

33、，#accept2sa·aab，#go2，a43sb·bba，#go3，b54saa·ab，#a·，bgo4，a6r35sbb·ba，#b·，ago5，b7r46saaa·b，#go6，b87sbbb·a，#go7，a98saaab·，#r19sbbba·，#r2lr(1)分析表：状态actiongotoab#sab0r3r41231accept2s43s54r365r476s87s98r19r2分析表无重定义，说明该文法是lr(1)文法，不是slr(1)文法。5.4 考虑以下的文法：eeeee

34、e*ea（1）为这个文法构造lr(1)项目集规范族。（2）构造lr(1)分析表。（3）为这个文法构造lalr(1)项目集规范族。（4）构造lalr(1)分析表。（5）对输入符号串“aa*a+”进行lr(1)和lalr(1)分析。解：（1）拓广文法gs：0：se1：eee2：eee*3：ea构造lr(1)项目集规范族：状态项目集转换函数0s·e ，#e·ee ，a:#e·ee* ，a:#e·a ，a:#go0，e1go0，e1go0，e1go0，a21se· ，#ee·e ，a:#ee·e* ，a:#e·ee ，*:

35、+e·ee* ，*:+e·a ，*:+acceptgo1，e3go1，e3go1，e3go1，e3go1，a42ea· ，a:#r33eee· ，a:#eee·* ，a:#ee·e ，*:+ee·e* ，*:+e·ee ，*:+e·ee* ，*:+e·a ，*:+go3，5go3，*6go3，e7go3，e7go3，e7go3，e7go3，a44ea· ，*:+r35eee· ，a:#r16eee*· ，a:#r27eee· ，*:+eee·*

36、，*:+ee·e ，*:+ee·e* ，*:+e·ee ，*:+e·ee* ，*:+e·a ，*:+go7，+8go7，*9go7，e7go7，e7go7，e7go7，e7go7，a48eee· ，*:+r19eee*· ，*:+r2（2）构造lr(1)分析表状态actiongoto*a#e0s211s4accept32r3r33s5s6s474r3r35r1r16r2r27s8s9s478r1r19r2r2（3）构造lalr(1)项目集规范族:状态项目集转换函数0s·e ，#e·ee ，a:#e

37、3;ee* ，a:#e·a ，a:#go0，e1go0，e1go0，e1go0，a21se· ，#ee·e ，a:#ee·e* ，a:#e·ee ，*:+e·ee* ，*:+e·a ，*:+acceptgo1，e3go1，e3go1，e3go1，e3go1，a22ea· ，a:#:*:+r33eee· ，a:#:*:+eee·* ，a:#:*:+ee·e ，*:+ee·e* ，*:+e·ee ，*:+e·ee* ，*:+e·a ，*:+go3，4

38、go3，*5go3，e3go3，e3go3，e3go3，e3go3，a24eee· ，a:#:*:+r15eee*· ，a:#:*:+r2（4）构造lalr(1)分析表。状态actiongoto*a#e0s211s2accept32r3r3r3r33s4s5s234r1r1r1r15r2r2r2r2（5）对输入符号串“aa*a+”进行lr(1)分析:步骤状态栈符号栈输入串actiongoto10#aa*a+#s2202#aa*a+#r3 1301#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)文法