用于转换节点树的库

8 投票

2 回答

1074 浏览

提问于 2025-04-17 10:33

我希望能找到一种方法，把一种树结构转换成另一种，而不需要写一堆重复的、杂乱无章的代码。有没有什么库可以帮助解决这个问题？我主要使用Python，但如果有其他语言的解决方案，只要能转到Python，我也会考虑。

举个例子：我想把这个节点树转换成另一个节点树：（请原谅我使用了S表达式）

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

变成这个：

(C (B) (D))

只要父节点是A，第二个祖先是C，不管上下文是什么（可能还有其他父节点或祖先）。我希望能用一种简单、简洁且可重用的方式来表达这个转换。当然，这个例子很具体，希望能讨论更一般的情况。

补充：RefactoringNG是我在寻找的那种工具，尽管它引入了一种全新的语法来解决问题，我希望能避免这种情况。我还在寻找更多或更好的例子。

背景：

我能把Python和Cheetah（别问！）文件转换成标记化的树结构，然后再把这些转换成lxml树。我打算重新组织这些树，并输出结果，以实现自动重构。XSLT似乎是重写XML的标准工具，但我觉得它的语法很糟糕（显然是我个人的看法），而且我们公司没人能理解它。

我可以写一些函数，直接使用lxml的方法（比如.xpath等）来实现我的重构，但我担心这样会导致一堆专门为某个目的写的杂乱代码，无法重用。

lxml 代码重用语法简化 xsl S表达式节点树树结构转换重构工具

2 个回答

在我看来，你真正想要的是一个程序转换系统，这个系统可以让你通过源代码的表面语法（甚至目标语言的语法）来解析和转换代码，从而直接表达重写的内容。

即使你能拿到Python代码的XML表示，写一个XSLT/XPath转换的工作量也会比你想象的要大。因为表示真实代码的树结构比你想的要复杂，XSLT的语法也不太方便，而且它不能直接表达你想检查的常见条件（比如，两个子树是否相同）。还有一个关于XML的麻烦：假设它已经被转换过了，你怎么从中重新生成原来的源代码语法呢？你需要某种格式化工具。

不管代码是如何表示的，一个普遍的问题是，如果没有关于作用域和类型的信息（你可以从哪里获得这些信息），写出正确的转换是相当困难的。毕竟，如果你要把Python转换成一个使用不同运算符进行字符串连接和算术运算的语言（与Java不同，Java对这两者都使用“+”），你需要能够决定生成哪个运算符。因此，你需要类型信息来做出决定。虽然Python可以说是没有类型的，但实际上大多数表达式涉及的变量在其整个生命周期内只有一种类型。所以你还需要流分析来计算类型。

我们的DMS软件重构工具包具备所有这些功能（解析、流分析、模式匹配/重写、格式化），并且有强大的解析器支持多种语言，包括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）。其中的“...”是元引用，用来将Python语法（在这些引号内，DMS通过领域符号声明知道这是Python）与DMS RSL语言区分开。元引用中的\n指的是规则参数列表中定义的命名非终结符类型的语法变量占位符。是的，元引用中的(...)是Python，它们在语法树中存在，因为在DMS看来，它们和语言的其他部分一样，都是语法。

这个规则看起来有点奇怪，因为我尽量跟你的示例保持一致，而从表达式语言的角度来看，你的示例之所以奇怪，正是因为它有不寻常的括号。

使用这个规则，DMS可以像这样解析Python（使用它的Python解析器）

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

构建一个抽象语法树（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)) ";

你可以通过查看代数作为DMS领域来更好地理解这一点。

如果你的目标是用Python实现这一切……我帮不了你。DMS是一个相当庞大的系统，复制它会需要很多精力。

回答于 2025-04-17 由 Python大师

分享举报

让我们在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',)))

回答于 2025-04-17 由 Python大师

分享举报

用于转换节点树的库

2 个回答

撰写回答