Antlr AST 产生（可能的）疯狂

Question

以下情况可能吗？我想“反转”给予 antlr 的输入，并使每个标记成为前一个标记的子标记。

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

Stack.Overflow.Horse

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

Horse
  |---Overflow
         |---Stack

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

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

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

Answer 1

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

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

但这只会使最后一个节点成为根节点，而所有其他节点成为其子节点。例如，以下源：

a.b.c.d.e

将生成以下树：

    e
 / / \ \
d c   b a

我看不到简单的修复方法，因为当您第一次解析 abcde 时，a 将是 ID 和 bcde 对 function 的递归调用：

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

导致 bcde 将具有 a作为它的孩子。当 b 成为 ID 时，它也会作为子项添加到 a 旁边。在您的情况下，应将 a 作为子项删除，然后将其添加到 b 的子项列表中。但据我所知，这在 ANLTR 中是不可能的（至少在语法中不可能以干净的方式）。

---

编辑

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

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

然后在 中收集所有可能的前面节点（children） >使用 += 运算符列出：

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

并在解析器中使用自定义成员方法将这些子元素“注入”到树的根中（进入在您的 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：

• （使用 http://graph.gafol.net)

对于输入字符串：

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