去除间接左递归（我不懂形式符号）

Question

我已经尝试寻找我的解决方案的答案，但我似乎无法理解一般化的解决方案。我无法弄清楚哪些元素映射到大写字母，哪些应该用小写字母表示，这无济于事。

这是我在 Antlr 中的语法的一部分：

expression
    : literal
    | unaryExpression
    | binaryExpression
    | priorityExpression
    | invocation
    ;

binaryExpression: expression binaryOperator expression;

binaryOperator
    : ADD
    | SUBTRACT
    | DIVIDE
    | CONCAT
    | EQUALS
    | NOT_EQUALS
    | LESS_THAN
    | GREATER_THAN
    | MULTIPLY
    ;

我将如何删除 binaryExpression 中的递归？

Answer 1

只需删除 binaryExpression 并直接在 expression 中使用 expression binaryOperator expression:

expression
    : literal
    | unaryExpression
    | expression binaryOperator expression
    | priorityExpression
    | invocation
    ;

binaryOperator
    : ADD
    | SUBTRACT
    | DIVIDE
    | CONCAT
    | EQUALS
    | NOT_EQUALS
    | LESS_THAN
    | GREATER_THAN
    | MULTIPLY
    ;

编辑

but now I lose the binary expression node in the AST and I have to detect it later in code

然后使用labels:

expression
    : literal                              #literalExpr
    | unaryExpression                      #unaryExpr
    | expression binaryOperator expression #binaryExpr
    | priorityExpression                   #priorityExpr
    | invocation                           #invocationExpr
    ;

binaryOperator
    : ADD
    | SUBTRACT
    | DIVIDE
    | CONCAT
    | EQUALS
    | NOT_EQUALS
    | LESS_THAN
    | GREATER_THAN
    | MULTIPLY
    ;

Also, I'd like to gain a better understanding of how to remove this recursion instead of offloading it to Antlr

你不能。 ANTLR 根本不允许这种间接的左递归规则。只能直接左递归。