2

私は Java のサブセット用の文法を作成していますが、私の文法が ANTLR によってあいまいであると見なされるという問題が発生しているようです (少なくとも、それがエラーの背後にある理由だと思います)。

これが私の文法の関連部分です：

expr : (op=MINUS | op=NOT) expr exprPrime      -> ^(Expr $op expr exprPrime)
     | NEW ID OPEN_PAREN CLOSE_PAREN exprPrime -> ^(Expr NEW ID OPEN_PAREN CLOSE_PAREN exprPrime)
     | ID exprPrime                            -> ^(Expr ID exprPrime)
     | THIS exprPrime                          -> ^(Expr THIS exprPrime)
     | INTEGER exprPrime                       -> ^(Expr INTEGER exprPrime)
     | NULL exprPrime                          -> ^(Expr NULL exprPrime)
     | TRUE exprPrime                          -> ^(Expr TRUE exprPrime)
     | FALSE exprPrime                         -> ^(Expr FALSE exprPrime)
     | OPEN_PAREN expr CLOSE_PAREN exprPrime   -> ^(Expr OPEN_PAREN expr CLOSE_PAREN exprPrime)
     ;

// remove left recursion via exprPrime
exprPrime : (op=PLUS | op=MINUS | op=MULT | op=DIV | op=LT | op=LEQ | op=GT | op=GEQ | op=EQ | op=NEQ | op=AND | op=OR | op=NOT) expr exprPrime
               -> ^(ExprPrime $op expr exprPrime)
          | DOT ID OPEN_PAREN (expr (COMMA expr)*)? CLOSE_PAREN exprPrime
               -> ^(ExprPrime DOT ID OPEN_PAREN (expr (COMMA expr)*)? CLOSE_PAREN exprPrime)
          |    
               -> ^(Epsilon)
          ;

/*------------------------------------------------------------------
 * LEXER RULES
 *------------------------------------------------------------------*/

CLASS         : 'class'   ;
PUBLIC        : 'public'  ;
STATIC        : 'static'  ;
EXTENDS       : 'extends' ;
NEW           : 'new'     ;
THIS          : 'this'    ;
NULL          : 'null'    ;
IF            : 'if'      ;
ELSE          : 'else'    ;
WHILE         : 'while'   ;
MAIN          : 'main'    ;
TRUE          : 'true'    ;
FALSE         : 'false'   ;
RETURN        : 'return'  ;
SYSO          : 'System.out.println' ;

OPEN_BRACKET  : '{' ;
CLOSE_BRACKET : '}' ;
OPEN_SQUARE   : '[' ;
CLOSE_SQUARE  : ']' ;
OPEN_PAREN    : '(' ;
CLOSE_PAREN   : ')' ;

ASSIGN        : '=' ;
COMMA         : ',' ;
DOT           : '.' ;
SEMICOLON     : ';' ;

STRING_TYPE   : 'String'  ;
INTEGER_TYPE  : 'int'     ;
VOID_TYPE     : 'void'    ;
BOOLEAN_TYPE  : 'boolean' ;

PLUS          : '+'  ;
MINUS         : '-'  ;
MULT          : '*'  ;
DIV           : '/'  ;
LT            : '<'  ;
LEQ           : '<=' ;
GT            : '>'  ;
GEQ           : '>=' ;
EQ            : '==' ;
NEQ           : '!=' ;
AND           : '&&' ;
OR            : '||' ;
NOT           : '!'  ;

ID            : LETTER (LETTER | DIGIT)* ;
INTEGER       : (NON_ZERO_DIGIT DIGIT*) | ZERO ;

WHITESPACE    : ('\t' | ' ' | '\r' | '\n'| '\u000C')+ { $channel = HIDDEN; } ;
COMMENT       : (('/*' .* '*/') | ('//' .* '\n')) { $channel = HIDDEN; } ;

fragment ZERO            : '0' ;
fragment DIGIT           : '0'..'9' ;
fragment NON_ZERO_DIGIT  : '1'..'9' ;
fragment LETTER          : 'a'..'z' | 'A'..'Z' ;

そして、文法を作成するときに発生するエラーは次のとおりです。

