在ANTLR中所有情况下都可以消除左递归吗? [英] Can left recursion be eliminated in all cases in ANTLR?

问题描述

说我有以下内容

语法 #1

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

然后变成了这个.

语法#2

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

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

but I still don't see how this would solve the problem? In Grammar #1 I can express

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

我可以用 Grammar #1 保持这样的链接.但我没有看到如何使用语法 #2 来实现这一点?

I can keep chaining like this with Grammar #1. But I am not seeing how to achieve this using grammar #2?

推荐答案

你可以这样写:

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 表达式具有更高的优先级.

This will keep AND expressions have a higher precedence than OR expressions.

像这样解析输入:true and ((false or true) and true or false) 导致以下解析树:

Parsing input like this: true and ((false or true) and true or false) results in the following parse tree:

这篇关于在ANTLR中所有情况下都可以消除左递归吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！