树结构的正则表达式？

Question

有没有类似正则表达式的东西可以用来搜索和修改树结构？我想要的是一些简洁的小语言（就像perl的正则表达式那样）。

下面是一个例子，可能能更清楚地说明我想要的是什么。

<root>
  <node name="1">
    subtrees ....
  </node>
  <node name="2">
    <node name="2.1">
     data
    </node>
    other subtrees...
  </node>
</root>

在上面的树结构上，可以进行的一个操作是“把节点2.1的子树移动到节点1的子树里”。这个操作的结果可能看起来像这样……

<root>
  <node name="1">
    subtrees ....
    <node name="2.1">
     data
    </node>
  </node>
  <node name="2">
    other subtrees...
  </node>
</root>

像是查找和替换的操作，比如找出所有至少有两个孩子的节点，找出所有数据以“a”开头的节点，并在它们的子树至少有两个兄弟节点的情况下把“a”替换成“b”等等，这些操作应该是可以支持的。

对于字符串来说，只有一个维度，就是字符串的长度，我们可以用正则表达式做很多上述操作（或者它们的一维等价操作）。我想知道树结构有没有类似的东西。（可能不需要一个单独的正则表达式，而是需要写一组转换规则，但这也没关系）。

我想知道有没有什么简单的小语言（不是正则表达式本身，但像正则表达式那样通过库等方式容易使用），可以用来执行这些操作？最好是作为一个python库。

Answer 1

我不知道有没有一种通用的语言可以做到这一点，但我觉得你可能在寻找类似于XPath的东西。

Answer 2

有一个叫做 TXL 的工具，可以用来进行基于模式的树重写。

使用模式进行树重写的工作，也可以通过一些解析工具包来完成，比如 ANTLR。

如果你想了解如何通过自下而上的树重写来生成代码，可以搜索一下谷歌的 BURS 或 BURG。

Answer 3

斯坦福大学的TSurgeon和Tregex可以做到这一点。你可以从这个链接下载这个库：http://nlp.stanford.edu/software/tregex.shtml