warning(200): MiniJava.g:101:11: Decision can match input such as "NEQ" using multiple alternatives: 1, 3
As a result, alternative(s) 3 were disabled for that input
warning(200): MiniJava.g:101:11: Decision can match input such as "EQ" using multiple alternatives: 1, 3
As a result, alternative(s) 3 were disabled for that input
warning(200): MiniJava.g:101:11: Decision can match input such as "MULT" using multiple alternatives: 1, 3
As a result, alternative(s) 3 were disabled for that input
warning(200): MiniJava.g:101:11: Decision can match input such as "DIV" using multiple alternatives: 1, 3
As a result, alternative(s) 3 were disabled for that input
warning(200): MiniJava.g:101:11: Decision can match input such as "GEQ" using multiple alternatives: 1, 3
As a result, alternative(s) 3 were disabled for that input
warning(200): MiniJava.g:101:11: Decision can match input such as "NOT" using multiple alternatives: 1, 3
As a result, alternative(s) 3 were disabled for that input
warning(200): MiniJava.g:101:11: Decision can match input such as "LT" using multiple alternatives: 1, 3
As a result, alternative(s) 3 were disabled for that input
warning(200): MiniJava.g:101:11: Decision can match input such as "LEQ" using multiple alternatives: 1, 3
As a result, alternative(s) 3 were disabled for that input
warning(200): MiniJava.g:101:11: Decision can match input such as "DOT" using multiple alternatives: 2, 3
As a result, alternative(s) 3 were disabled for that input
warning(200): MiniJava.g:101:11: Decision can match input such as "OR" using multiple alternatives: 1, 3
As a result, alternative(s) 3 were disabled for that input
warning(200): MiniJava.g:101:11: Decision can match input such as "PLUS" using multiple alternatives: 1, 3
As a result, alternative(s) 3 were disabled for that input
warning(200): MiniJava.g:101:11: Decision can match input such as "AND" using multiple alternatives: 1, 3
As a result, alternative(s) 3 were disabled for that input
warning(200): MiniJava.g:101:11: Decision can match input such as "MINUS" using multiple alternatives: 1, 3
As a result, alternative(s) 3 were disabled for that input
warning(200): MiniJava.g:101:11: Decision can match input such as "GT" using multiple alternatives: 1, 3
As a result, alternative(s) 3 were disabled for that input

行番号はすべて、exprPrime の定義を含む行を指しています (簡潔にするために、上の文法のほとんどを省略しました。さらに投稿する必要がある場合はお知らせください)。exprPrime 自体は、'expr' での左再帰を回避するために作成されました。

あいまいさを取り除くために文法を変更する方法はありますか? あいまいさが何であるかを理解しているかどうかさえわかりません。

4

2 に答える 2

3

文法を最小化して、あいまいさを示すことができます。

grammar T;                          // line 1
                                    //      2
expr                                //      3 
 : MINUS expr exprPrime             //      4
 ;                                  //      5
                                    //      6
exprPrime                           //      7
 : MINUS expr exprPrime             //      8
 | // epsilon                       //      9
 ;                                  //      10
                                    //      11
MINUS   : '-';                      //      12
INTEGER : '0'..'9'+;                //      13

この文法からパーサーを生成すると、次の警告が表示されます。

[20:38:15] warning(200): T.g:8:2: 
Decision can match input such as "MINUS" using multiple alternatives: 1, 2

As a result, alternative(s) 2 were disabled for that input
[20:38:15] error(201): T.g:8:2: The following alternatives can never be matched: 2

最初の部分は、文法の 8 行目で、生成されたパーサーがトークンに一致するために両方の「パス」を取ることができることを示していますMINUS(8 行目と 9 行目の両方の選択肢が一致しMINUSます!)。それがあいまいさです (そして、あなたの文法には、さらに多くの曖昧さがあります)。2 番目の部分は、このあいまいさのために、生成されたパーサーが 2 番目の選択肢を取ることができないことを通知します (そのパスは無効になっています)。

もう 1 つ: 同じ選択肢内のすべての演算子を一致させることにより*、たとえば-. そして、すべての正しい再帰的な生成は、文法を理解するのを難しくします. 代わりに次のようにします。

// ...

tokens {
  UNARY_MINUS;
  PARAMS;
  INVOKE;
}

parse
 : expr EOF
 ;

expr
 : or_expr
 ;

or_expr
 : and_expr (OR^ and_expr)*
 ;

and_expr
 : rel_expr (AND^ rel_expr)*
 ;

rel_expr
 : eq_expr ((LT | GT | LEQ | GEQ)^ eq_expr)?
 ;

eq_expr
 : add_expr ((EQ | NEQ)^ add_expr)?
 ;

add_expr
 : mult_expr ((PLUS | MINUS)^ mult_expr)*
 ;

mult_expr
 : unary_expr ((MULT | DIV)^ unary_expr)*
 ;

unary_expr
 : MINUS atom -> ^(UNARY_MINUS atom)
 | atom
 ;

atom
 : NEW ID OPEN_PAREN params CLOSE_PAREN -> ^(NEW ID params)
 | (ID -> ID) (invoke -> ^(ID invoke))?
 | THIS
 | INTEGER
 | NULL
 | TRUE
 | FALSE 
 | OPEN_PAREN expr CLOSE_PAREN -> expr
 ;

invoke
 : DOT ID OPEN_PAREN params CLOSE_PAREN invoke? -> ^(INVOKE ID params invoke?)
 ;

params
 : (expr (COMMA expr)*)? -> ^(PARAMS expr*)
 ;
// ...

あいまいさはなく、すべての演算子には適切な優先順位があります (OR最低であり、単項演算子が最高です (もちろん、アトムはさらに高くなります...))。"x.foo(9,y)&&(1==2||true)+2+3+4==333"ルールのように入力を解析するexprと、次の AST になります。

ここに画像の説明を入力

于 2012-04-26T19:07:37.523 に答える
0

あいまいさは、 will の 3 番目の選択肢が何exprPrimeにでも一致するという事実にあります。空のルールは常に成功し、入力を進めることはありません。あいまいさを排除するために、その代替を定義から削除し、出現するすべての を に置き換えることができます。exprPrimeexprPrime?

于 2012-04-26T17:30:38.357 に答える