将子树从AST的一个部分移到另一个部分

Question

我正在研究将Oracle SQL转换为ANSI SQL的工具。我有一个解析Oracle SQL和ANSI SQL的语法。

我想从AST的where子句部分提取Oracle外部连接表达式，并在AST的from子句部分的末尾插入新的连接子句以用于匹配的select或subquery。

具有重写规则的树解析器可以执行这种类型的树转换吗？

即采取从Oracle SQL

SELECT 
    a.columna, b.columnb 
FROM 
    tablea a, 
    tableb b 
WHERE 
    a.columna2 (+) = b.columnb2 (+) 
    AND 
    a.columna3 = 'foo' 
    AND 
    b.columnb3 = 'bar' 

产生AST并将其转换为一个AST为ANSI SQL

SELECT 
    a.columna, b.columnb 
FROM 
    tablea a FULL OUTER JOIN tableb b ON (a.columna2 = b.columnb2) 
WHERE 
    a.columna3 = 'foo' 
    and 
    b.columnb3 = 'bar' 

注释1：对于tablea和tableb表的引用从FROM条款删除并用引用相同表和表别名的JOIN子句替换。

注2：Oracle连接条件在sql_condition比较两端都存在OuterJoinIndicator（+）时被标识为FULL OUTER JOIN。注3：连接条件比较从WHERE子句中删除，并用于构造连接子句ON条件[删除了OuterJoinIndicator（s）]。

Answer 1

如果你有两种不同的语法，你很可能会发现语法中的“小差异”会导致这些子句的AST差异很大，所以你真正的问题是将树结构转换为另一个树形结构。而且你必须对整棵树分段执行此操作，因为这些差异遍布整个语法。因人而异。

ANTLR的树解析器很可能会让你识别任意片段;这些肯定是在其他语法的AST中产生等价物的线索。但是你必须编写很多这样的片段，并且代码相应的例程逐节点地组装等价的树。作为大型文法（如Oracle SQL）的一般规则，这可能是相当多的工作。你可以这样做。

另一种方法是program transformation系统。这些工具可让您编写表面语法模式（例如，Oracle SQL和ANSI SQL中的短语），以便直接编写和应用转换。以这种方式写入转换是相当容易的恕我直言。你会写出来是这样的：

source domain Oracle. 
target domain ANSISQL. 
rule xlate_Oracle_SELECT(c: columns, t1: table, t2: table, 
          c1: column, c2: column, 
          more_conditions: conditions):SQL_phrase 
    "SELECT \c FROM \t1, \t2 WHERE c1 (+) = c2 (+) and \more_conditions"; 
    => 
     "SELECT \c FROM \t1 FULL OUTER JOIN \t2 on (c1 = c2) WHERE \more_conditions"; 

（反斜杠-ID是可以匹配的声明语法类型在该位置合法的任意部分树模式变量）

的原因，这作品是转换工具用第一个语法解析第一个模式，因此得到一个它可以在第一个语法的树上匹配的树，并类似地使用第二个语法解析第二个模式，得到一个替换树，第二语法规则。转换引擎匹配第一个模式的树，并替换第二个树。因此，这样的规则将蓝色树中的一小组蓝色树节点转换为所需树形类型的一小组绿色节点。颜色比喻应该清楚地表明，如果您想要精确翻译，您必须将全部蓝色节点翻译成绿色节点。

你会需要更多的规则，以各种小节翻译只是纸翻在语法上的差异，例如，：

rule translate column(t: IDENTIFIER, c: IDENTIFIER,):table->table 
    "\t.\c" -> " \toSQLidentifier\(\t\).\toSQLidentifier\(\c\)"; 

这将处理两种语言如何拼写识别，区别通过调用自定义函数toSQLidentifier那个字符串黑客入侵。

我不认为ANTLR支持这种转换规则。你可以用很多代码模拟它。

如果你有两种语言的“联合”语法（这就是你所暗示的），你可能会避免一些这样的语法，但这通常会给你一个高度模糊的语法，这是一个巨大的麻烦。如果您在这方面取得成功，则只需在语言不同的情况下应用翻译规则（例如，所有内容都是蓝色节点）。

你也可以破解它：从左到右扫描树;相当相当的部分（弄明白这一点比看起来更难），它们在哪里不一样，相当打印替换。这是一个非常脆弱的方式来做到这一点。

Answer 2

是的，这是非常有可能的，特别是因为你有一个可以识别Oracle和ANSI SQL的语法。我曾经写过一个从AREV BASIC到Visual BASIC的翻译，并做了许多类似的转换。

在我的项目中，我使用了ANTLR 2，并编写了一个主树语法，它根据语法中的所有规则完全走过树。然后，我使用ANTLR 2的子类来覆盖特定的规则来完成转换。我喜欢这个，因为它让我建立了通行证的翻译，并保留了我的所有表达式处理在一个通行证中，另一个通行证中的控制结构等。

ANTLR 3不提供语法子类化，所以你将无法使用这种方法。你将需要一个完整的树语法来打印出你的结果树。就我个人而言，我会先写这个树语法并让它正常工作。然后，我会复制该语法并删除所有动作，但是可以选择重写AST。然后修改您的转换所需的规则。如果你做了很多转换，你可能想要使用多遍，每次传递一棵树语法。你可能有一两次做分析，以帮助推动后来的传球。在我的BASIC翻译项目中，我做了分析过程中的流量分析，数据流分析和死代码删除控制。

如果您需要帮助编写特定的转换，您需要共享您的树语法。有相当多的树语法成语来包裹你的头。如果您需要帮助，特伦斯的ANTLR 3书将是一笔宝贵的购买。如果你还没有写出树语法，那么当你卡住时发布问题。选择正确的根节点很重要。如果你想了解如何构建树和树解析器，你可以看看我的C语法。这是ANTLR 2，但树木建筑的概念是相同的。 http://www.antlr3.org/grammar/cgram/grammars/

您是否需要保留注释和格式？这增加了另一层复杂性，为此我建议创建另一个问题。