编译原理练习三答案

练习三9、考虑下面上下文无关文法：SSS*|SS+|a（1）表明通过此文发如何生成串aa+a*,并为该串构造推导树。（2）该文法生成的语言是什么？答:（1）S=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）该文发是二义的吗？说明理由。答：（1）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)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是它的一个句型。因为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） 产生式包括：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的短语。B=b，b是相对B的短语。B=SBB=BB =bB=bb，bb是相对B的短语。直接短语有：a，b，句柄：a14、给出生成下述语言的上下文无关文法：（1）abab|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=0（2）1010|n,m=0答：S-1S0 S-A A-0