如何避免ANTLR 4中的相互左递归

Question

我正在写一个语法来处理标量和向量表达式.下面的语法被简化以显示我所遇到的问题,其中标量表达式可以从向量导出,并且向量可以从标量导出.例如,矢量可以是文字[1, 2, 3]或标量和矢量2 * [1, 2, 3](相当于[2, 4, 6])的乘积.标量可以是文字2或向量的索引[1, 2, 3][1](相当于2).

grammar LeftRecursion;

Integer
    : [0-9]+
    ;

WhiteSpace
    : [ \t\r\n]+ -> skip
    ;

input
    : expression EOF;

expression
    : scalar
    | vector
    ;

scalar
    : Integer
    | vector '[' Integer ']'
    ;

vector
    : '[' Integer ',' Integer ',' Integer ']'
    | scalar '*' vector
    ;

ANTLR4给了我错误:The following sets of rules are mutually left-recursive [scalar, vector].这是有道理的,因为scalar引用vector,反之亦然,但同时它应该是确定性的.

我如何重构这个语法以避免相互(间接)左递归？我可以扩展其中一个术语,但是这会在完整的语法中引入很多重复,其中有更多的矢量和标量替代品.我还可以重构语法以获得主表达式,但我不想允许scalar '*' scalar作为有效的vector替代方法.还有其他选择吗？

Answer 1

scalar
    : Integer
    | vector '[' Integer ']'
    ;

vector
    : '[' Integer ',' Integer ',' Integer ']'
    | scalar '*' vector
    ;

给出你可以写一个表达式

[i,i,i][i] * [i,i,i][i] * ... * [i,i,i]

这会导致 java 和其他堆栈深度有限的语言的解析器堆栈溢出。

我认为你应该为向量查找创建一个不同的语法规则，它不是一个标量，它只是产生一个标量，但这应该在解析器树处理中处理，而不是在 ANTLR 中处理。