如何避免ANTLR 4中的相互左递归 [英] How to avoid mutual left-recursion in ANTLR 4
问题描述
我正在编写一种语法来处理标量和向量表达式.下面的语法经过简化以显示我所遇到的问题,其中标量表达式可以从矢量导出,而矢量可以从标量导出.例如,向量可以是文字[1, 2, 3]
或标量与向量2 * [1, 2, 3]
的乘积(等效于[2, 4, 6]
).标量可以是文字2
或向量[1, 2, 3][1]
的索引(等效于2
).
I am writing a grammar to handle scalar and vector expressions. The grammar below is simplified to show the problem I have where a scalar expression can be derived from a vector and a vector can be derived from a scalar. For example, a vector could be a literal [1, 2, 3]
or the product of a scalar and a vector 2 * [1, 2, 3]
(equivalent to [2, 4, 6]
). A scalar could be a literal 2
or an index into a vector [1, 2, 3][1]
(equivalent to 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
,反之亦然,但是同时它应该是确定性的.
ANTLR4 gives me the error: The following sets of rules are mutually left-recursive [scalar, vector]
. This makes sense because scalar
references vector
and vice-versa, but at the same time it should be deterministic.
我将如何重构该语法以避免相互(间接)左递归?我可以扩展其中一个术语,但是这会在完整语法中引入很多重复之处,其中有更多替代选择用于向量和标量.我也可以重构语法以使其具有主表达式,但是我不想允许scalar '*' scalar
作为有效的vector
替代.还有其他选择吗?
How would I refactor this grammar to avoid the mutual (indirect) left-recursion? I could expand one of the terms inplace, but that would introduce a lot of duplication in the full grammar where there are more alternatives for vector and scalar. I could also refactor the grammar to have a primary expression, but I don't want to allow scalar '*' scalar
as a valid vector
alternative. Are there other options?
推荐答案
AFAIK不能解决,只能扩展以消除间接递归规则:
AFAIK, there is no way around it but to expand to eliminate the indirect recursive rule:
expression
: scalar
| vector
;
scalar
: '[' Integer ',' Integer ',' Integer ']' '[' Integer ']'
| scalar '*' vector '[' Integer ']'
| Integer
;
vector
: '[' Integer ',' Integer ',' Integer ']'
| scalar '*' vector
;
这篇关于如何避免ANTLR 4中的相互左递归的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!