parsing - ANTLR 赋值表达式消歧

Question

以下语法有效，但也会给出警告:

测试.g

grammar test;

options {
  language = Java;
  output = AST;
  ASTLabelType = CommonTree; 
}

program
  : expr ';'!
  ;

term: ID | INT
  ;

assign
  : term ('='^ expr)?
  ;

add : assign (('+' | '-')^ assign)*
  ;

expr: add
  ;

//   T O K E N S

ID  : (LETTER | '_') (LETTER | DIGIT | '_')* ;

INT : DIGIT+ ;

WS  :
    ( ' '
    | '\t'
    | '\r'
    | '\n'
    ) {$channel=HIDDEN;}
    ;

DOT : '.' ;

fragment
LETTER : ('a'..'z'|'A'..'Z') ;

fragment
DIGIT   : '0'..'9' ;

警告

[15:08:20] warning(200): C:\Users\Charles\Desktop\test.g:21:34: 
Decision can match input such as "'+'..'-'" using multiple alternatives: 1, 2

As a result, alternative(s) 2 were disabled for that input

再说一次，它确实按照我想要的方式生成一棵树:

Input: 0 + a = 1 + b = 2 + 3;

ANTLR produces  | ... but I think it
this tree:      | gives the warning
                | because it _could_
  +             | also be parsed this
 / \            | way:
0   =           |  
   / \          |           +     
  a   +         |         /   \   
     / \        |        +     3  
    1   =       |     /     \     
       / \      |    +       =    
      b   +     |   / \     / \   
         / \    |  0   =   b   2  
        2   3   |     / \         
                |    a   1        

我如何明确告诉 ANTLR 我希望它在左侧创建 AST，从而明确我的意图并消除警告？

Answer 1

Charles wrote:

How can I explicitly tell ANTLR that I want it to create the AST on the left, thus making my intent clear and silencing the warning?

您不应为分配和添加创建两个单独的规则。按照您现在的规则，assign 优先于您不希望的 add:通过查看您想要的 AST，它们应该具有相同的优先级。因此，您需要将所有运算符 +、- 和 = 包装在一条规则中:

program
  :  expr ';'!
  ;

expr
  :  term (('+' | '-' | '=')^ expr)*
  ;

但是现在语法仍然有歧义。您需要“帮助”解析器超越这种歧义，以确保在解析 (('+' | '-' | '=') expr 时确实前面存在 operator expr )*。这可以使用 syntactic predicate 来完成，看起来像这样:

(look_ahead_rule(s)_in_here)=> rule(s)_to_actually_parse

(( ... )=> 是谓词语法)

一个小演示:

grammar test;

options {
  output=AST;
  ASTLabelType=CommonTree; 
}

program
  :  expr ';'!
  ;

expr
  :  term ((op expr)=> op^ expr)*
  ;

op
  :  '+' 
  |  '-'
  |  '='
  ;

term
  :  ID 
  |  INT
  ;

ID  : (LETTER | '_') (LETTER | DIGIT | '_')* ;
INT : DIGIT+ ;
WS  : (' ' | '\t' | '\r' | '\n') {$channel=HIDDEN;};

fragment LETTER : ('a'..'z'|'A'..'Z');
fragment DIGIT  : '0'..'9';

可以使用以下类进行测试:

import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;
import org.antlr.stringtemplate.*;

public class Main {
  public static void main(String[] args) throws Exception {
    String source =  "0 + a = 1 + b = 2 + 3;";
    testLexer lexer = new testLexer(new ANTLRStringStream(source));
    testParser parser = new testParser(new CommonTokenStream(lexer));
    CommonTree tree = (CommonTree)parser.program().getTree();
    DOTTreeGenerator gen = new DOTTreeGenerator();
    StringTemplate st = gen.toDOT(tree);
    System.out.println(st);
  }
}

并且Main类的输出对应于以下AST:

其创建时没有来自 ANTLR 的任何警告。