將子樹從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/

您是否需要保留註釋和格式？這增加了另一層複雜性，爲此我建議創建另一個問題。