2023-07-26 15:31

关注

处理语法规则中的运算符优先级、左递归和结合性

序言

近期的工作是为 govaluate 编写 Monaco 编辑器插件，来支持词法高亮、语法检测、方法变量检索和自动补全等功能。

govaluate 是 Go 语言生态中一个用于解析表达式求值的库，它的语法类似于 C 语言表达式。为了让 Monaco 编辑器支持它，我们需要梳理其语法规则，并编写相应的语法解析器。

考虑到实现成本，我选择使用 ANTLR 生成语法解析器，而不是手写递归下降语法解析器。使用 ANTLR 后，发现它带来了的更多惊喜。其中最重要的是，它能够隐式处理运算符优先级、左递归和结合性，无需我们手动优化 BNF。

运算符优先级、左递归和结合性

用自上而下的语法描述表达式，并手工编写递归下降语法分析器识别表达式总是很繁琐的。这主要是因为最自然的语法存在二义性，以及最直观的规范存在左递归。稍后我们将详细讨论左递归的问题，但现在需要明确的是，传统的自上而下的语法和解析器无法处理左递归。

为了说明这个问题，考虑一个简单的算术表达式，它包含乘法和加法运算符以及整数。由于每个表达式都具有相似的结构，我们自然地将乘法表达式描述为由 '*' 连接的两个子表达式。类似地，加法表达式是由 '+' 连接的两个子表达式。我们也可以用简单的整数作为表达式。表面上看，我们可以使用以下规则描述其语法：

expr : expr '*' expr // 匹配通过 '*' 运算符连接的子表达式
     | expr '+' expr // 匹配通过 '+' 运算符连接的子表达式
     | INT           // 匹配整数
     ;

然而，该规则存在二义性，即对于某些输入短语存在多种匹配方式。它适用于简单整数和单运算符表达式，如 1+2 和 1*2，因为只有一种方法匹配它们的方式。例如，只能选择第二条规则来匹配 1+2：

1+2

问题是，例如 1+2*3 可以用两种不同的方式来解释。这两种方式具有不同的语义，左侧的树说将2和3相乘的结果加1，而右边的树将3乘以1和2的结果。

1+2*3

这是一个运算符优先级的问题，传统语法根本无法指定优先级。大多数语法工具，如 Bison 使用附加标记来指定运算符的优先级。

相反，ANTLR 允许我们通过子表达式的顺序隐式地指定运算符的优先级。在规则 expr 中，乘法表达式在加法表达式之前，这使得 ANTLR 解决了 1+2*3 的运算符歧义。

默认情况下，ANTLR 将运算符从左向右结合，正如我们对 '*' 和 '+' 所期望的那样。不过，有些运算符更偏向从右到左结合，此时必须使用选项 assoc 手动指定运算符的结合性。下面是一个表达式规则，可以将输入 2^3^4 正确解释为 2^(3^4)：

expr : expr '^'<assoc=right> expr // ^ 运算符从右到左结合
     | INT
     ;

下面的解析树说明了使用不同结合性的 '^' 运算符的区别。通常情况下，我们希望得到右侧的解析树，但是语言设计者可以自由地选择任何一种结合性。

2^3^4

要将所有三个运算符组合在一个规则中，我们将 '^' 子表达式放在其他运算符之前，因为它的优先级高于 '*' 和 '+'（1+2^3 的运算结果是9）。

expr : expr '^'<assoc=right> expr // ^ 运算符从右到左结合
     | expr '*' expr // 匹配通过 '*' 运算符连接的子表达式
     | expr '+' expr // 匹配通过 '+' 运算符连接的子表达式
     | INT // 匹配整数
     ;

熟悉 ANTLR v3 的读者，他们一直在等待我指出，ANTLR 和所有传统的自上而下的解析器生成器一样，无法处理左递归规则。然而，ANTLR v4 的一个主要改进是它现在可以处理直接左递归。左递归规则指在子表达式的左侧直接或间接调用自身的规则。由于除了 INT 子表达式之外的所有子表达式都以对 expr 规则本身的引用开头，因此 expr 规则是直接递归的（它也是右递归的，因为一些子表达式的右侧引用了 expr）。

尽管 ANTLR v4 可以处理直接左递归，但它无法处理间接左递归。这意味着我们无法处理下面这个等效的语法规则：

expr : expo // 通过 expo 间接递归调用 expr
     | ...
     ;  
expo : expr '^'<assoc=right> expr ;

处理左递归的传统方法

为了使用 ANTLR v3 来识别表达式，我们必须将 expr 中的左递归拆分为多个规则，每个优先级一个规则。例如，对于带有乘法和加法运算符的表达式，我们将使用以下规则：

expr : addExpr ;  
addExpr : multExpr ('+' multExpr)* ; multExpr: atom ('*' atom)* ;  
atom : INT ;

对于像 C 和 Java 这样的语言，表达式最终需要大约15个这样的规则。无论是构建自上而下的语法还是手写构建递归下降语法分析器，这都是一项繁琐的工作。

ANTLR v4 简化了对直接左递归表达式规则的处理。新机制不仅效率更高，而且表达式规则也更简短、更易于理解。例如，在 Java 语法中，专用于表达式的行数减少了一半（从172行减少到91行）。

ANTLR 如何移除直接左递归

简而言之，ANTLR 用一个 (...)* 来代替左递归，(...) 中比较运算符的优先级。

让我们从 ANTLR 执行的转换开始，然后通过一个例子来了解优先级爬升算法（precedence climbing）。

直接左递归子表达式模式

ANTLR 搜索所有左递归规则，查找与以下4种子表达式运算符模式匹配的规则。

1. 二元运算（binary）

