Может ли левая рекурсия быть устранена во всех случаях в ANTLR?

Question

говорят, что у меня есть следующая

грамматика # 1

expr:
    expr AND expr
    | expr OR expr
    | primary 
;

и превращена в это.

грамматика # 2

expr:
    andExpr
    | primary
;
andExpr: orExpr AND orExpr;
orExpr: ... OR ...;

но я до сих пор не понимаю, как это решит проблему? В грамматике # 1 я могу express

true and false and true and true or false
true or false and true

Я могу продолжать цепочку, как это с грамматикой # 1. Но я не вижу, как добиться этого с помощью грамматики № 2?

Answer 1

Вы могли бы написать это так:

grammar Test;

parse
 : expr EOF
 ;

expr
 : or_expr
 ;

or_expr
 : and_expr (OR and_expr)*
 ;

and_expr
 : primary (AND primary)*
 ;

primary
 : TRUE
 | FALSE
 | '(' expr ')'
 ;

TRUE  : 'true';
FALSE : 'false';
AND   : 'and';
OR    : 'or';

SPACES
 : [ \t\r\n] -> skip
 ;

Это сохранит выражения И имеет более высокий приоритет, чем выражения ИЛИ.

Синтаксический анализ ввода выглядит так: true and ((false or true) and true or false) приводит к следующему дерево разбора: