Antlr AST порождает (возможно) безумие - PullRequest
1 голос
/ 27 сентября 2010

Возможно ли следующее?Я хочу "перевернуть" входные данные, данные для antlr, и сделать каждый токен дочерним по отношению к предыдущему.

Итак, для ввода (Предположим, каждый токен отделен символом '.'):

Stack.Overflow.Horse

Мне бы хотелось, чтобы моя грамматика производила следующие AST:

Horse
  |---Overflow
         |---Stack

Пока мне удалось изменить узлы, но я не могу сделать их дочерними по отношению друг к другу.:

function
 : ID PERIOD function
   -> function ID
 | ID
 ;

ID  : 'a'..'z'*
    ;

1 Ответ

3 голосов
/ 27 сентября 2010

Я не думаю, что есть простой способ сделать это. Вы можете сделать свое правило так:

function
 : ID PERIOD function
   -> ^(function ID)
 | ID
 ;

но только последний узел становится корневым, а все остальные узлы - его дочерними. Например, следующий источник:

a.b.c.d.e

приведет к следующему дереву:

    e
 / / \ \
d c   b a

Я не вижу простого исправления, поскольку при первом разборе a.b.c.d.e, a будут ID и b.c.d.e рекурсивным вызовом function:

a.b.c.d.e
| +-----+
|    |
|    `-----> function
|
`----------> ID

, в результате чего b.c.d.e будет иметь a в качестве дочернего элемента. Когда b становится ID, он также добавляется как дочерний элемент рядом с a. В вашем случае a следует удалить как ребенка, а затем добавить в список детей b. Но AFAIK, это невозможно в ANLTR (по крайней мере, не в чистом виде внутри грамматики).


EDIT

Хорошо, в качестве обходного пути я задумал что-то элегантное, но это не сработало, как я надеялся. Таким образом, в качестве менее элегантного решения вы можете сопоставить узел last в качестве корня в правиле перезаписи:

function
  :  (id '.')* last=id -> ^($last)
  ;

и затем соберите все возможные предшествующие узлы (children) в List, используя оператор +=:

function
  :  (children+=id '.')* last=id -> ^($last)
  ;

и используйте пользовательский метод member в синтаксическом анализаторе, чтобы «вставить» эти children в корень дерева (переходя справа налево в вашем List!):

function
  :  (children+=id '.')* last=id {reverse($children, (CommonTree)$last.tree);} -> ^($last)
  ;

Небольшая демонстрация:

grammar ReverseTree;

options {
  output=AST;
}

tokens {
  ROOT;
}

@members {
  private void reverse(List nodes, CommonTree root) {
    if(nodes == null) return;
    for(int i = nodes.size()-1; i >= 0; i--) {
      CommonTree temp = (CommonTree)nodes.get(i);
      root.addChild(temp);
      root = temp;
    }
  }
}

parse
  :  function+ EOF -> ^(ROOT function+)
  ;

function
  :  (children+=id '.')* last=id {reverse($children, (CommonTree)$last.tree);} -> ^($last)
  ;

id 
  :  ID
  ;

ID
  :  ('a'..'z' | 'A'..'Z')+
  ;

Space
  :  ' ' {skip();}
  ;

И небольшой тестовый класс:

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

public class Main {
    public static void main(String[] args) throws Exception {
        ANTLRStringStream in = new ANTLRStringStream("a.b.c.d.e    Stack.Overflow.Horse    singleNode");
        ReverseTreeLexer lexer = new ReverseTreeLexer(in);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        ReverseTreeParser parser = new ReverseTreeParser(tokens);
        ReverseTreeParser.parse_return returnValue = parser.parse();
        CommonTree tree = (CommonTree)returnValue.getTree();
        DOTTreeGenerator gen = new DOTTreeGenerator();
        StringTemplate st = gen.toDOT(tree);
        System.out.println(st);
    }
}

, который будет производить AST, который выглядит следующим образом:

alt text

Для входной строки:

"a.b.c.d.e    Stack.Overflow.Horse    singleNode"
...