Как правильно добавить новые токены (переписать), чтобы создать узлы AST, которые не находятся на входе? - PullRequest
Новая
       1

Как правильно добавить новые токены (переписать), чтобы создать узлы AST, которые не находятся на входе?

3 голосов
/ 15 июня 2011

У меня есть довольно базовая математическая грамматика выражений для ANTLR, и здесь интерес представляет обработка подразумеваемого оператора * в скобках, например, (2-3)(4+5)(6*7) на самом деле должно быть (2-3)*(4+5)*(6*7).

Учитывая ввод (2-3)(4+5)(6*7) Я пытаюсь добавить отсутствующий оператор * в дерево AST при синтаксическом анализе, в следующей грамматике я думаю, что мне удалось этого добиться, но мне интересно,это правильный, самый элегантный способ?

grammar G; 

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

tokens {
  ADD = '+' ;
  SUB = '-' ;
  MUL = '*' ;
  DIV = '/' ;
  OPARN = '(' ;
  CPARN = ')' ;
}

start
    : expression EOF!
    ;

expression
    : mult (( ADD^ | SUB^ ) mult)*
    ;

mult
   : atom (( MUL^ | DIV^) atom)*    
   ;

atom
   : INTEGER
   | (
       OPARN  expression CPARN -> expression
     )

     (
       OPARN  expression CPARN -> ^(MUL expression)+
     )*  
   ;


INTEGER : ('0'..'9')+ ;
WS  : (' ' | '\t' | '\n' | '\r' | '\f')+ {$channel = HIDDEN;};

Эта грамматика выводит правильное дерево AST в ANTLRworks:

AST Output

Я только начинаю разбираться с анализом и ANTLR, не так много опыта, поэтому обратная связь с очень ценится!

Спасибо заранее!Карл

1 Ответ

3 голосов
/ 15 июня 2011

Прежде всего, вы проделали большую работу, учитывая тот факт, что вы никогда раньше не использовали ANTLR.

Вы можете опустить language=Java и ASTLabelType=CommonTree, которые являются значениями по умолчанию. Так что вы можете просто сделать: 

options {
  output=AST;
}

Кроме того, вам не нужно указывать корневой узел для каждого оператора отдельно. Так что вам не нужно делать: 

(ADD^ | SUB^)

но следующее: 

(ADD | SUB)^

будет достаточно. Имея только два оператора, разница невелика, но при реализации реляционных операторов (>=, <=, > и <) последние немного проще.

Теперь для вас AST: вы, вероятно, захотите создать бинарное дерево: таким образом, все внутренние узлы являются операторами, а листья будут операндами, что значительно упрощает фактическую оценку ваших выражений. Чтобы получить двоичное дерево, вам нужно немного изменить правило atom: 

atom
   : INTEGER
   | (
       OPARN  expression CPARN -> expression
     )
     (
       OPARN  e=expression CPARN -> ^(MUL $atom $e)
     )*  
   ;

, который выдает следующий AST при вводе "(2-3)(4+5)(6*7)":

enter image description here

(изображение предоставлено: graphviz-dev.appspot.com )

Файл DOT был сгенерирован со следующим тестовым классом: 

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

public class Main {
  public static void main(String[] args) throws Exception {
    GLexer lexer = new GLexer(new ANTLRStringStream("(2-3)(4+5)(6*7)"));
    GParser parser = new GParser(new CommonTokenStream(lexer));
    CommonTree tree = (CommonTree)parser.start().getTree();
    DOTTreeGenerator gen = new DOTTreeGenerator();
    StringTemplate st = gen.toDOT(tree);
    System.out.println(st);
  }
}
...