编译原理及实现
2.1 设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及A+和A*.
x0=(aaa)0=ε | x0|=0 xx=aaaaaa |xx|=6 x5=aaaaaaaaaaaaaaa | x5|=15 A+ =A1∪A2∪ …. ∪A n∪…={a,aa,aaa,aaaa,aaaaa…} A* = A0 ∪A1 ∪ A2 ∪ …. ∪ A n ∪…={ε,a,aa,aaa,aaaa,aaaaa…}
2.2 令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3
xy=abcb |xy|=4xyz=abcbaab |xyz|=7(xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=12
2.3 设有文法G[S]：S∷=SS*|SS+|a，写出符号串aa+a*规范推导，
并构造语法树。
S => SS* => Sa* => SS+a* => Sa+a* => aa+a*
1
S S S * S a S a + 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=>0101
2.5 已知文法G[S]： S∷=AB A∷=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。
开始符号：E
Vt={+, - , * , / ,（ , ）, i} Vn={E , F , T}
2
2.7 对2.6题的文法，写出句型T+T*F+i的短语、简单短语以及句柄。
短语：T+T*F+i T+T*F i i T T*F 简单短语：i T*F T 句柄：T
2.8 设有文法G[S]：S∷=S*S|S+S|(S)|a，该文法是二义性文法吗？
S S * S S S E E E T + T + T * F T F i + S S + S a a S * S a a a a
根据所给文法推导出句子a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。
2.9 写一文法，使其语言是奇正整数集合。 A::=1|3|5|7|9|NA
3