编译原理(大题2).doc

1. 已知文法 GS: ，证明文法GS为二义文法。解：证明： 由文法GS：SaSb|Sb|b，对句子aabbbb对应的两棵语法树为：因此，文法GS为二义文法。 2. 已知文法GS： 答： 对于串abc (1)S=Ac=abc (2)S=aB=abc 即存在两不同的最右推导。所以，该文法是二义的3. 设有文法GS: , 证明文法GS为二义文法。答：因为文法G【S】存在句子aa有两个不同的最左推导：所以文法GS是二义性的：S=SaS=SaSaS=aSaS=aaS=aa=S=SaS=aS=aSaS=aaS=aa4已知文法GP：, 证明文法GP为二义文法。答：解答：因为文法存在句型fbfbf，此句型有两棵不同的语法树，5 已知文法GP：, 证明文法GP为二义文法。答：对于文法G定义的句子i+i*i，有两棵不同的语法树：