ANTLR присваивание выражения неоднозначности - PullRequest
Новая
       6

ANTLR присваивание выражения неоднозначности

3 голосов
/ 09 сентября 2011

Следующая грамматика работает, но также выдает предупреждение:

test.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 слева, таким образом, делая мои намерения ясными и заставляя замолчатьпредупреждение?

1 Ответ

5 голосов
/ 09 сентября 2011

Чарльз писал:

Как я могу явно сказать ANTLR, что я хочу, чтобы он создал AST слева, таким образом, разъясняя мои намеренияи отключение предупреждения?

Не следует создавать два отдельных правила для assign и add.Как ваши правила сейчас, assign имеет приоритет над add, который вы не хотите: они должны иметь равный приоритет, глядя на ваш желаемый AST.Итак, вам нужно заключить все операторы +, - и = в одно правило: 

program
  :  expr ';'!
  ;

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

Но теперь грамматика все еще неоднозначна.Вам нужно «помочь» синтаксическому анализатору выйти за пределы этой двусмысленности, чтобы убедиться, что на самом деле operator expr впереди при разборе (('+' | '-' | '=') expr)*.Это можно сделать с помощью синтаксического предиката , который выглядит следующим образом: 

(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:

enter image description here

, который создается без любых предупреждений от ANTLR.

...