ANTLR:如何使用树语法替换子树中的特定节点？

标签 antlr

我有一个创建 AST 的 ANTLR 语法，然后我编写了两个树语法来创建树解析器，用于对 AST 进行两次传递以进行语义分析。 (之后我再做一遍并使用 StringTemplate 生成输出代码)

到目前为止一切正常，但我正在尝试扩展语言以支持函数中的参数多态性(而到目前为止它只支持“简单”函数)。

因此，例如，我想要这样的东西:

T getMax<T>  (T a, T b) {
     if (a > b) return a;
   return b;
}

并根据调用函数的实际类型生成简单的、非参数多态的代码。例如，如果有人调用 getMax<int> (5)那么我将只生成 int getMax(int a, int b) 的代码

到目前为止，在第一遍中，我检查了对多态函数的所有调用，并保存了调用该函数时使用的特定类型。

所以，此时我知道所有参数类型，以及它们需要替换的所有实际类型。

在第二遍中，我想实际修改我的语法树并将这个参数化多态函数声明替换为 1 个或多个具有特定类型的函数声明。

所以，问题是
  • 在 AST 中复制和创建“兄弟”节点(及其所有子节点)并将它们插入到原始函数声明旁边的最佳方法是什么？
    我只是说类似的话
          {
       myTreeNode.parent.addChild(myTreeNode.dupNode());  
      }
  • 替换所有出现的类型 T 的最佳方法是什么？比如说，int在上面示例中新创建的子树中？我认为一个简单的重写规则是不够的，因为我还需要替换函数体中的所有类型。
    我是否需要编写另一个仅适用于此函数声明子树并进行所有替换的树语法？手动操作更容易吗？

    • 对不起，如果这太困惑了。

    编辑 :

    Let's say your input is this:

    T add<T> (T a, T b) { return a+b }
add<int>(1, 2)
add<string>('f', 'oo')

    how would your AST look like after the 2nd pass?



    我正在考虑删除原始函数声明，并在其位置引入 2 个专门的声明。

    所以生成的 AST 将是一个根节点(我们可以称之为“程序”)，它有 4 个子节点、2 个函数声明和 2 个函数调用。

    打印 Lisp 风格:
    (METHOD_DECL int add (ARG_DECL int a) (ARG_DECL int b) (BLOCK (return (EXPR (+ (EXPR a) (EXPR b)))))) 
(METHOD_DECL string add (ARG_DECL string a) (ARG_DECL string b) (BLOCK (return (EXPR (+ (EXPR a) (EXPR b)))))) 
(EXPR (CALL add (ELIST (EXPR 3) (EXPR 4)))) 
(EXPR (CALL add (ELIST (EXPR "f") (EXPR "oo"))))

    被删除和替换的子树是这样的:
    (METHOD_DECL T add (TYPEPARAMS T) (ARG_DECL T a) (ARG_DECL T b) (BLOCK (return (EXPR (+ (EXPR a) (EXPR b))))))

    另外，我想删除原始参数多态函数声明子树的原因是我在进行类型检查时不知道如何忽略它。树解析器“自动”匹配所有二进制操作、返回语句、参数等并进行类型检查。所以，如果我把它留在那里，它会报告错误，因为例如 T 不是正确的类型，所以你不能将它与 + 运算符一起使用。

    最佳答案

    就个人而言，我会让解析器将方法与主代码块分开。给定输入:

    T add<T> (T a, T b) { 
  T c = a + b 
  return c 
}
int sub(int x, int y) { return x-y }
add<int>(1, 2)
add<string>('f', 'oo')

    然后解析器将生成代表的树:

    add<int>(1, 2)
add<string>('f', 'oo')

    以及表示方法的单独树:

    int    add (int a, int b)       { int c = a + b      return c   }
