如何使用左递归和贪婪'?'运算符选择解析器规则优先级？

Question

以(几乎(教科书为例，我们希望乘法优先于加法，但也包括一个可选部分来匹配。

expr : expr '*' expr  ('ALSO')?
     | expr '+' expr
     | INT
     ;
INT: [0-9]+;
WS : [ trn]+ -> skip ;

当尝试语法时3 * 4 + 2我们得到一个意想不到的树，看起来像

                  expr:1
               /    |   
            expr:1  *   expr:2
              |         /  |  
              3    expr:1  +  expr:1
                     |           |
                     4           2

但是，当使用3 + 4 * 2时，我们得到了我所期望的

                  expr:1
               /    |   
            expr:1  +   expr:2
              |         /  |  
              3    expr:1  *  expr:1
                     |           |
                     4           2

此外，如果将可选令牌切换到第二行，我们每次都会得到预期的树。

expr : expr '*' expr
     | expr '+' expr ('ALSO')?
     | INT
     ;

我还尝试使用非贪婪运算符??，并定义词法分析器令牌，这样我们就不必担心由于隐式令牌而导致的排序的奇怪之处。

如何解释这种排序？

Answer 1

这看起来像一个错误。您可以在此处报告：https://github.com/antlr/antlr4/issues(如果尚未报告...我没有检查(

似乎一种解决方法是包含不包含ALSO令牌的额外替代方案：

expr : expr '*' expr 'ALSO'
     | expr '*' expr
     | expr '+' expr
     | INT
     ;

这会为 3 * 4 + 2 和 3 + 4 * 2 生成预期的解析树。