词法分析 | 分析树和二义性文法

分析树

1、推导可以表达成树状的形状结构 （和推导的顺序无关）

2、特点

    一、树中的每个内部节点代表非终结符

    二、每个叶子节点代表终结符

    三、每一步推导代表如何从双亲节点生成它的直接孩子节点。

例子1 

如果G为

E--> num 
E--> id 
E--> E+E
E--> E*E

推导出5+6*7 为如下图

第一种推导方式

第二种推导方式

他们的结果完全不相同。

这就导致了二义性的产生。正确的应该是第一种的方式。

那么基于存在二义性的问题。可以通过三种解决方案：

二义性的消除

1、将二义文法改成非二义文法；
2、规定二义文法中符号的优先级和结合性；
3、改变语言的结构或书写方式。

使用第一种方法

需要引入新的终结符，且新引入的非终结符

E -> E + T
   | T
T -> T * F
   | F
F -> num
   | id

5+6*7的推导过程

 E -> E + T
   -> T + T
   -> F + T
   -> 5 + T
   -> 5 + T * F
   -> 5 + F * F
   -> 5 + 6 * F
   -> 5 + 6 * 7

使用第二种方法

引入优先级的

E -> T | E + T | E - T
T -> num | T * num | T / num

这样的一个推导过程

E -> T
E -> E + T
E -> T + T
T -> T * num
T -> num * num
E -> 5 + T
E -> 5 + T * F
E -> 5 + F * F
E -> 5 + 6 * F
E -> 5 + 6 * 7

还有更多的方式可以参考如下的链接

https://www.jianshu.com/p/2d55d50f8bc4