string add (string a, string b) { string c = a + b   return c   }
int    sub (int x, int y)       {                    return x-y }

    在解析阶段，您只需跟踪两个实例变量中的所有参数参数( pp ) -calls 和 -methods:

    @parser::members {

  private Map<String, Set<Token>> ppMethodCalls = new HashMap<String, Set<Token>>();
  private Map<String, CommonTree> ppMethods = new HashMap<String, CommonTree>();

  // a separate AST for all methods
  public CommonTree methods = new CommonTree(new CommonToken(METHODS, "METHODS"));

  // ...

}

    解析示例代码后，ppMethodCalls将持有:

    {"add" => {Token="int", Token="string"}}

    和 ppMethods将持有:

    {"add" => Tree=^(METHOD T add ... )}

    当解析器完全解析输入源时，调用以下方法:

      public void replacePP() {

    // iterate over all pp method calls
    for(Map.Entry<String, Set<Token>> entry : ppMethodCalls.entrySet()) {

      // get the name of the method being called
      String name = entry.getKey();

      // iterate over all tokens ('int' and 'string', in my example)
      for(Token tok : entry.getValue()) {

        // get the original pp-method instance
        CommonTree ppm = ppMethods.get(name);

        // create a deep copy from the original pp-method (will post 'copyTree(...)' later)
        CommonTree cp = Main.copyTree(ppm);

        // remove the first token from the tree (this is 'T' in my example)
        CommonTree pp = (CommonTree)cp.deleteChild(0);

        // replace all 'T' tokens with the actual parameter (either 'int' or 'string' in my example)
        replace(pp, tok, cp);

        // add the rewritten tree to the separate 'methods' tree
        methods.addChild(cp);
      }
    }
  }

  private void replace(CommonTree param, Token token, CommonTree tree) {
    if(tree == null) return;
    if(tree.getType() == param.getType() && tree.getText().equals(param.getText())) {
      tree.getToken().setType(token.getType());
      tree.getToken().setText(token.getText());
    }
    if(tree.getChildCount() > 0) {
      for(Object child : tree.getChildren()) {
        replace(param, token, (CommonTree)child);
      }
    }
  }

    这将为 add<int>(...) 创建两个新树和 add<string>(...)并将它们添加到实例变量中:methods: CommonTree .

    一个小演示:

    文件:PP.g

    grammar PP;

options {
  output=AST;
  ASTLabelType=CommonTree;
}

tokens {
  ROOT;
  METHODS;
  BLOCK;
  ASSIGN;
  ARG;
  ARGS;
  ELIST;
  METHOD;
  CALL;
}

@parser::header {
  import java.util.Map;
  import java.util.HashMap;
  import java.util.Set;
  import java.util.HashSet;
}

@parser::members {

  private Map<String, Set<Token>> ppMethodCalls = new HashMap<String, Set<Token>>();
  private Map<String, CommonTree> ppMethods = new HashMap<String, CommonTree>();
  public CommonTree methods = new CommonTree(new CommonToken(METHODS, "METHODS"));

  private void ppCall(String name, Token pp) {
    Set<Token> existing = ppMethodCalls.remove(name);
    if(existing == null) existing = new HashSet<Token>();
    existing.add(pp);
    ppMethodCalls.put(name, existing);
  }

  public void replacePP() {
    for(Map.Entry<String, Set<Token>> entry : ppMethodCalls.entrySet()) {
      String name = entry.getKey();
      for(Token tok : entry.getValue()) {
        CommonTree ppm = ppMethods.get(name);
        CommonTree cp = Main.copyTree(ppm);
        CommonTree pp = (CommonTree)cp.deleteChild(0);
        replace(pp, tok, cp);
        methods.addChild(cp);
      }
    }
  }

  private void replace(CommonTree param, Token token, CommonTree tree) {
    if(tree == null) return;
    if(tree.getType() == param.getType() && tree.getText().equals(param.getText())) {
      tree.getToken().setType(token.getType());
      tree.getToken().setText(token.getText());
    }
    if(tree.getChildCount() > 0) {
      for(Object child : tree.getChildren()) {
        replace(param, token, (CommonTree)child);
      }
    }
  }
}

parse
  :  block EOF -> block
  ;

block
  :  statement* -> ^(BLOCK statement*)
  ;

statement
  :  ppMethod     {ppMethods.put($ppMethod.name, $ppMethod.tree);} -> /* omit from main AST */
  |  normalMethod {methods.addChild($normalMethod.tree);}          -> /* omit from main AST */
  |  methodCall
  |  assignment
  |  Return expr -> ^(Return expr)
  ;

assignment
  :  type Id '=' expr -> ^(ASSIGN type Id expr)
  |  Id Id '=' expr   -> ^(ASSIGN Id Id expr)
  ;

normalMethod
  :  type Id '(' argList ')' '{' block '}' -> ^(METHOD type Id argList block)
  ;

ppMethod returns [String name]
  :  tp=Id id=Id {$name=$id.text;} '<' pp=Id '>' '(' ppArgList ')' '{' block '}' -> ^(METHOD $pp $tp $id ppArgList block)
  ;

methodCall
  :  Id ('<' type '>' {ppCall($Id.text, $type.tree.getToken());})? '(' exprList ')' -> ^(CALL Id exprList)
  ;

argList
  :  (arg (',' arg)*)? -> ^(ARGS arg*)
  ;

arg
  :  type Id -> ^(ARG type Id)
  ;

ppArgList
  :  (ppArg (',' ppArg)*)? -> ^(ARGS ppArg*)
  ;

ppArg
  :  type Id -> ^(ARG type Id)
  |  Id Id   -> ^(ARG Id Id)
  ;

exprList
  :  (expr (',' expr)*)? -> ^(ELIST expr*)
  ;

