Устранение левой рекурсии из этой странной грамматики выражения

Question

Я пытаюсь написать грамматику выражений, в которой есть 3 оператора "+", "-" и "/". Оператор умножения подразумевается сопоставлением, как в:

(1 + 2) (3 + 4 5)

Вот грамматика:

S -> A ('+' A) *

A -> B ('-' B) *

B -> C ('/' C) *

C -> D (D) *

D -> ID | Num | '(' S ')'

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

C -> D ('*' D) *

Тогда ошибка устранена. Я сбит с толку. Хотелось бы помочь!

Answer 1

Я ничего не знаю о Xtext, но у Antlr 4 нет проблем с этой грамматикой:

grammar Expr; 
s: a ('+' a)* ;
a: b ('-' b)* ;
b: c ('/' c)* ;
c: d ( d )* ;
d: ID | NUM |'(' s ')' ;
ID: [a-z][a-z0-9]* ;
NUM: [0-9]+ ;
WS: [ \t\r\n]+ -> skip ;

Когда я собираю и запускаю ваш пример (1+2)(3+4 5) Я получаю это дерево разбора:

Возможно, Xtext использует старую версию Antlr. Это отличная программа, но в старых версиях она не идеальна. Эта грамматика не является леворекурсивной по стандартному определению. Возможно, Antlr преобразует ее в более простую грамматику, которая остается рекурсивной, но это будет ошибкой, которая, по-видимому, исправлена.

Поэтому, если мои предположения верны, вы будете успешны со следующей явно "упрощенной" грамматикой:

grammar Expr; 
s: a ap ;
ap: '+' a ap | /* eps */ ;
a: b bp ;
bp: '-' b bp | /* eps */ ;
b: c cp ;
cp: '/' c cp | /* eps */ ;
c: d dp ;
dp: d dp | ;
d: ID | NUM |'(' s ')' ;
ID: [a-z][a-z0-9]* ;
NUM: [0-9]+ ;
WS: [ \t\r\n]+ -> skip ;

Новое дерево разбора: