Как избежать взаимной левой рекурсии в ANTLR 4

Я пишу грамматику для обработки скалярных и векторных выражений. Приведенная ниже грамматика упрощена, чтобы показать мою проблему, когда скалярное выражение может быть получено из вектора, а вектор может быть получен из скаляра. Например, вектор может быть литералом [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 . Есть ли другие варианты?


antlr4 left-recursion
person Rangi Keen    schedule 26.12.2013    source источник

Ответы (2)


arrow_upward
4
arrow_downward

AFAIK, нет другого способа обойти это, кроме как расширить, чтобы исключить косвенное рекурсивное правило:

expression
    : scalar
    | vector
    ;

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

vector
    : '[' Integer ',' Integer ',' Integer ']'
    | scalar '*' vector
    ;
person Bart Kiers    schedule 26.12.2013
comment
Не могли бы вы избежать дублирования, добавив дополнительное правило? т.е. vector_literal: '['Integer, Integer, Integer ']' и использовать его в scalar и vector? scalar: vector_literal '[' Integer ']' и т. д. - person Milan Iliev; 09.10.2015

arrow_upward
-1
arrow_downward 

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

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

дает, что вы можете написать выражения

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

который будет отображать переполнение стека синтаксического анализатора для java и других языков с ограниченной глубиной стека.

Я думаю, вам следует создать другое грамматическое правило для векторного поиска, это не скаляр, это просто результат скаляра, но это должно обрабатываться при обработке дерева синтаксического анализатора, а не в ANTLR.

person claj    schedule 26.12.2013
comment
Почти любая грамматика может привести к неограниченной глубине выражения. Возьмем, к примеру, самореферентное правило scalar : Integer | scalar '*' scalar;. Это также может быть расширено до любой длины 1 * 2 * 3 * 4 * ... * n. - person Rangi Keen; 27.12.2013