Помогите с левым факторингом грамматики для удаления левой рекурсии

У меня есть небольшой настраиваемый язык сценариев, и я пытаюсь обновить его, чтобы разрешить такие логические выражения, как a> 2 и a> 2 и (b 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 или (b , находится в комментариях -out в правиле атома . Когда я раскомментирую эту строку и включаю ее в грамматику, ANTLR выдает мне эту ошибку:

[фатальный] атом правила имеет решение не-LL (*) из-за рекурсивных вызовов правил, доступных из alts 1,2. Разрешить с помощью левостороннего факторинга, синтаксических предикатов или опции backtrack = true.

Я хотел бы решить эту проблему, удалив рекурсию, но, похоже, я не могу перейти от описания Википедии о том, как удалить левую рекурсию в мои собственные.

При использовании этой грамматики я иногда хочу использовать оператор в качестве корня с такими входными данными, как abc = 2 + 3 , который присваивает значение переменной с именем abc. В других случаях я хочу использовать грамматику для оценки выражения с логическим в качестве корня с такими входными данными, как abc> 3 и (xyz 10) . Когда я попытался использовать ответ @Bart в качестве модели, он работал нормально, пока я не попытался объединить части грамматики, используемые оператором , с частями, используемыми в логическом . Оба они должны иметь возможность использовать выражение , но именно здесь я застрял с этой ошибкой левой рекурсии.

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

7
задан Chris Farmer 8 July 2011 в 23:09
поделиться