内容发布更新时间 : 2024/9/12 15:02:28星期一 下面是文章的全部内容请认真阅读。
编译原理及实现
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