编译原理及实现课后习题答案.doc

(完整word)编译原理及实现课后习题答案(完整word)编译原理及实现课后习题答案(完整word)编译原理及实现课后习题答案编译原理及实现课后习题解答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|=12设有文法G[S]：S∷=SS＊|SS+｜a,写出符号串aa+a*规范推导，并构造语法树。S=〉SS＊=>Sa＊=>SS+a＊=〉Sa+a*=>aa+a＊SSS*SS+aaa2。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。开始符号：EVt={+,—,*,/，（,),i}Vn={E,F,T｝ETE+FTE+iFT*T2.7对2。6题的文法，写出句型T+T＊F+i的短语、简单短语以及句柄.短语：T+T*F+iSHAPE\＊MERGEFORMATT+T*FiiTT*F简单短语：iT＊FT句柄：T2。8设有文法G[S］：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，m≥1}的文法。G[S］:S::=ABA：:=aA|aB：：=bB|b3。1有正则文法G[Z]：Z:：=Ua｜Vb,U：:=Zb|b，V:：=Za|a，画出该文法的状态图，并检查句子abba是否合法。解:该文法的状态图如下：SUVZaaabbb句子abba合法。3。2状态图如图3。35所示，S为开始状态,Z为终止状态。写出相应的正则文法以及V，Vn和Vt.SAZabab图3-35状态图解：左线性文法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)*|01、SZ1(1|0)*|02、SZ1(1|0)*03、SAZ01ε014、q0q1010,1q2正则表达式:1(1010*|1(010）＊1）*001354621010107801011ε01a,baa将图3。36的NFAM确定化图3.36状态图解：abq0={0}｛0，1｝｛1}q1={0，1}｛0，1}{1}q2=｛1}｛0｝ΦDFA：q0q1q2ababa将图3.37的DFA化简。014253aaaaaabbbbbb图3.37DFA状态图解：划分ab｛0，1}{1}｛2，4｝{2,3,4，5}｛1，3,0,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：q0q1q2baaabb4。1对下面文法，设计递归下降分析程序。S→aAS｜（A），A→Ab｜c解:首先将左递归去掉，将规则A→Ab｜c改成A→c{b｝非终结符号S的分析程序如下：过程SINPUTSYM=’a’INPUTSYM=下一个符号YNINPUTSYM=’(’INPUTSYM=下一个符号YINPUT