expr
  :  atom (('+' | '-')^ atom)*
  ;

atom
  :  Int
  |  Str
  |  Id
  |  methodCall
  |  '(' expr ')' -> expr
  ;

type
  :  K_Int
  |  K_Str
  ;

Return : 'return';
K_Int  : 'int';
K_Str  : 'string';
Id     : ('a'..'z' | 'A'..'Z') ('a'..'z' | 'A'..'Z' | Digit)*;
Int    : Digit+;
Str    : '\'' ~'\''* '\'';

Comment : '#' ~('\r' | '\n')* {$channel=HIDDEN;};
Space   : (' ' | '\t' | '\r' | '\n') {$channel=HIDDEN;};

fragment Digit : '0'..'9';

    文件:Main.java

    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 src =
        "T add<T> (T a, T b) {                 \n" +
        "    T c = a + b                       \n" +
        "    return c                          \n" +
        "}                                     \n" +
        "int sub(int x, int y) { return x-y }  \n" +
        "add<int>(1, 2)                        \n" +
        "add<string>('f', 'oo')                \n";
    PPLexer lexer = new PPLexer(new ANTLRStringStream(src));
    PPParser parser = new PPParser(new CommonTokenStream(lexer));
    CommonTree tree = (CommonTree)parser.parse().getTree();
    parser.replacePP();
    System.out.println(new DOTTreeGenerator().toDOT(tree));
    System.out.println(new DOTTreeGenerator().toDOT(parser.methods));
  }

  // put this in a Util-class or else in the parser   
  public static CommonTree copyTree(CommonTree original) {
    CommonTree copy = new CommonTree(original.getToken());
    copyTreeRecursive(copy, original);
    return copy;
  }

  private static void copyTreeRecursive(CommonTree copy, CommonTree original) {
    if(original.getChildren() != null) {
      for(Object o : original.getChildren()) {

        CommonTree originalChild = (CommonTree)o;

        // get the token from the original child node
        CommonToken oTok = (CommonToken)originalChild.getToken();

        // create a new token with the same type & text as 'oTok' 
        CommonToken cTok = new CommonToken(oTok.getType(), oTok.getText());

        // copy all attributes from 'oTok' to 'cTok'  
        cTok.setLine(oTok.getLine());
        cTok.setCharPositionInLine(oTok.getCharPositionInLine());
        cTok.setChannel(oTok.getChannel());
        cTok.setStartIndex(oTok.getStartIndex());
        cTok.setStopIndex(oTok.getStopIndex());
        cTok.setTokenIndex(oTok.getTokenIndex());

        // create a new tree node with the 'cTok' as token
        CommonTree copyChild = new CommonTree(cTok);

        // set the parent node of the child node
        copyChild.setParent(copy);

        // add the child to the parent node
        copy.addChild(copyChild);

        // make a recursive call to copy deeper
        copyTreeRecursive(copyChild, originalChild);
      }
    }
  }
}

    如果您现在运行主类:

    *尼克斯

    java -cp antlr-3.3.jar org.antlr.Tool PP.g
javac -cp antlr-3.3.jar *.java
java -cp .:antlr-3.3.jar Main

    或 window 

    java -cp antlr-3.3.jar org.antlr.Tool PP.g
javac -cp antlr-3.3.jar *.java
java -cp .;antlr-3.3.jar Main

    您将看到以 DOT 代码打印的两棵树:

    1

    enter image description here

    2

    enter image description here

    请注意，这只是我整理的一个快速技巧:事情可以再整理一下，returns [String name]在 ppMethod规则并不漂亮。它也不适合这样的方法:

    A foo<A,B> (A a, B b) {
  return A ~ B 
}

foo<int,string>(42, 'foo')

    也许还有更多的事情。我会把它留给你，希望你可以通过上面的小演示进一步了解。

    关于ANTLR:如何使用树语法替换子树中的特定节点？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7169226/

    上一篇：ruby-on-rails - 运行 Brew Doctor 时的主要警告

    下一篇：backbone.js - RequireJS - 我是否必须为子类重新导入以前需要的文件

    相关文章：

    ANTLR:源语言到目标语言的转换

    python - 访问用括号定义的属性

    java - ANTLR 语法第 1 行 :6 mismatched input '<EOF>' expecting '.'

    java - Antlr:无法找到或本地主类，即使它存在

    java - 组合语法可以工作，但是当词法分析器和解析器语法分离时会出现错误？

    java - 使用ANTLR4获取方法的注释

    java - Antlr 3 无法处理句法谓词

    antlr - 使用 ParseTreeWalker 中止树遍历

    java - 使用自定义 AST 节点类型进行树过滤时，如何避免抛出 ClassCastException？

    java - 方法specialStateTransition(int, IntStream)的代码超过65535字节

    ©2024 IT工具网  联系我们