编译原理及实现课后习题答案绝杀版

2.1设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及A+和A*.x0=(aaa)0=ε|x0|=0xx=aaaaaa|xx|=6x5=aaaaaaaaaaaaaaa|x5|=15A+=A1∪A2∪….∪An∪…={a,aa,aaa,aaaa,aaaaa…}A*=A0∪A1∪A2∪….∪An∪…={ε,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=abcbabcbabcb|(xy)3|=122.3设有文法G[S]：S∷=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语法树。S=SS*=Sa*=SS+a*=Sa+a*=aa+a*2.4已知文法G[Z]：Z∷=U0∣V1、U∷=Z1∣1、V∷=Z0∣0,请写出全部由此文法描述的只含有四个符号的句子。Z=U0=Z10=U010=1010Z=U0=Z10=V110=0110Z=V1=Z01=U001=1001Z=V1=Z01=V101=01012.5已知文法G[S]：S∷=ABA∷=aA︱εB∷=bBc︱bc,写出该文法描述的语言。A∷=aA︱ε描述的语言:{an|n=0}B∷=bBc︱bc描述的语言：{bncn|n=1}L(G[S])={anbmcm|n=0,m=1}2.6已知文法E∷=T∣E+T∣E-T、T∷=F∣T*F∣T/F、F∷=(E)∣i，写出该文法的开始符号、终结符号集合VT、非终结符号集合VN。SSS*SS+aaa开始符号：EVt={+,-,*,/,（,）,i}Vn={E,F,T}2.7对2.6题的文法，写出句型T+T*F+i的短语、简单短语以及句柄。短语：T+T*F+iT+T*FiiTT*F简单短语：iT*FT句柄：T2.8设有文法G[S]：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,m≥1}的文法。G[S]:S::=ABA::=aA|aB::=bB|b3.1有正则文法G[Z]：Z::=Ua|Vb，U::=Zb|b，V::=Za|a，画出该文法的状态图，并检查句子abba是否合法。解：该文法的状态图如下：句子abba合法。SSS*S+SaaaSSS+S*SaaaETE+FTE+iFT*T3.2状态图如图3.35所示，S为开始状态，Z为终止状态。写出相应的正则文法以及V，Vn和Vt。解：左线性文法G[Z]:右线性文法G’[S]:Z::=Ab|bS::=aA|bA::=Aa|aA::=aA|bV={Z,A,a,b}V={S,A,a,b}Vn={Z,A}Vn={S,A}Vt={a,b}Vt={a,b}3.3构造下列正则表达式相应的NFA：1(1|0)*|01(1010*|1(010)*1)*0解：正则表达式：1(1|0)*|0正则表达式：1(1010*|1(010)*1)*03.4将右图的NFAM确定化解：01a,baaabq0={0}{0,1}{1}q1={0,1}{0,1}{1}q2={1}{0}ΦDFA:3.5将图3.37的DFA化简。解：划分ab{0,1}{1}{2,4}{2,3,4,5}{1,0,3,5}{3,5,2,4}划分ab{0,1}{1}{2,4}{2,4}{0,1}{3,5}{3,5}{3,5}{2,4}q0={0,1}q1={2,4}q2={3,5}化简后的DFA：4.1对下面文法，设计递归下降分析程序。S→aAS|(A),A→Ab|c解：首先将左递归去掉，将规则A→Ab|c改成A→c{b}非终结符号S的分析程序如下：非终结符号A的分析程序如下：4.2设有文法G[Z]：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），在分析过程中，将造成回溯。改写文法可避免回溯：将规则B∷=Aab代入规则A∷=a|Bb得：A∷=a|Aabb，再转换成：A∷=a{abb}，可避免回溯。4.3若有文法如下，设计递归下降分析程序。语句→语句赋值语句|ε赋值语句→ID=表达式表达式→项|表达式＋项|表达式－项项→因子|项*因子|项/因子因子→ID|NUM|(表达式)解：首先，去掉左递归语句→语句赋值语句|ε改为：语句→{赋值语句}表达式→项|表达式+项|表达式-项改为：表达式→项{（+|-）项}项→因子|项*因子|项/因子改为：项→因子{（*|/）因子}则文法变为：语句→{赋值语句}赋值语句→ID=表达式表达式→项{（+|-）项}项→因子{（*|/）因子}因子→ID|NUM|(表达式)非终结符号语句的分析程序如下：非终结符号赋值语句的分析程序如下：非终结符号表达式的分析程序如下：语句→{赋值语句}赋值语句→ID=表达式表达式→项{（+|-）项}非终结符号项的分析程序如下：非终结符号因子的分析程序如下：4.4有文法G[A]：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(B’b)B’POPPOP，复值语句的分析程序项→因子{（*|/）因子}因子→ID|NUM|(表达式)PUSH(B’b)aPOP,NEXTSYMePOP,NEXTSYMbPOP,NEXTSYM#ACCEPT更常用且简单的LL(1)分析表：aeb#AA→aABeA→εA→εBB→bB’B’B’→εB’→bB’4.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，识别以下算术表达式，请写出分析过程。（1）i+i*i+i（2）i*(i+i+i)解：（1）i+i*i+i步骤分析栈余留输入串分析表元素所用产生式1#Ei+i*i+i#POP,PUSH(E’T)E→TE’2#E’Ti+i*i+i#POP,PUSH(T’F)T→FT’3#E’T’Fi+i*i+i#POP,PUSH(i)F→i4#E’T’ii+i*i+i#POP,NEXTSYM5#E’T’+i*i+i#POPT’→ε6#E’+i*i+i#POP,PUSH(E’T+)E’→+TE’7#E’T++i*i+i#POP,NEXTSYM8#E’Ti*i+i#POP,PUSH(T’F)T→FT’9#E’T’Fi*i+i#POP,PUSH(i)F→i10#E’T’ii*i+i#POP,NEXTSYM11#E’T’*i+i#POP,PUSH(T’F*)T’→*FT’12#E’T’F**i+i#POP,NEXTSYM13#E’T’Fi+i#POP,PUSH(i)F→i14#E’T’ii+i#POP,NEXTSYM15#E’T’+i#POPT’→ε16#E’+i#POP,PUSH(E’T+)E’→+TE’17#E’T++i#POP,NEXTSYM18#E’Ti#POP,PUSH(T’F)T→FT’19#E’T’Fi#POP,PUSH(i)F→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)E→TE’2#E’Ti*(i+i+i)#POP,PUSH(T’F)T→FT’3#E’T’Fi*(i+i+i)#POP,PUSH(i)F→i4#E’T’ii*(i+i+i)#POP,NEXTSYM5#E’T’*(i+i+i)#POP,PUSH(T’F*)T’→*FT’6#E’T’F**(i+i+i)#POP,NEXTSYM7#E’T’F(i+i+i)#POP,PUSH()E()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’Ti+i+i)#POP,PUSH(T’F)T→FT’11#E’T’)E’T’Fi+i+i)#POP,PUSH(i)F→i12#E’T’)E’T’ii+i+i)#POP,NEXTSYM13#E’T’)E’T’+i+i)#POPT’→ε14#E’T’)E’+i+i)#POP,PUSH(E’T+)E’→+TE’15#E’T’)E’T++i+i)#POP,NEXTSYM16#E’T’)E’Ti+i)#POP,PUSH(T’F)T→FT’17#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’→ε20#E’T’)E’+i)#POP,PUSH(E’T+)E’→+TE’21#E’T’)E’T++i)#POP,NEXTSYM22#E’T’)E’Ti)#POP,PUSH(T’F)T→FT’23#E’T’)E’T’Fi)#POP,PUSH(i)F→i24#E’T’)E’T’ii)#POP,NEXTSYM25#E’T’)E’T’)#POPT’→ε26#E’T’)E’)#POPE’→ε27#E’T’))#POP,NEXTSYM28#E’T’#POPT’→ε29#E’#POPE’→ε30##ACCEPT4.7考虑下面简化了的C声明文法：声明语句→类型变量表；类型→int|float|char变量表→ID,变量表|ID（1）在该文法中提取左因子。（2）为所得的文法的非终结符构造FIRST集合和FOLLOW集合。（3）说明所得的文法是LL(1)文法。（4）为所得的文法构造LL(1)分析表。（5）假设有输入串为“charx，y，z；”，写出相对应的LL(1)分析过程。解：（1）规则变量表→ID,变量表|ID提取公因子如下：变量表→ID（,变量表|ε）增加新的非终结符变量表1，规则变为：变量表→ID变量表1变量表1→，变量表|εC声明文法改变为：