java - 如何合并两个 AST？

Question

我正在尝试实现一个工具来合并某些源代码的不同版本。给定相同源代码的两个版本，我们的想法是解析它们，生成各自的抽象源代码树 (AST)，最后将它们合并为一个保持语法一致性的输出源——词法分析器和解析器是问题 ANTLR: How to skip multiline comments 中的那些。

我知道有类 ParserRuleReturnScope 可以帮助...但是 getStop() 和 getStart() 总是返回 null :-(

这是一个片段，说明了我如何修改 perser 以打印规则:

parser grammar CodeTableParser;

options {
    tokenVocab = CodeTableLexer;
    backtrack = true;
    output = AST;
}

@header {
    package ch.bsource.ice.parsers;
}

@members {
    private void log(ParserRuleReturnScope rule) {
        System.out.println("Rule: " + rule.getClass().getName());
        System.out.println("    getStart(): " + rule.getStart());
        System.out.println("    getStop(): " + rule.getStop());
        System.out.println("    getTree(): " + rule.getTree());
    }
}

parse
    : codeTabHeader codeTable endCodeTable eof { log(retval); }
    ;

codeTabHeader
    : comment CodeTabHeader^ { log(retval); }
    ;

...

Answer 1

假设您拥有 AST(一开始通常很难获得，解析真实语言通常比看起来更难)，您首先必须确定它们的共同点，然后构建一个映射收集该信息。这并不像看起来那么容易；您是否将已经移动但完全相同的子树的代码块计算为“通用”？除了标识符的一致重命名外，两个相同的子树怎么样？更改后的评论呢？ (大多数 AST 会丢失注释；大多数程序员会认为这是一个非常糟糕的主意)。

您可以构建“最长公共(public)子串”算法的变体来比较树。我在自己构建的工具中使用了它。

最后，合并树后，现在需要重新生成文本，最好保留原始代码的大部分布局。 (程序员讨厌你改变他们如此喜欢的布局)。因此，您的 AST 需要捕获位置信息，并且您的再生必须尽可能地尊重这一点。