作业2解答-编译原理作业答案-孙悦红

2.1设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及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=Z00=U000=1000Z=V1=Z00=V100=01002.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+i,T+T*Fi(简单短语)T(简单短语、句柄)T*F2.8设有文法G[S]：S∷=S*S|S+S|(S)|a，该文法是二义性文法吗？根据所给文法推导出句子a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。2.9写一文法，使其语言是奇正整数集合。A::=1|3|5|7|9|NAN::=N0|N1|N2|N3|N4|N5|N6|N7|N8|N9|N::=0|1|2|3|4|5|6|7|8|92.10给出语言{anbm|n,m≥1}的文法。G[S]:S::=ABA::=aA|aB::=bB|bSSS*S+SaaaSSS+S*Saaa