logo标签列表

树形结构的正则表达式？

javapythoncregextree-structure
12

有没有正则表达式可以用于搜索和修改树形结构？我正在寻找简洁的迷你语言（如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”开头并将其替换为“b”，如果子树具有至少2个其他同级节点，则替换等。

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

我想知道是否有一种简单的迷你语言（不是正则表达式本身，而是像正则表达式一样通过库等方式易于访问），可以用作Python库来执行这些操作？

考虑一下那个东西的语法可能是什么样子的... :) - Mehrdad Afshari
嗯，你能更明确地说明你有什么以及正则表达式应该做什么吗？ - akappa
这需要更具体明确一些 - 你是在解析XML还是其他东西？ - Nathaniel Flath
3
不应称其为“常规”，因为“常规”需要“无上下文语法”，而树结构并不具备此特征。 - Svante
我同意，称其为“常规”的说法是不正确的，然而，我将其与常规语言进行比较的想法是出于实用性考虑。我想在字符串中进行搜索和替换 - 我使用正则表达式，我想在树上执行相同的操作，我使用..？ - JSN
@Svante的评论有两个问题：首先，正则表达式所评估的数据不一定是规则的。例如，您可以使用正则表达式在任意复杂语言的语料库中搜索特定n-gram的使用情况。其次，“正则表达式”在编程语言中的使用与定义Chomsky层次结构中的“正则表达式”并不相同。请参见此帖子以获取解释。哦，当然，“树”可以是“上下文无关的”。 - Lutz Büch
7个回答
8
有没有Java或Python的非GPL替代品？ - matanster
@matanster 是的，Python的正则表达式包也能够匹配递归模式。 - Anderson Green
5

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

1
我已经研究了XPath。它看起来很有前途，但似乎不能处理节点集合上的表达式（例如，查找至少有2个兄弟节点的所有节点）。它的功能有限。 - JSN
5

与基于模式的树重写相关，TXL 是一个好的选择。

使用解析器工具包（如ANTLR）也可以进行带有模式的树重写。

在底向上树重写中进行代码生成，可以参考谷歌的 BURS 或 BURG。

1
TXL看起来非常有前途，但是无论是ANTLR还是TXL都假定上下文无关文法，在需要执行解析时这一点非常重要。然而，为了进行转换和树形结构的类似正则表达式的行为，它应该明确地依赖于上下文。请参见我对上面问题的澄清，其中包括我想要的一些用例（例如：在兄弟节点上搜索并带有条件）。 - JSN
1

遍历二叉搜索树需要状态（我在哪个节点？）和比较（这个值是否小于或大于那个值？），这些都无法由有限状态自动机完成。

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

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

我认为您对FSA要求过高了。

如果每个节点都包含与之相关的所有数据（以及与之相关的状态），例如祖先和父状态，那么自动机可以正常工作吗？ - Aiden Bell
然后，与其他节点相关的子表达式可以调用子引擎返回映射到转换的状态或布尔值。 - Aiden Bell
1

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

更典型的做法是编写状态机风格的解析器，可能使用正则表达式来解析树中的每个特定节点。

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

1

模式匹配，由Scala、F#、Erlang和Haskell等语言提供，旨在简洁地操作数据结构，如树，尤其是与递归结合使用时。

这里是一个非常高级别的视图，展示了Scala中模式匹配可以做什么。所示示例实际上并不能充分展示模式匹配的优势。

维基百科也提供了一些关于模式匹配的参考资料，此处和此处。

1

我有点惊讶XSLT没有成为答案。诚然，我认为它不是特别优雅的语言，大多数现有的解决方案倾向于采用过程化方法而不是模式匹配，并且由于盲目地将XML应用于XML而获得了非常糟糕的声誉 - 但除此之外，它符合要求。可惜它的规范表示如此冗长...

现在，XSLT似乎是最接近我想要的，但编写上下文敏感查询似乎很复杂，我的问题是找到比XSLT更好的东西。 - JSN
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接