用于转换节点树的库

Question

我希望能够在不写一堆重复的意大利面条代码的情况下表达一棵树到另一棵树的一般转换.有没有图书馆来帮助解决这个问题？我的目标语言是Python,但只要可以移植到Python,我就会看其他语言.

示例:我想转换此节点树:(请原谅S表达式)

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

进入这一个:

(C (B) (D))

只要父母是A而第二个祖先是C,无论上下文(可能有更多的父母或祖先).我想以简单,简洁和可重用的方式表达这种转变.当然这个例子非常具体.请尝试解决一般情况.

编辑:RefactoringNG是我正在寻找的东西,虽然它引入了一个全新的语法来解决问题,我想避免.我还在寻找更多和/或更好的例子.

---

背景:

我能够将python和猎豹(不要问!)文件转换为标记化的树表示,然后将它们转换为lxml树.我计划重新组织树并写出结果,以实现自动重构.XSLT似乎是重写XML的标准工具,但语法很糟糕(在我看来,很明显),我们店里的任何人都不会理解它.

我可以编写一些函数,它们只使用lxml方法(.xpath等)来实现我的重构,但我担心我最终会得到一堆专用的意大利面条代码,这些代码无法重复使用.

Answer 1

恕我直言，您真正想要的是一个程序转换系统，它允许您使用源代码（甚至目标语言）的表面语法表达的模式来解析和转换代码，以直接表达重写。

您会发现，即使您能够获得 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 是一个相当大的系统，复制起来需要付出很大的努力。