6

我正在编写一个语法来处理标量和向量表达式。下面的语法被简化以显示我遇到的问题，其中标量表达式可以从向量导出，向量可以从标量导出。例如，向量可以是文字[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，反之亦然，但同时它应该是确定性的。

我将如何重构此语法以避免相互（间接）左递归？我可以扩展其中一个术语 inplace，但这会在完整语法中引入大量重复，其中向量和标量有更多替代方案。我也可以将语法重构为具有主要表达式，但我不想允许scalar '*' scalar作为有效的vector替代方案。还有其他选择吗？

4

2 回答 2

4

AFAIK，除了扩展以消除间接递归规则之外，别无他法：

expression
    : scalar
    | vector
    ;

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

vector
    : '[' Integer ',' Integer ',' Integer ']'
    | scalar '*' vector
    ;
于 2013-12-26T22:42:15.087 回答
-1 
scalar
    : Integer
    | vector '[' Integer ']'
    ;

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

给出你可以写一个表达式

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

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

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

于 2013-12-26T21:56:36.260 回答