27

在这里，人们有时会说“你不能用正则表达式解析 X，因为 X 不是正则语言”。然而，据我了解，现代正则表达式引擎可以匹配的不仅仅是乔姆斯基意义上的正则语言。我的问题：

给定一个支持的正则表达式引擎

  • 反向引用
  • 无限宽度的环视断言
  • 递归，比如(?R)

它可以解析什么样的语言？它可以解析任何上下文无关的语言吗？如果不能，反例是什么？

（准确地说，“解析”的意思是“构建一个单一的正则表达式，它将接受由语法 X 生成的所有字符串并拒绝所有其他字符串”）。

补充：我特别有兴趣看到现代正则表达式引擎（Perl、Net、python 正则表达式模块）无法解析的上下文无关语言的示例。

4

3 回答 3

19

我最近写了一篇关于这个主题的相当长的文章：正则表达式的真正力量。

总结一下：

  • 支持递归子模式引用的正则表达式可以匹配所有上下文无关语言（例如a^n b^n）。
  • 带有环视断言和子模式引用的正则表达式至少可以匹配一些上下文相关的语言（例如ww和a^n b^n c^n）。
  • 如果断言具有无限宽度（如您所说），则可以匹配所有上下文相关的语法。我不知道任何正则表达式风格，尽管它对后视没有固定宽度的限制（同时支持子模式引用）。
  • 具有反向引用的正则表达式是 NP 完全的，因此任何其他 NP 问题都可以使用正则表达式来解决（在应用多项式时间变换之后）。

一些例子：

  • 匹配上下文无关语言{a^n b^n, n>0}：

    /^(a(?1)?b)$/
# or
/^ (?: a (?= a* (\1?+ b) ) )+ \1 $/x

  • 匹配上下文相关语言{a^n b^n c^n, n>0}：

    /^
    (?=(a(?-1)?b)c)
    a+(b(?-1)?c)
$/x
# or
/^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $/x
于 2012-07-08T11:06:51.507 回答
9

现代正则表达式引擎当然可以解析比常规语言集更大的语言集。这么说，四个经典的乔姆斯基集都没有被正则表达式准确识别。正则表达式清楚地识别所有常规语言。有一些经典的上下文无关语言无法被正则表达式识别，例如平衡括号语言a^n b^n，除非有计数的反向引用可用。但是，正则表达式可以解析ww上下文相关的语言。

实际上，形式语言理论中的正则表达式与正则表达式的关系不大。在最一般的情况下，匹配具有无限反向引用的正则表达式是 NP-Complete 的，因此所有足够强大的正则表达式的模式匹配算法都是指数的，至少在一般情况下是这样。然而，对于大多数输入来说，大多数时候它们都非常快。众所周知，匹配上下文无关语言最多比 快n^3，因此正则表达式中有一些语言不是上下文无关的（如ww），但并非所有上下文无关语言都可以被正则表达式解析。0 型语言通常是不可判定的，子正则表达式无法到达那里。

因此，作为一个不是很确定的结论，正则表达式可以解析广泛的语言集，包括所有常规语言，以及一些上下文无关和上下文敏感的语言，但它并不完全等于任何这些语言集。还有其他类别的语言和其他分类法，您可以在其中找到更准确的答案，但是没有任何分类法将上下文无关语言作为语言层次结构中的适当子集包含在正则表达式中，因为正则表达式无法准确识别单一语言仅在某些部分与上下文无关语言相交，两者都不是另一个的适当子集。

于 2012-07-05T19:54:15.117 回答
2

您可以在Ralph W. Fasold、Jeff Connor-Linton P.477 的《语言和语言学概论》中了解正则表达式

乔姆斯基层次结构：

类型0 >= 类型1 >= 类型2 >= 类型3

计算语言学主要以类型 2 和 3 语法为特征

•类型 3 语法：

– 包括正则表达式和有限状态自动机（又名有限状态机）

——本次演讲的重点

•类型 2 语法：

--常用于自然语言解析器

– 用于在许多语言理论中对句法结构进行建模（通常由其他机制补充）

——我们将在下一次关于解析的演讲中发挥关键作用。

大多数具有相互关系链接的 XML（如Microsoft DGML（有向图标记语言））都是 Regex 无用的示例。

这三个答案可能有用：

1 -环顾四周影响哪些语言可以通过正则表达式匹配

2 -正则表达式-arent

3 -在哪里做最多的正则表达式实现落在复杂性规模上

于 2012-07-06T07:48:14.470 回答