2 二义性

分析树

分析树是推导的图形表示，分析树忽略了不同的推导顺序（左和右）。

二义性

有些文法的有些句子存在不止一颗分析树（即存在多种推导）。

如果这样的情况存在，就称这个文法是二义的。

大多数情况下都希望文法是无二义的，但是在某些情况下精心选择的二义文法也可以带来方便，但是同时需要消二义性规则来给每个句子只留下一棵语法分析树。

语言和文法的关联

正规式可以描述的语言都可以用上下文无关文法来描述。

文法的表示功能更强大。

此法规则非常简单，不必用功能更强的文法来描述。

词法记号构造（正规式）比文法更加简洁且易于理解。

消除二义性

若没有规定 $+,*$ 的优先级，则在解释类似 $a*b+c$ 的时候会导致二义性。

需要通过文法分层来消除这种二义性。

比如规定 $term$ 是某种乘法表达式，$factor$ 是最小运算单元，可以重写之前的文法：

• $expr→term+expr|term$
• $term→factor*term|factor$
• $factor→id|(expr)$

注意这里 $term+expr$ 的顺序实际上隐式地声明了算符的结合性（左结合的）。

定义语言语法的文法有二义性并不可怕，只要有消除二义性的规则就行了（比如 if-else match 文法中指定 else 与最接近的未配对 if 匹配）。

举例：

stmt → if expr then stmt | if expr then stmt else stmt | other

我们有一个实例语句：

if E1 then if E2 then S1 else S2

有下面两种分析方式（用缩进表示）：

if E1:
    if E2:
        S1
    else:
        S2

if E1:
    if E2:
        S1
else:
    S2

解决办法：

基本思想是在一个 then 和一个 else 之间出现的语句必须是 matched 的，不能是尚未匹配的 then 结尾。

stmt → matched_stmt | open_stmt

matched_stmt → if expr then matched_stmt else matched_stmt | other

open_stmt → if expr then stmt | if expr then matched_stmt else open_stmt

本文阅读量