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

Question

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

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

INT: [0-9]+;

WS : [ \t\r\n]+ -> 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 生成预期的解析树。