现代正则表达式引擎可以解析哪种形式的语言？

问题描述

在这里，人们有时会说类似您不能用正则表达式解析X，因为X不是正则语言之类的话。但是，据我了解，现代正则表达式引擎不仅可以匹配的正则语言。我的问题：的正则表达式引擎

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

what kind of languages can it parse? Can it parse any context-free language, and if not, what would be the counterexample?

（确切地说，解析是指构建一个常规表示将接受由语法X生成的所有字符串而拒绝所有其他字符串的表达式）。

(To be precise, by "parse" I mean "build a single regular expression that would accept all strings generated by the grammar X and reject all other strings").

添加：我特别想看到一个上下文示例-现代regex引擎（Perl，Net，python regex模块）无法解析的免费语言。

Add.: I'm particularly interested to see an example of a context-free language that modern regex engines (Perl, Net, python regex module) would be unable to parse.

推荐答案

我最近写了一篇有关该主题的较长文章：。

I recently wrote a rather long article on this topic: The true power of regular expressions.

总结：

• 支持递归子模式引用的正则表达式可以匹配 all 个上下文无关的语言（例如 a ^ nb ^ n ）。


• 带有环顾断言和子模式引用的正则表达式至少可以匹配 some 上下文相关语言（例如 ww 和 a ^ nb ^ nc ^ n ）。


• 如果断言具有无限的宽度（如您所说），则可以匹配 all 所有上下文相关的语法。我不知道任何正则表达式风格，尽管它对后视没有固定宽度的限制（并且同时支持子模式引用）。


• 带有后向引用的正则表达式是NP完整的，因此，可以使用正则表达式（在应用多项式时间转换之后）解决任何其他NP问题。

• Regular expressions with support for recursive subpattern references can match all context-free languages (e.g a^n b^n).
• Regular expressions with lookaround assertions and subpattern references can match at least some context-sensitive languages (e.g. ww and a^n b^n c^n).
• If the assertions have unlimited width (as you say), then all context-sensitive grammars can be matched. I don't know any regex flavor though that does not have fixed-width restrictions on lookbehind (and at the same time supports subpattern references).
• Regular expressions with backreferences are NP-complete, so any other NP problem can be solved using regular expressions (after applying a polynomial-time transformation).

一些示例：

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

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

匹配上下文相关语言 {a ^ nb ^ nc ^ n，n> 0} ：

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

这篇关于现代正则表达式引擎可以解析哪种形式的语言？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！