Помогите с левым факторингом грамматики, чтобы удалить левую рекурсию - PullRequest
Новая
       73

Помогите с левым факторингом грамматики, чтобы удалить левую рекурсию

7 голосов
/ 08 июля 2011

У меня есть небольшой пользовательский язык сценариев, и я пытаюсь обновить его, чтобы разрешить логические выражения, такие как 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');

Моя попытка разместить в скобках логические выражения, такие как 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). Когда я пытался использовать ответ @ Барта в качестве модели, он работал нормально, пока я не попытался объединить части грамматики, используемые statement, с частями, используемыми boolean. Они оба должны иметь возможность использовать expression, но именно здесь я застрял с этой левой ошибкой рекурсии.

Итак, как мне справиться с круглыми скобками и избежать проблемы с левой рекурсией?

1 Ответ

11 голосов
/ 08 июля 2011

Булевы выражения точно такие же, как аддитивные и мультипликативные выражения, и поэтому не должны отделяться от них.Вот как можно учесть все типы выражений: 

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

в следующее дерево разбора:

enter image description here

...