如何合并两个AST的？(How to merge two ASTs?)

我试图实施合并不同版本的一些源代码的工具。由于相同的源代码的两个版本，想法是将其解析，生成相应的抽象源代码树（AST），最后把它们合并成一个单一的输出源保持语法一致性-词法和语法分析器是这些问题的ANTLR：如何跳过多行注释。

我知道有类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:

调用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填充字段。

我不能说这是否会帮助你与你的合并工具，但我认为这将至少让你过去与半填充范围对象的问题。

Answer 2:

假设你拥有的AST（往往难以在第一时间拿到的地方，真正的解析语言往往比看起来难），您必须首先确定他们有什么共同点，并建立一个映射收集的信息。这并不像看起来那么容易; 你指望已移动，但完全相同的子树，为“普通”的代码块？怎么样两个子树是除了标识一致改名一样吗？怎么样改变的意见？（AST的大部分失去的意见;大多数程序员会认为这是一个非常糟糕的主意）。

你可以建立的“最长公共子串”算法来比较树木的变化。我用在我所开发的工具。

最后，你已经合并了树后，现在你需要重新生成文本，保留最好最原始代码的布局。（当你改变他们那么可爱生产布局程序员讨厌）。所以，你的AST需要捕获位置信息，并且你的再生必须遵守这个地方就可以了。

文章来源: How to merge two ASTs?