《编译原理练习三答案》由会员分享，可在线阅读，更多相关《编译原理练习三答案（5页珍藏版）》请在金锄头文库上搜索。
1、细心整理练习三9、考虑下面上下文无关文法：SSS*|SS+|a1说明通过此文发如何生成串aa+a*,并为该串构造推导树。2该文法生成的语言是什么？答:1S=SS*=SS+S*=aS+S*=aa+S*=aa+a*S=SS*=SS*S*=SS*S*S*=S(S*)=Sa*(S*)=aa*a*(S*)=S(a*)=SS+(a*)=SS+S+(a*)=SS+S+S+(a*)=S(S+)(a*)=a(S+)(a*)=aa+(S+) (a*)=aa+a+(S+) (a*)=a(a+)(a*)所以该文发生成的语言是：L1= a(a+)(a*)|n,m=110、文法S-S(S)S|1生成的语言是什么？2该文发
2、是二义的吗？说明理由。答：1S=S(S)S=S(S(S)S)S=S(S(S)S)S=S(S)S(S(S)S)S=S(S)S(S)S(S(S)S)S=(S(S)S(S(S)S)S=(S(S)S(S(S)S)S(S)S=(S(S)S(S(S)S)S(S)S(S)S=(S(S)S(S(S)S) (S(S)S所以该文法生成的就是嵌套的括号。2由上面推导过程可知该语法可以构成不同的语法树，所以它是二义的。11、令文法GE为：E-T|E+T|E-TT-F|T*F|T/FF-(E)|i证明E+T*F是它的一个句型，指出这个句型的全部短语，干脆短语和句柄。答：因为E=E+T=E+T*F，所以E+T*F是它的一
3、个句型。因为E=E+T=E+T*F，所以该句型相对于E的短语有：E+T*F因为T- T*F，所以该句型相对于T的短语有：T*F干脆短语为：T*F句柄为：T*F13、一个上下文无关文法生成句子abbaa的推导树如下：（1） 给出该句子相应的最左推导，最右推导。（2） 该文法的产生式集合P可能有哪些元素？（3） 找出该句子的全部短语，简洁短语，句柄。答：（1） 最右推导：S=ABS=ABAa=ABaa=ASBBaa=ASBbaa=ASbbaa=Abbaa=Abbaa=abbaa最左推导：S=ABS=aBS=aSBBS=aBBS=aBBS=abBS=abbS=abbAa=abbaa（2） 产生式包括
4、：S-ABS|Aa| B-b|SBB A-a该文法的产生式集合P可能有 S=S=Aa=aaS=ABS=aBS=abS=ab =abS=ABS=ABAa=aBAa=abAa=abaaS=ABS=ASBBS=AAaBBS=aAaBBS=aaaBBS=aaabBS=aaabbS=aaabb=aaabb所以有 aa ab abaa aaabb 3因为产生式包括：S-ABS|Aa| B-b|SBB A-aS=，是相对S的短语。S=Aa=aa，aa是相对S的短语。S=ABS=aBS=aSBBS=aBBS=aBBS=abBS=abbS=abbAa=abbaa，abbaa是相对S的短语。A=a，a是相对A的短
5、语。B=b，b是相对B的短语。B=SBB=BB =bB=bb，bb是相对B的短语。干脆短语有：a，b，句柄：a14、给诞生成下述语言的上下文无关文法：1abab|n,m=0答：S-ASBS S-ASB S- A-a B-bS=ASBS=aSBS=aSbS=aASBbS=aaSbBS=aaSbbS=aaASbbBS=aaaSbbBS=aaaSbbbS=aSbS=abS=abS=abASB= abaSB= abaSb=abaASBb=abaaSBb=abaaSbb= abaSb= abab= abab推导得：L1=abab|n,m=021010|n,m=0答：S-1S0 S-A A-0A1 A-S=1S0=11S00=111S000=1S0=1A0=11A00=111A000=10A10=1010=1010推导得：L2=1010|n,m=0
