现代正则表达式引擎可以解析什么样的正式语言？

Question

在SO上,人们有时会说"你不能用正则表达式解析X,因为X不是常规语言".然而,根据我的理解,现代正则表达式引擎可以匹配乔姆斯基意义上的常规语言.我的问题:

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

• 反向引用
• 无限宽度的外观断言
• 递归,就像 (?R)

它可以解析什么样的语言？它可以解析任何无上下文的语言,如果没有,那会是什么样的反例？

(确切地说,"解析"是指"构建一个接受语法X生成的所有字符串并拒绝所有其他字符串的单个正则表达式").

添加:我特别感兴趣的是看到现代正则表达式引擎(Perl,Net,python正则表达式模块)无法解析的无上下文语言的示例.

Answer 1

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

总结一下:

• 支持递归子模式引用的正则表达式可以匹配所有无上下文语言(例如a^n b^n).
• 具有环绕声断言和子模式引用的正则表达式可以匹配至少一些上下文敏感语言(例如ww和a^n b^n c^n).
• 如果断言具有无限宽度(如您所说),则可以匹配所有上下文相关语法.虽然对lookbehind没有固定宽度限制(并且同时支持子模式引用),但我不知道任何正则表达式的味道.
• 具有反向引用的正则表达式是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
  

Answer 2

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

实际上,形式语言理论中的正则表达式只与正则表达式有轻微关系.在最一般的情况下,具有无限反向引用的匹配正则数是NP-Complete,因此对于足够强大的正则表达式的所有模式匹配算法都是指数的,至少在一般情况下是如此.然而,对于大多数输入而言,它们都非常快.众所周知,匹配无上下文的语言最多比某些东西更快n^3,因此正则表达式中的某些语言不是无上下文的(例如ww),但并非所有无上下文的语言都可以被正则表达式解析.类型0语言通常是不可判定的,儿子正则表达不到那里.

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