11

是否有用于搜索和修改树结构的正则表达式等价物？我正在寻找简洁的迷你语言（如 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>

搜索和替换操作，例如查找所有具有至少 2 个子节点的节点、查找数据以“a”开头的所有节点，如果子树至少有 2 个其他兄弟节点，则将其替换为“b”等。应该支持。

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

我想知道是否有一些简单的迷你语言（不是正则表达式本身，而是通过库等可以像正则表达式一样访问的东西）。执行这些操作？最好作为 python 库。

4

7 回答 7

8

斯坦福大学的 TSurgeon 和 Tregex 能够做到这一点。您可以从http://nlp.stanford.edu/software/tregex.shtml下载该库

于 2011-05-21T13:40:55.173 回答
5

我不知道可以做到这一点的通用语言，但在我看来，您正在寻找类似XPath的东西。

于 2009-05-17T18:17:02.567 回答
5

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

使用ANTLR等解析器工具包也可以使用模式重写树

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

于 2009-05-17T18:17:31.427 回答
1

在二叉搜索树中导航需要状态（我在哪个节点？）和比较（该值小于还是大于该值？），这是有限状态自动机无法完成的。

当然，您可以搜索具有给定值的节点，但是如果您不知道其父节点，例如，您如何删除不是叶子的节点？

即使通过节点提供的信息知道父节点，如何确定左子树的最小值，将其移除并放入节点中？

我认为你对 FSA 的要求太高了。

于 2009-05-17T18:13:22.010 回答
1

本文提供了一些关于递归 Perl 正则表达式的有用提示，但老实说，很少看到以这种方式处理树结构。

更典型的是，人们会编写一个状态机样式的解析器，它可能使用正则表达式来解析树中的每个特定节点。

Expat可能是一个很好的例子。

于 2009-05-17T18:17:55.310 回答
1

由 Scala、F#、Erlang 和 Haskell 等语言提供的模式匹配（我相信还有更多）旨在简洁地操作树等数据结构，尤其是与递归一起使用时。

这是 Scala 中模式匹配可以做什么的一个非常高级的视图。显示的示例确实不公平地进行模式匹配。

维基百科也有一些关于模式匹配的参考。这里和这里。

于 2009-05-17T18:33:12.820 回答
1

我有点惊讶XSLT没有作为答案出现。诚然，我不认为它是一种特别优雅的语言，并且大多数现有的解决方案倾向于支持过程方法而不是模式匹配，并且仅仅因为将 XML 应用于 XML 而盲目地应用它而得到了一个非常糟糕的代表——但除此之外它符合要求。可惜它的规范表示是如此冗长，虽然......

于 2009-05-17T20:51:00.407 回答