antlr - 帮助对语法进行左分解以消除左递归

Question

我有一个小的自定义脚本语言，我正在尝试更新它以允许 bool 表达式，例如 a > 2和 a > 2 and (b < 3 or c > 5) .这是我在这里遇到问题的括号表达式。

这是一个(根据@Bart Kiers 的回答从原始帖子开始编辑)展示问题的完整语法。这是我实际语法的精简版，但问题也出现在这里。

grammar test;


options {
    language = 'JavaScript'; 
    output = AST;
} 


statement 
    :   value_assignment_statement  
        EOF
    ;


value_assignment_statement 
    :   IDENT
        '='
        expression                      
    ;

value_expression 
    :   value_list_expression           
    |   IDENT                           
    ;


value_list_expression 
    :   value_enumerated_list       
    ;


value_enumerated_list : '{' unary+ '}'
    ;



term 
    :   LPAREN expression RPAREN        
    |   INTEGER                         
    |   value_expression                
    ;

unary : ( '+' | '-' )* term
    ;

mult :  unary ( ('*' | '/') unary)*
    ;

expression : mult ( ('+' | '-') mult )*
    ;


boolean 
    :   boolean_expression
        EOF
    ;

boolean_expression
    :   boolean_or_expression
    ;

boolean_or_expression 
    :   boolean_and_expression (OR boolean_and_expression)*
    ;

boolean_and_expression 
    :   boolean_rel_expression (AND boolean_rel_expression)*
    ;

boolean_rel_expression
    :   boolean_neg_expression relational_operator boolean_neg_expression
    ;

boolean_neg_expression 
    :   (NOT)? atom
    ;

atom
    :   LPAREN boolean_expression RPAREN
    //| expression
    ;


relational_operator : '=' | '>' | '<';


LPAREN      :   '(';
RPAREN      :   ')';
AND         :   'and';
OR          :   'or';
NOT         :   'not';
IDENT       :   LETTER LETTER+;
INTEGER     :   DIGIT+;
WS          :   (' ' | '\n' | '\r' | '\t')+     { $channel = HIDDEN; };

fragment DIGIT      : '0'..'9';
fragment LETTER     : ('a'..'z' | 'A'..'Z');

我尝试容纳带括号的 bool 表达式，例如 a > 2 or (b < 3)位于 atom 中注释掉的行中规则。当我取消注释这一行并将其包含在语法中时，ANTLR 给了我这个错误:

[fatal] rule atom has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2. Resolve by left-factoring or using syntactic predicates or using backtrack=true option.

我想通过删除递归来解决这个问题，但我似乎无法从 Wikipedia description on how to remove left recursion 进行转换到我自己的东西。

在使用这个语法时，我有时想使用 statement作为具有输入的根，例如 abc = 2 + 3 ，它为名为 abc 的变量赋值。其他时候我想使用语法来评估表达式 boolean作为输入的根，例如 abc > 3 and (xyz < 5 or xyz > 10) .当我尝试使用@Bart 的答案作为模型时，它运行良好，直到我尝试合并 statement 使用的语法部分与 boolean 使用的零件.他们都应该能够使用 expression ，但这就是我遇到这个左递归错误的地方。

那么，我怎样才能既处理括号又避免左递归问题呢？

Answer 1

bool 表达式与加法和乘法表达式相同，因此不应与它们分开。以下是解释所有类型表达式的方法:

grammar test;

parse
  :  expression EOF
  ;

expression 
  :  or
  ;

or
  :  and (OR and)*
  ;

and
  :  rel (AND rel)*
  ;

rel
  :  add (('=' | '>' | '<') add)*
  ;

add
  :  mult (('+' | '-') mult)*
  ;

mult
  :  unary (('*' | '/') unary)*
  ;

unary 
  :  '-' term
  |  '+' term
  |  NOT term
  |  term
  ;

term 
  :  INTEGER  
  |  IDENT       
  |  list
  |  '(' expression ')'
  ;

list 
  :  '{' (expression (',' expression)*)? '}'
  ;

AND     :  'and';
OR      :  'or';
NOT     :  'not';
IDENT   :  LETTER LETTER*;
INTEGER :  DIGIT+;
WS      :  (' ' | '\n' | '\r' | '\t')+  { $channel = HIDDEN; };

fragment DIGIT   : '0'..'9';
fragment LETTER  : ('a'..'z' | 'A'..'Z');

这将解析示例输入:

abc > 3 and (xyz < 5 or xyz > {1, 2, 3})

进入以下解析树: