7

我有一个小的自定义脚本语言，我正在尝试更新它以允许布尔表达式，例如a > 2and 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');

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

[致命] 规则原子具有非 LL(*) 决策，因为可以从 alts 1,2 访问递归规则调用。通过左分解或使用句法谓词或使用 backtrack=true 选项来解决。

我想通过删除递归来解决这个问题，但我似乎无法从维基百科关于如何删除左递归的描述过渡到我自己的东西。

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

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

4

1 回答 1

11

布尔表达式与加法和乘法表达式相同，因此不应与它们分开。以下是如何解释所有类型的表达式：

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})

进入以下解析树：

在此处输入图像描述

于 2011-07-08T19:41:56.303 回答