编译原理练习三答案(共5页).doc

精选优质文档-倾情为你奉上练习三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(