在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

我可以使用#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和((false或true)以及true或false)会产生以下解析树:

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

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