ANTLR4 中交替与排序的优先级

Question

我认为在 ANTLR4 解析器中排序（由子规则的顺序隐式给出）比交替（由 | 字符显式给出）具有更高的优先级，这意味着

a : x | y z ;

在语义上与

相同

a : x | ( y z) ;

查看 ANTLR4 书籍并进行一般搜索，我找不到对此的明确说明，但它似乎是合理的，但是给定了规则

expression :
        pmqident
    |
        constant 
    | 
[snip]
    | 
        '(' scalar_subquery ')' 
    |
        unary_operator expression   // this is unbracketed
    |
        expression binary_operator expression
[snip]
    ;

我给它喂这个select - 2 / 3我得到这个解析树

而如果我只是在 unary_operator expression 周围添加方括号并且完全不改变任何其他内容，就可以得到这个

expression :
[snip]
        '(' scalar_subquery ')' 
    |
        ( unary_operator expression )   // brackets added here
    |
        expression binary_operator expression
[snip]
    ;

并给它相同的SQL，我明白了

我误会了什么？

（顺便说一句，将“- 2 / 3”解析为“（-（2 / 3））”实际上是我想要的。这就是 MSSQL 的做法。疯了世界）

------

好的，要重现（对我有用），不是完全最小化而是大量剥离的代码。文件名为 MSSQL.g4:

grammar MSSQL;

expression :
        constant 
    |
        unary_operator expression  // bracket/unbracket this
    |
        expression binary_operator expression  
    ;

constant : INTEGER_CONST ;

INTEGER_CONST : [0-9]+ ;

binary_operator :
        arithmetic_operator
    ;

arithmetic_operator :
        subtract
    |
        divide
    ;

add_symbol : PLUS_SIGN ;
subtract   : MINUS_SIGN ;
divide     : DIVIDE_SIGN ;

unary_operator :
        SIGN
    ;

SIGN : PLUS_SIGN | MINUS_SIGN ;

DIVIDE_SIGN : '/' ;
PLUS_SIGN  : '+' ;
MINUS_SIGN : '-' ;

SKIPWS : [ \t\r\n]+ -> skip ; // skip spaces, tabs, newlines

编译它的 DOS crud（给出相关部分）：

set CurrDir=%~dp0
set CurrDir=%CurrDir:~0,-1%
cd %CurrDir%

java  org.antlr.v4.Tool  -Werror  -o %CurrDir%\MSSQL  MSSQL.g4
IF %ERRORLEVEL% NEQ 0 goto problem

javac  %CurrDir%\MSSQL\MSSQL*.java
IF %ERRORLEVEL% NEQ 0 goto problem

cd ./MSSQL
echo enter sql...
java org.antlr.v4.gui.TestRig MSSQL expression -gui -trace  -tokens

输入是- 2 / 3

运行在win2k8R2上，位版本如下

C:\Users\jan>java -version
java version "1.8.0_65"
Java(TM) SE Runtime Environment (build 1.8.0_65-b17)
Java HotSpot(TM) 64-Bit Server VM (build 25.65-b01, mixed mode)

C:\Users\jan>java  org.antlr.v4.Tool
ANTLR Parser Generator  Version 4.5.1

还需要什么吗？任何人都可以复制吗？

坦率地说，我很难相信这是一个错误。就是太基础了。

仅供参考，我发现这最初不是通过 bracketing/unbracketing 而是通过将子规则的主体提升到规则中，并注意到行为发生了变化。

Answer 1

此答案是在 antlr/antlr4#564 未修复的情况下编写的。

在代码生成过程中，ANTLR 在重写左递归规则以在递归下降解析器中工作时寻找一些特定模式。

考虑以下规则：

expression
  : INT
  | '++' expression
  | expression '++'
  | expression '+' expression
  ;

后缀： 顶级替代方案，以递归调用开始。在示例中，备选方案 expression '++' 属于此类。
前缀： 顶级替代方案，结束递归调用。在示例中，备选方案 '++' expression 属于此类。
二进制： 顶级替代方案，以递归调用开始和结束。在示例中，备选方案 expression '+' expression 属于此类。
其他：其他。在示例中，备选方案 INT 属于此类。

匹配这些模式时，不执行任何简化。这包括删除其他不必要的括号，这是问题 antlr/antlr4#564.

的基础

通过在左递归规则中将顶级备选方案括起来，您可以强制将备选方案视为 Other。对于通常为 Suffix 或 Binary 的替代项，由于未消除左递归，这会导致编译错误。对于 Prefix 替代项（您拥有），语法仍然可以编译但会更改行为，因为替代项被视为主要表达式而不是覆盖其在运算符优先顺序中的原始位置的运算符。

请注意，在已经位于 Other 类别中的顶级备选方案周围加上括号根本不会改变行为。同样，在非左递归规则中将替代项括起来也不会改变行为。

ANTLR4 中交替与排序的优先级

Precedence of alternation vs sequencing in ANTLR4

antlr4

------