优先级，左递归以及相关性
用自顶向下的语法指定和通过手工的递归下降语法分析器识别表达式一直是个麻烦。首先是因为大部分自然语法是模糊的，其次是因为大部分自然语法规格使用一种被称为左递归的特殊类型递归。所以自顶向下的语法和语法分析器不能处理传统形式上的左递归。
为了阐明这个问题，设想一个算术表达式语言，它只有乘法和加法运算符以及整数。表达式是自相似的。也就是说，一个乘法表达式是由“*”运算符连接的两个子表达式。同样的，一个加法表达式是由“+”运算符连接的两个子表达式。我们也可以把整数看作表达式。整个语法规则看起来就像以下显示的那样：
问题是指定的规则可以像中间和右边语法分析树描绘的那样用两种方法解释1+2*3这样的输入。两者的解释是不同的，因为中间的树说加1到2乘3的结果上，而右边的树说3乘以1加2的结果。这是一个运算符优先级的问题，但常规语法根本没有指定优先级的方法。大部分语法工具使用额外的符号来指定运算符优先级。
与之相反的是，ANTLR解决二义性有利于首先给出的选项，隐式地允许我们指定运算符优先级。规则expr有一个乘法选项在加法选项之前，因此，ANTLR解决1+2*3的运算符二义性有利于乘法。
默认情况下，ANTLR从左到右结合运算符，然而某些像指数群这样的运算符则是从右到左。因此，我们必须使用选项assoc手动指定运算符记号上的相关性。这里是一个能正确地把输入
为了把所有这三个运算符合并成一条规则，我们把指数表达式选项放在其它表达式选项之前，因为它的运算符比乘法和加法都有更高的优先级。合并后的语法如下所示：
expr : expr '*' expr // 匹配由“*”运算符连接的子表达式
| expr '+' expr // 匹配由“+”运算符连接的子表达式
| INT // 匹配简单整数
;
2^3^4解释成2^(3^4)的表达式规则：
expr : expr '^'<assoc=right> expr // 运算符是右结合的
| INT
;
expr : expr '^'<assoc=right> expr // 运算符是右结合的
| expr '*' expr // 匹配由“*”运算符连接的子表达式
| expr '+' expr // 匹配由“+”运算符连接的子表达式
| INT // 匹配简单整数
;
expr : expo ; // 通过expo左递归地间接调用expr
expo : expr '^'<assoc=right> expr ;
正文到此结束
热门推荐
近期评论
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
搞个gitee的项目
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
