7

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 で次のエラーが表示されます。

[致命的] alt 1、2 から到達可能な再帰的なルール呼び出しにより、ルール アトムに非 LL(*) 決定があります。左因数分解するか、構文述語を使用するか、backtrack=true オプションを使用して解決します。

再帰を削除することでこれに対処したいのですが、左再帰を削除する方法に関するウィキペディアの説明から自分のものに移行できないようです。

この文法を使用する際に、abc という名前の変数に値を代入するstatementなどの入力でルートとして使用したい場合があります。また、文法を使用して、 などの入力をルートとabc = 2 + 3する式を評価したい場合もあります。@Bart の回答をモデルとして使用しようとすると、 で使用される文法の部分を で使用される部分とマージしようとするまではうまくいきました。どちらも を使用できるはずですが、この左再帰エラーで立ち往生しています。booleanabc > 3 and (xyz < 5 or xyz > 10)statementbooleanexpression

では、括弧を処理し、左再帰の問題を回避するにはどうすればよいでしょうか?

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 に答える