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

(完整word)1编译原理及实现课后题及答案(完整word)1编译原理及实现课后题及答案PAGE\*MERGEFORMAT53(完整word)1编译原理及实现课后题及答案编译原理及实现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）3设有文法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，请写出全部由此文法描述的只含有四个符号的句子。2。5已知文法G[S］：S∷=ABA∷=aA︱εB∷=bBc︱bc,写出该文法描述的语言。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=下一个符号YINPUTSYM=’)’INPUTSYM=下一个符号YNN出口错误错误过程A过程S过程A非终结符号A的分析程序如下：过程AINPUTSYM=’c’INPUTSYM=下一个符号YINPUTSYM=’b’N错误INPUTSYM=下一个符号Y出口N4。2设有文法G[Z]：Z∷=（A),A∷=a｜Bb,B∷=Aab若采用递归下降分析方法,对此文法来说，在分析过程中，能否避免回溯？为什么？解:若采用递归下降分析方法，对此文法来说,在分析