如何合并两个抽象语法树？

Question

我正在尝试实现一个合并不同版本源代码的工具。给定相同源代码的两个版本，想法是解析它们，生成相应的抽象语法树（AST），并最终将它们合并成一个单一的输出源代码，保持语法一致性 - 词法分析器和解析器是问题ANTLR：如何跳过多行注释中的那些。

我知道有一个名为ParserRuleReturnScope的类可以帮助……但是getStop() 和getStart()总是返回null :-(

以下是一个代码片段，演示了我如何修改我的解析器以打印规则：

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); }
    ;

...

- j3d

---

我认为你需要更多的信息才能进行合并。例如一个共同的祖先版本，或者至少是已经被删除、添加或修改的内容。 - rolve

暂时可能不会，但现在这个工具只需要：1）保留共同部分；2）从最新的源代码版本中获取修改内容；3）保留两个源代码版本的非共同部分。就是这样。 - j3d

请查看我帖子的更新以获取更多细节。 - j3d

Answer 1

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

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

最后，在合并树之后，现在您需要重新生成文本，理想情况下保留原始代码的大部分布局。（程序员讨厌您改变他们如此喜爱的布局）。因此，您的AST需要捕获位置信息，并且您的再生必须在可能的情况下遵守该信息。

- Ira Baxter

---

是的...这差不多就是我所做的...无论如何，非常感谢您有趣且有用的评论 :-) - j3d

我对您是如何解决合并树的问题很感兴趣 - 我遇到了一些麻烦。您是如何实现LCS来比较树的？在获得共同部分之后，您是如何应用增量呢？ - j3d

我们使用后缀树。您可以阅读有关如何使用它们查找克隆（例如，“公共”）代码的信息，网址为http://ieeexplore.ieee.org/iel5/4023959/4023960/04023995.pdf。这将获取匹配的常量子树。您需要在剩下的内容上构建某种统一器，这是相当启发式的。 - Ira Baxter

Answer 2

你解析器代码中的 log(retval) 调用看起来像是在规则结束时发生，但实际上并不是。你需要将调用移动到一个 @after 块中。

我将 log 更改为输出消息以及作用域信息，并像下面这样在我的语法中添加了调用：

script    
    @init {log("@init", retval);}
    @after {log("@after", retval);}
    : statement* EOF  {log("after last rule reference", retval);} 
        -> ^(STMTS statement*) 
    ;

解析测试输入产生了以下输出：

Logging from @init
    getStart(): [@0,0:4='Print',<10>,1:0]
    getStop(): null
    getTree(): null
Logging from after last rule reference
    getStart(): [@0,0:4='Print',<10>,1:0]
    getStop(): null
    getTree(): null
Logging from @after
    getStart(): [@0,0:4='Print',<10>,1:0]
    getStop(): [@4,15:15='<EOF>',<-1>,1:15]
    getTree(): STMTS

after 块中的调用同时填充了 stop 和 tree 字段。

我不能确定这是否会对您的合并工具有所帮助，但我认为这至少可以让您解决半填充作用域对象的问题。

- user1201210

---

谢谢 :-) 现在 ParserRuleReturnScope 字段已经填充完毕。关于合并源代码... 我正在调查如何实现它... 无论如何，再次感谢您的惊人支持！ - j3d