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

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

词法分析是编译原理中的一个重要环节，其中分析树和二义性文法是理解词法分析的关键概念。本文将通过具体例子，深入探讨分析树的结构特点以及二义性文法的消除方法。

分析树

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

本文原文来自o2oxy.cn