用于转换节点树的库

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',)))