1

以下甚至可能吗？我想“反转”给 antlr 的输入，并使每个令牌成为前一个令牌的子代。

因此，对于输入（假设每个标记由 '.' 字符分隔）：

Stack.Overflow.Horse

我希望我的语法产生以下 AST：

Horse
  |---Overflow
         |---Stack

到目前为止，我已经设法反转节点，但我无法让它们成为彼此的孩子：

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

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

1 回答 1

3

我不认为有一个简单的方法可以做到这一点。你可以这样制定规则：

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作为它的孩子的事实。当 thenb变为 时ID，它也被添加为 child 旁边a。在您的情况下，a应该作为孩子删除，然后添加到 的b孩子列表中。但是 AFAIK，这在 ANLTR 中是不可能的（至少，在语法中不是以干净的方式）。

编辑

好的，作为一种解决方法，我想到了一些优雅的东西，但这并没有像我希望的那样奏效。因此，作为一个不太优雅的解决方案，您可以将last节点匹配为重写规则中的根：

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

然后使用运算符children在 a 中收集所有可能的先前节点 ( ) ：List+=

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

并在解析器中使用自定义成员方法将这些“注入”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：

替代文字

对于输入字符串：

"a.b.c.d.e    Stack.Overflow.Horse    singleNode"
于 2010-09-27T15:40:00.213 回答