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！）。这就是歧义（在你的语法中，还有很多很多）。第二部分通知您，由于这种歧义，生成的解析器将无法采用第二种选择（该路径被禁用）。

另一件事：通过在同一个备选方案中匹配所有运算符，您无法使*优先级高于-. 所有的右递归产生式都使语法难以理解。我会这样做：

// ...

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

歧义在于第三个替代方案exprPrime将匹配任何东西- 空规则总是成功并且永远不会推进输入。为了消除歧义，您可以从定义中删除该替代项，并将所有出现的 替换exprPrime为exprPrime?。

于 2012-04-26T17:30:38.357 回答