编译原理作业题.doc

={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…}∑={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+[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=>[S]:S∷=ABA∷=aA︱εB∷=bBc︱bc,写出该文法描述的语言。A∷=aA︱ε描述的语言:{an|n>=0}B∷=bBc︱bc描述的语言:{|n>=1}L(G[S])={anbmcm|n>=0,m>=1}∷=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*,写出句型T+T*F+i的短语、简单短语以及句柄。短语:T+T*F+iT+T*FiiTT*F简单短语:iT*FT句柄:[S]:S∷=S*S|S+S|(S)|a,该文法是二义性文法吗?SSS*S+SaaaSSS+S*Saaa根据所给文法推导出句子a+a*a,画出了两棵不同的语法树,所以该文法是二义性文法。,使其语言是奇正整数集合。A::=1|3|5|7|9|NAN::=0|1|2|3|4|5|6|7|8|{anbm|n,m≥1}的文法。G[S]:S::=ABA::=aA|aB::=bB|[Z]:Z::=Ua|Vb,U::=Zb|b,V::=Za|a,画出该文法的状态图,并检查句子abba是否合法。解:该文法的状态图如下:SUVZaaabbb句子abba合法。,S为开始状态,Z为终止状态。写出相应的正则文法以及V,Vn和Vt。SAZabab图3-35状态图解:左线性文法G[Z]:右线性文法G’[S]:Z::=Ab|b S::=aA|b A::=Aa|a A::=aA|bV={Z,A,a,b} V={S,A,a,b}Vn={Z,A} Vn={S,A}Vt={a,b} Vt={a,b}: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)*0013546210**********ε01a,:abq0={0}{0,1}{1}q1={0,1}{0,1}{1}q2={1}{0}Φ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:,设计递归下降分析程序。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=下一个符号YINPU