任何形如 expr op expr 或 expr (op1|op2|...|opN) expr 的子表达式。op 可以表示由单个单词或多个单词组成的运算符。例如，Java 语法可能会单独处理尖括号，而不是将运算符 <=> 和 >= 视为单个单词。以下是一个语法规则，用于以相同的优先级处理比较运算符：

expr: ...
    | expr ('<' '=' | '>' '=' | '>' | '<') expr
    ...
    ;

op 也可以是规则引用。例如，我们可以将这些单词放到另一个规则中。

expr: ...
    | expr compareOps expr
    ...
    ;
compareOps : ('<' '=' | '>' '=' | '>' | '<') ;

2. 三元运算（ternary）

任何形如 expr op1 expr op2 expr 的子表达式。op1 和 op2 必须是单个单词组成的运算符。此模式处理 C 族语言中的 ?: 运算符：

expr: ...
    | expr '?' expr ':' expr
    ...
    ;

3. 前缀一元运算（unary prefix）

任何形如 elements expr 的子表达式。ANTLR 将后面跟着尾部递归规则引用的任何序列识别为一元前缀操作，只要子表达式不是二元运算和三元运算模式。以下是两种使用前缀运算符的语法规则：

expr: ...  
    | '(' type ')' expr
    ...  
    | ('+'|'-'|'++'|'--') expr
    ...
    ;

4. 后缀一元运算（unary suffix）

任何形如 expr elements 的子表达式。与前缀一元运算模式一样，ANTLR 识别具有直接左递归规则引用的任何元素序列的子表达式，只要它不符合二元运算或三元运算模式。以下是两种使用后缀运算符的语法规则：

expr: ...  
    | expr '.' Identifier
    ...  
    | expr '.' 'super' '(' exprList? ')'
    ...
    ;

除了运算符模式外，任何其他模式都被视为主表达式元素，包括诸如 '(' expr ')' 之类的内容，因为它不适用于运算符模式。这是有道理的，因为括号的目的是将封闭的表达式视为单个原子元素。这些模式可以以任何顺序出现，ANTLR 会收集并妥善处理它们。以下是一些表示主表达式的语法规则：

expr: ...
    | literal
    | Identifier
    | type '.' 'class'
    ...
    ;

除非另有规定，否则 ANTLR 假设所有运算符都是左结合性。换句话说，1+2+3 被解析为 (1+2)+3。但是，有些运算符是右结合性，例如赋值和求幂。为了指定正确的结合性，可以使用 assoc 选项：

expr: expr '^'<assoc=right> expr
    ...
    | expr '='<assoc=right> expr
    ...
    ;

左递归规则转换

如果启用 -Xlog ANTLR 命令行选项，你可以在日志文件中找到经过转换的左递归规则。以下是前面显示的 expr.g4 中的规则 stat 和 expr 的情况：

// 使用 "antlr4 -Xlog Expr.g4" 查看转换后的规则
stat: expr[0] ';' ; // 匹配包含多种优先级运算符的表达式

expr[int _p] // _p 表示期望的最小优先级
    : ( INT // 匹配主表达式（非运算符）
      | ID
      )
      // 匹配运算符只要它们的优先级等于或高于预期的最小值
      ( {4 >= $_p}? '*' expr[5] // * has precedence 4  
      | {3 >= $_p}? '+' expr[4] // + has precedence 3
      )*
    ;

关键是决定匹配当前运算符还是匹配下一个运算符。(...)* 循环匹配运算符和右操作数。对于输入 1+2*3 ，循环将匹配 +2 和 *3。循环替换中优先级的目的是决定解析器是应该立即匹配当前运算符和操作数对，还是退出当前的规则。例如，优先级断言 {3>=$_p}? 表示，如果当前子表达式的预期最小优先级 _p 大于加法运算符的优先级3，则退出加法规则。

_p 的值总是从上一个运算符的优先级得来，就像 stat 所做的那样：expr[0]，_p 从0开始。要了解 _p 的作用，让我们看看从转换后的规则生成的一些解析树（在方括号中显示参数 _p 的值）。请注意，这些解析树不是 ANTLR 根据原始的左递归规则构建的。这些是转换后的规则的解析树，而不是原始规则。以下是一些示例输入和相关的解析树：

在第一个树中，对 expr 的初始调用 _p 为0，expr 立即用子规则 (INT|ID) 匹配1。现在，expr 必须决定它是匹配 + 还是跳出闭包并返回。优先级的断言 {3>=0}? 为真，因此进入循环并匹配 +，然后用参数4递归调用 expr。本次调用匹配2并立即返回，因为没有更多的输入。expr[0] 返回到 stat 中对 expr 的原始调用。

第二个树说明了 expr[0] 如何匹配1，并且再次断言 {3>=0}? 为真，允许我们匹配 + 运算符后面跟着的第二个操作数 expr[4]。对 expr[4] 的递归调用匹配2，然后优先级断言 {4>=4}? 为真，这使得解析器可以通过调用 expr[5] 来匹配 * 运算符和最后一个操作数3。

第三个解析树是最有趣的。初始调用 expr[0] 匹配1，然后决定匹配 * 操作，因为优先级断言 {4>=0}? 为真。然后，该循环递归地调用 expr[5]，它立即匹配2。现在，在对 expr[5] 的调用中，解析器不应该匹配 +，否则 2+3 将在乘法之前求值。（在解析树中，我们会看到带有 2+3 的 expr[5] 作为子级，而不仅仅是2。）优先级断言 {3>=5}? 为假，不接收该子规则，因此 expr[5] 在不匹配 + 的情况下返回。返回后，expr[0] 匹配 +3，因为优先级断言 {3>=0}? 为真。