树结构的正则表达式？

Question

是否有正则表达式等价的搜索和修改树结构？我正在寻找简洁的迷你语言(如perl regex).

这是一个可以澄清我在寻找什么的例子.

<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>

搜索和替换操作,例如查找具有至少2个子节点的所有节点,查找数据以"a"开头的所有节点,如果子树至少有2个其他兄弟节点等,则将其替换为"b",等等.

对于字符串,其中唯一的维度是跨越字符串的长度,我们可以使用正则表达式执行上述操作中的许多操作(或其1D等价物).我想知道是否有树的等价物.(而不是单个正则表达式,您可能需要编写一组转换规则,但这没关系).

我想知道是否有一些简单的迷你语言(不是正则表达式,而是通过库等可以访问正则表达式等).执行这些操作？优选地,作为python库.

Answer 1

来自斯坦福的TSurgeon和Tregex有能力做到这一点.您可以从http://nlp.stanford.edu/software/tregex.shtml下载该库

Answer 2

我不知道能够做到这一点的通用语言,但在我看来,你正在寻找像XPath这样的东西.

Answer 3

有用于基于模式的树重写的TXL。

使用模式重写树也可以使用解析器工具包（如ANTLR）完成

使用自下而上的树重写、google BURS 或 BURG 生成代码。