《编译原理及实现课后习题答案》由会员分享，可在线阅读，更多相关《编译原理及实现课后习题答案（33页珍藏版）》请在金锄头文库上搜索。
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
2、 |xy|=4xyz=abcbaab |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*SSS*SS+aaa2.4 已知文法已知文法 GZ：Z=U0V1 、 U=Z11 、 V=Z00 ,请写出全部由此请写出全部由此文法描述的只含有四个符号的句子。文法描述的只含有四个符号的句子。Z=U0=Z10=U010=1010Z=U0=Z10=V110=0
3、110Z=V1=Z01=U001=1001Z=V1=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=+, - , * , / ,（
4、 , ）, iVn=E , F , T2.7 对对 2.6 题的文法，写出句型题的文法，写出句型 T+T*F+i 的短语、简单短语以及句柄。的短语、简单短语以及句柄。短语：短语：T+T*F+i T+T*Fi iT T*F简单短语：简单短语：i T*FT句柄：句柄：T2.8 设有文法设有文法 GS：S=S*S|S+S|(S)|a，该文法是二义性文法吗？，该文法是二义性文法吗？ETE+FTE+iFT*TSSS*S+SaaaSSS+S*Saaa根据所给文法推导出句子根据所给文法推导出句子 a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。，画出了两棵不同的语法树，所以该文法是二义性文法。2
5、.9 写一文法，使其语言是奇正整数集合。写一文法，使其语言是奇正整数集合。 A:=1|3|5|7|9|NAN:=0|1|2|3|4|5|6|7|8|92.10 给出语言给出语言anbm|n,m1的文法。的文法。 GS: S:=ABA:=aA|aB:=bB|b3.1 有正则文法有正则文法 GZ：Z:=Ua|Vb，U:=Zb|b，V:=Za|a ，画出该文法的状态图，并检查，画出该文法的状态图，并检查 句子句子 abba 是否合法。是否合法。 解：该文法的状态图如下：解：该文法的状态图如下：SUVZaaabbb句子句子 abba 合法。合法。3.2 状态图如图状态图如图 3.35 所示，所示，S
6、为开始状态，为开始状态，Z 为终止状态。写出相应的正则文法以及为终止状态。写出相应的正则文法以及 V，Vn和和 Vt。SAZabab图3-35状态图 解：解： 左线性文法左线性文法 GZ: 右线性文法右线性文法 GS: Z:=Ab|bS:=aA|bA:=Aa|aA:=aA|b V=Z,A,a,bV=S,A,a,b Vn=Z,AVn=S,A Vt=a,bVt=a,b 3.3 构造下列正则表达式相应的构造下列正则表达式相应的 NFA：1(1|0)*|0 1(1010*|1(010)*1)*0 解：正则表达式：解：正则表达式：1(1|0)*|0 1、SZ1(1|0)*|02、SZ 1(1|0)*03
7、、SAZ01014、q0q1010,1 q2正则表达式：正则表达式：1(1010*|1(010)*1)*0013546210 10 1078 01011 3.4将图将图 3.36 的的 NFA M 确定化确定化图3.36 状态图 解：解：abq0=00,11q1=0,10,1101a,baaq2=10DFA:q0q1q2ababa3.5将图将图 3.37 的的 DFA 化简。化简。014253aaaaaabbbb bb图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,1q
8、1=2,4q2=3,5 化简后的化简后的 DFA：q0q1q2b a aabb4.1 对下面文法，设计递归下降分析程序。对下面文法，设计递归下降分析程序。 SaAS|(A) , AAb|c解：解：首先将左递归去掉，将规则首先将左递归去掉，将规则 AAAb|c 改成改成 Acb 非终结符号非终结符号 S 的分析程序如下：的分析程序如下：过程过程 S INPUTSYM=a INPUTSYM=下一个符号下一个符号YNINPUTSYM=(INPUTSYM=下一个符号下一个符号YINPUTSYM=)INPUTSYM=下一个符号下一个符号YNN出口出口错误错误错误错误过程过程 A过程过程 S过程过程 A非
9、终结符号非终结符号 A 的分析程序如下：的分析程序如下：过程 A INPUTSYM=cINPUTSYM=下一个符号YINPUTSYM=bN 错误INPUTSYM=下一个符号Y出口N4.2 设有文法设有文法 GZ： Z=(A) , A=a|Bb , B=Aab 若采用递归下降分析方法，对此文法来说，在分析过程中，能否避免回溯？为什么？若采用递归下降分析方法，对此文法来说，在分析过程中，能否避免回溯？为什么？解：若采用递归下降分析方法，对此文法来说，在分析过程中不能避免回朔。因为规则解：若采用递归下降分析方法，对此文法来说，在分析过程中不能避免回朔。因为规则A=a|Bb 和规则和规则 B=Aab
10、构成了间接左递归，不满足实现没有回溯的递归下降分析方法构成了间接左递归，不满足实现没有回溯的递归下降分析方法 的条件（的条件（1） （书（书 P67） ，且规则，且规则 A: := a|Bb，FIRST(a)=a，FIRST(Bb)=a，即此规则候，即此规则候 选式的首符号集有相交，不满足实现没有回溯的递归下降分析方法的条件（选式的首符号集有相交，不满足实现没有回溯的递归下降分析方法的条件（2） （书（书 P67） ， 在分析过程中，将造成回溯。在分析过程中，将造成回溯。 改写文法可避免回溯：改写文法可避免回溯： 将规则将规则 B=Aab 代入规则代入规则 A=a|Bb 得：得：A=a|Aab
11、b，再转换成：，再转换成：A=aabb，可避免，可避免 回溯。回溯。4.3 若有文法如下，设计递归下降分析程序。若有文法如下，设计递归下降分析程序。 | ID= | |*|/ ID|NUM|()解：首先，去掉左递归解：首先，去掉左递归 | 改为：改为： | + | - 改为：改为： （+ | -） | * | / 改为：改为： （* | /）则文法变为：则文法变为： ID= （+ | -） （* | /） ID|NUM|()非终结符号非终结符号 的分析程序如下：的分析程序如下：语句INPUTSYM=IDNY赋值语句出口非终结符号非终结符号 的分析程序如下：的分析程序如下：FIRST()=IDI
12、D=赋值语句INPUTSYM=ID错误NINPUTSYM=下一个符号INPUTSYM=错误NINPUTSYM=下一个符号Y表达式出口非终结符号非终结符号 的分析程序如下：的分析程序如下：表达式INPUTSYM=+NINPUTSYM=-INPUTSYM=下一个符号Y出口项NY（+ | -）非终结符号非终结符号 的分析程序如下：的分析程序如下：项INPUTSYM=*NINPUTSYM=/INPUTSYM=下一个符号Y出口因子NY项非终结符号非终结符号 的分析程序如下：的分析程序如下：复值语句的分析程序（* | /）ID|NUM|()因子INPUTSYM=IDY出口INPUTSYM=NUM INPU
13、TSYM=下一个符号NYNINPUTSYM=(INPUTSYM=下一个符号Y表达式INPUTSYM=)错误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）先消除文法的左递归（转成右递归）先
14、消除文法的左递归（转成右递归） ，文法变为：，文法变为：A:=aABe|，B:=bB，B=bB |，该文法的，该文法的 LL(1)分析表为：分析表为：aeb#APOP ， PUSH(eBAa)POPPOPBPOP ， PUSH(Bb)BPOPPOP ， PUSH(Bb)aPOP, NEXTSYMePOP, NEXTSYMbPOP, NEXTSYM#ACCEPT更常用且简单的更常用且简单的 LL(1)分析表：分析表：aeb#AAAaABeAAAA BBbB BBBBbB4.5 若有文法若有文法 A(A)A| （1）为非终结符）为非终结符 A 构造构造 FIRST 集合和集合和 FOLLOW 集合。集合。 （2）说明该文法是）说明该文法是 LL(1)的文法。的文法。 解：解： （1）FIR
