帮助对语法进行左分解以消除左递归 [英] Help with left factoring a grammar to remove left recursion

问题描述

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

I have a small custom scripting language, and I am trying to update it to allow boolean expressions such as a > 2 and a > 2 and (b < 3 or c > 5). It's the parenthetical expressions that I am having trouble with here.

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

Here is a (edited since the original post based on the answer from @Bart Kiers) full grammar that exhibits the problem. This is a pared-down version of my actual grammar, but the problem occurs here too.

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 或 (b <3) 位于 atom 规则中注释掉的行中.当我取消注释这一行并将其包含在语法中时，ANTLR 给了我这个错误:

My attempt to accommodate parenthetical boolean expressions such as a > 2 or (b < 3) is in the commented-out line in the atom rule. When I uncomment this line and include it in the grammar, ANTLR gives me this error:

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

[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.

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

I would like to address this by removing the recursion, but I can't seem to make the transition from the Wikipedia description on how to remove left recursion to my own stuff.

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

In using this grammar, I want sometimes to use statement as a root with input such as abc = 2 + 3, which assigns a value to a variable named abc. Other times I want to use the grammar to evaluate an expression with boolean as the root with input such as abc > 3 and (xyz < 5 or xyz > 10). When I tried to use @Bart's answer as a model, it worked fine until I tried to merge the parts of the grammar used by statement with the parts used by boolean. They should both be able to use an expression, but that's where I'm stuck with this left recursion error.

那么，如何既处理括号又避免左递归问题?

So, how can I both handle parentheses and avoid the left recursion problem?

推荐答案

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

Boolean expressions are just the same as the additive- and multiplicative expression, and should therefore not be separated from them. Here's how to account for all types of expressions:

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

进入以下解析树:

这篇关于帮助对语法进行左分解以消除左递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！