我有一个创建 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 的最佳方法是什么?我认为简单的重写规则是不够的,因为我还需要替换函数体中的所有类型。
    我是否需要编写另一种树语法来仅在此函数声明子树上工作并进行所有替换?手动完成更容易吗?

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

    编辑 :



    我正在考虑删除原始函数声明,并在其位置引入 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

    2

    请注意,这只是我拼凑起来的一个小技巧:事情可以稍微整理一下,而且 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/

    10-11 19:31
    查看更多