词法分析：分析树与二义性文法详解

词法分析：分析树与二义性文法详解

词法分析是编译原理中的一个重要环节，其中分析树和二义性文法是两个核心概念。本文将通过具体例子，详细解释分析树的结构特点，并探讨二义性文法的产生原因及其解决方案。

分析树

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

推导过程：

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

更多解决方案可以参考：简书