优先级，左递归以及相关性

优质

小牛编辑

131浏览

2023-12-01

用自顶向下的语法指定和通过手工的递归下降语法分析器识别表达式一直是个麻烦。首先是因为大部分自然语法是模糊的，其次是因为大部分自然语法规格使用一种被称为左递归的特殊类型递归。所以自顶向下的语法和语法分析器不能处理传统形式上的左递归。

为了阐明这个问题，设想一个算术表达式语言，它只有乘法和加法运算符以及整数。表达式是自相似的。也就是说，一个乘法表达式是由“*”运算符连接的两个子表达式。同样的，一个加法表达式是由“+”运算符连接的两个子表达式。我们也可以把整数看作表达式。整个语法规则看起来就像以下显示的那样：

expr : expr '*' expr    // 匹配由“*”运算符连接的子表达式
     | expr '+' expr    // 匹配由“+”运算符连接的子表达式
     | INT              // 匹配简单整数
     ;

问题是上述规则对于某些输入短语来说是模棱两可的。换句话说，这个规则能用多种方法匹配单个输入流。对于简单的整数和像1+2和1*2这样的单运算符表达式是没问题的，因为只有一种方法能去匹配它们。例如，规则可以仅用第二个选项匹配1+2。就像下图左边所示的那样：

问题是指定的规则可以像中间和右边语法分析树描绘的那样用两种方法解释1+2*3这样的输入。两者的解释是不同的，因为中间的树说加1到2乘3的结果上，而右边的树说3乘以1加2的结果。这是一个运算符优先级的问题，但常规语法根本没有指定优先级的方法。大部分语法工具使用额外的符号来指定运算符优先级。

与之相反的是，ANTLR解决二义性有利于首先给出的选项，隐式地允许我们指定运算符优先级。规则expr有一个乘法选项在加法选项之前，因此，ANTLR解决1+2*3的运算符二义性有利于乘法。

默认情况下，ANTLR从左到右结合运算符，然而某些像指数群这样的运算符则是从右到左。因此，我们必须使用选项assoc手动指定运算符记号上的相关性。这里是一个能正确地把输入2^3^4解释成2^(3^4)的表达式规则：

expr : expr '^'<assoc=right> expr    // 运算符是右结合的
     | INT
     ;

下图中的语法分析树阐明了运算符左右结合版本的不同。右边的语法分析树是惯常的解释：

为了把所有这三个运算符合并成一条规则，我们把指数表达式选项放在其它表达式选项之前，因为它的运算符比乘法和加法都有更高的优先级。合并后的语法如下所示：

expr : expr '^'<assoc=right> expr    // 运算符是右结合的
     | expr '*' expr                 // 匹配由“*”运算符连接的子表达式
     | expr '+' expr                 // 匹配由“+”运算符连接的子表达式
     | INT                           // 匹配简单整数
     ;

不像其它常规的语法分析器生成器那样，ANTLR v4是可以处理直接左递归的。左递归规则是指直接或者间接调用在选项左边缘的自身的规则。规则expr是直接左递归的，因为除INT选项外的其它所有选项都开始于规则expr自身的引用。如果规则expr的引用处在某些选项的右边缘，那么它就是右递归的。虽然ANTLR v4可以处理直接左递归，但它不能处理间接左递归。这意味着我们不能把expr因子化为语法等效规则。

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

ANTLR v4可以简化直接左递归的表达式规则的工作。这种新的机制不仅更有效率，而且表达式规则也更小和更容易理解。