用於轉換節點樹的庫

Question

我希望能夠在不編寫大量重複的意大利細麪條代碼的情況下將一棵樹轉換爲另一棵樹。有沒有圖書館可以幫助解決這個問題？我的目標語言是Python，但只要可以移植到Python，我就會查看其他語言。

實施例：我想改變這個節點樹：（請原諒S-expressions）

(A (B) (C) (D)) 

向該之一：

(C (B) (D)) 

只要親本是A和第二祖先是C，無論上下文（可能有更多的父母或祖先）。我想以簡單，簡潔和可重用的方式表達這種轉變。當然這個例子非常具體。請嘗試解決一般情況。

編輯：RefactoringNG是我尋找的東西，雖然它引入了一個全新的語法來解決問題，我想避免。我仍然在尋找更多和/或更好的例子。

---

背景：

我能Python和獵豹（不要問！）文件轉換爲記號化樹表示，進而轉換成那些樹木lxml。我打算重新組織樹並寫出結果以實現自動化重構。 XSLT似乎是重寫XML的標準工具，但語法很糟糕（在我看來，顯然），我們商店裏沒有人會理解它。

我可以編寫一些簡單地使用lxml方法（.xpath等）來實現我的重構的函數，但我擔心我會用一堆專門構建的意大利麪代碼重新使用。

Answer 1

你真的想恕我直言，什麼是program transformation system，它允許您解析和使用源代碼（甚至目標語言）的表面語法表達的方式直接表達的重寫變換代碼。

你會發現，即使你能夠親自使用Python樹的XML表示，編寫XSLT/XPath轉換的努力也超出了你的期望;代表真實代碼的樹比你想象的要混亂，XSLT不是那種方便的符號，它不能直接表達你想檢查的樹的常見條件（例如，兩棵子樹是相同的）。與XML最後的複雜化：假設它已經被轉換。你如何重新產生源代碼的語法？你需要一些漂亮的打印機。

不管代碼是如何表示的，一個普遍的問題是沒有關於作用域和類型的信息（在哪裏可以得到它），編寫正確的轉換是非常困難的。畢竟，如果您要將python轉換爲使用不同運算符進行字符串連接和算術運算的語言（不像Java對兩者使用「+」），您需要能夠決定要生成哪個運算符。所以你需要類型信息來決定。 Python可以說是無類型的，但實際上大多數表達式涉及的變量在整個生命週期中只有一種類型。所以你還需要流量分析來計算類型。

我們DMS Software Reengineering Toolkit具有所有這些能力（分析，流程分析，模式匹配/重寫，以漂亮的方式），並robust parsers很多語言包括Python。（雖然它具有爲C，COBOL，Java實例化的流分析功能，但它沒有爲Python實例化，但是，你說你想在不考慮上下文的​​情況下進行轉換）。

要表達出你對DMS上Python語法接近你的例子重寫（這是不是Python的？）

domain Python; 

    rule revise_arguments(f:IDENTIFIER,A:expression,B:expression, 
            C:expression,D:expression):primary->primary 
    = " \f(\A,(\B),(\C),(\D)) " 
    -> " \f(\C,(\B),(\D)) "; 

上面的符號是DMS規則重寫語言（RSL）。 「...」是元語言，它們用於從DMS RSL語言中分離出Python語法（在這些引號中，DMS知道它是Python，因爲域名符號聲明）。元引用內部的\ n是指在規則參數列表中定義的指定非終結符類型的語法變量佔位符。是的，（...）在metaquotes裏面是Python（）......就DMS而言，它們存在於語法樹中，因爲它們與語言的其他部分一樣，只是的語法。

上面的規則看起來有點奇怪，因爲我試圖儘可能接近你的例子，而從表達式語言的角度來看，你的例子很奇怪，因爲它確實有非同尋常的括號。

有了這個規則，DMS可以像

 foobar(2+3,(x-y),(p),(baz())) 

構建解析的Python（使用Python的解析器）的AST，對陣的是AST的（解析到AST）規則，它改寫到另一個AST相應到：

 foobar(p,(x-y),(baz())) 

然後漂白打印表面語法（有效）python退出。

如果你打算你的例子是在LISP代碼的轉換，你 需要的DMS（並不難打造，但我們並沒有太多 呼籲這）一個LISP語法，並寫出相應的表面語法：

domain Lisp; 

    rule revise_form(A:form,B:form, C:form, D:form):form->form 
    = " (\A,(\B),(\C),(\D)) " 
    -> " (\C,(\B),(\D)) "; 

通過查看Algebra as a DMS domain，您可以獲得更好的感受。

如果你的目標是在Python中實現所有這些......我沒有太多的幫助。 DMS是一個相當大的系統，它將是一個很大的努力複製。

Answer 2

讓我們在Python代碼中試試這個。我爲葉子使用了字符串，但這可以用於任何對象。

def lift_middle_child(in_tree): 
    (A, (B,), (C,), (D,)) = in_tree 

    return (C, (B,), (D,)) 

print lift_middle_child(('A', ('B',), ('C',), ('D',))) # could use lists too 

這類樹改造，一般最好是在實用的風格進行 - 如果你創建了一堆的這些功能，你可以明確地撰寫，或者創建一個合成功能在與他們合作的一個點，免費樣式。因爲你已經使用了s表達式，我假設你可以很容易地將樹表示爲嵌套列表（或等價物 - 除非我錯了，lxml節點可以這樣迭代）。顯然，這個例子依賴於一個已知的輸入結構，但你的問題意味着這一點。您可以編寫更靈活的函數，並且仍然可以編寫它們，只要它們具有統一的界面即可。

下面的代碼在行動：http://ideone.com/02Uv0i

現在，這裏的扭轉孩子的功能，並使用與上面的函數，一個提升和反向：

def compose2(a,b): # might want to get this from the functional library 
    return lambda *x: a(b(*x)) 

def compose(*funcs): #compose(a,b,c) = a(b(c(x))) - you might want to reverse that 
    return reduce(compose2,funcs) 

def reverse_children(in_tree): 
    return in_tree[0:1] + in_tree[1:][::-1] # slightly cryptic, but works for anything subscriptable 

lift_and_reverse = compose(reverse_children,lift_middle_child) # right most function applied first - if you find this confusing, reverse order in compose function. 

print lift_and_reverse(('A', ('B',), ('C',), ('D',)))