编译原理——证明文法具有二义性

证明一个文法具有二义性我们需要掌握两个知识点。

1.语法分析树

定义很简单,就是把一个句型的推导写成树的形式,这种表示法就叫语法分析树,或者简称为语法树。大概是这个样子的
编译原理——证明文法具有二义性

2.二义性

一个文法存在某个句子对应两棵不同的语法树,则称这个文法是二义的。也就是该句子有两个不同的最左(最右)推导。


ok,让我们
编译原理——证明文法具有二义性
证明下列文法G(S)是二义的
S->Ac|aB
A->ab
B->bc

过程很简单就是自己定义一个句子,然后说明这个句子有两个语法树就可以了。
这里定义句子是abc,对应的两个语法树像这个样子
编译原理——证明文法具有二义性
所以该文法是二义文法。