在 ANTLR 中是否可以在所有情况下消除左递归？

Question

假设我有以下内容

语法#1

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

然后变成了这个

语法 #2

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

但我仍然不明白这将如何解决问题？在语法#1 中我可以表达

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
 ;

这将使 AND 表达式的优先级高于 OR 表达式。

像这样解析输入：true and ((false or true) and true or false) 产生以下解析树：

在 ANTLR 中是否可以在所有情况下消除左递归？

Can left recursion be eliminated in all cases in ANTLR?

antlr

antlr4