文档库

最新最全的文档下载
当前位置:文档库 > 编译原理(大题2)

编译原理(大题2)

1. 已知文法 G[S]: S aSb Sb b →,证明文法G[S]为二义文法。

解:证明:

由文法G[S]:S →aSb|Sb|b ,对句子aabbbb

对应的两棵语法树为:

编译原理(大题2)

因此,文法G[S]为二义文法。

2. 已知文法G[S]:

|S Ac aB

A ab

B bc

→→→ 答: 对于串abc (1)S=>Ac=>abc (2)S=>aB=>abc 即存在两不同的最右推导。所以,该文法是二义的

3.设有文法G[S]: ()|S S S S ε→, 证明文法G[S]为二义文法。

答:因为文法G 【S 】存在句子aa 有两个不同的最左推导:所以文法G[S]是二义性的: S =>SaS=>SaSaS=>aSaS=>aaS=>aa=

S=>SaS=>aS=>aSaS=>aaS=>aa

4.已知文法G[P]:P PaP PbP cP Pe f →, 证明文法G[P]为二义文法。

答:解答:因为文法存在句型fbfbf

,此句型有两棵不同的语法树,

编译原理(大题2)

5.已知文法G[P]:()*|P S S S S i S →+, 证明文法G[P]为二义文法。

答:对于文法G 定义的句子i+i*i ,有两棵不同的语法树

编译原理(大题2)