如何避免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 给了我错误:以下规则集是相互左递归的 [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 '*' 标量 作为有效的 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屋！