正则表达式和嵌套模式：最终的答案是什么？

Question

这个问题和它的答案都表明:

1. 可以使用正则表达式匹配嵌套模式。

2. 这是不可能的，因为嵌套模式不是常规语言和因此dfa(正则表达式)不能识别它们。

在阅读上述问题的答案(https://stackoverflow.com/a/3851098/2876289)之前，我总是站在2的一边。但是现在我不太确定了。

'/(((?>[^()]+|(?1))*))/'

真的匹配嵌套模式吗?

被问到-我尝试了上面的vim(和JavaScript)，它不起作用。虽然它可能需要转换为不同的语法。引用它的答案有9个赞成

Answer 1

你必须区分以下三件事:

1. regex的实现，具有处理嵌套事物的特性。
没有这些特性的正则表达式的
2. 实现
3. 理论意义上的"正则表达式"

case 1:我知道有两个特性可以处理嵌套括号(或其他东西)

• 引用捕获组的子模式的能力，这是您的示例的情况:

  (((?>[^()]+|(?1))*))

(?1)表示捕获组1(在自身内部获得递归)

此功能可在PCRE正则表达式引擎(PHP, R，)， Ruby(使用oniguruma语法)，Perl, Python的新正则表达式模块，javascript的XRegExp库，libboost…

• 一个堆栈系统，像。net:

  (?:[^()]|(?<Open>[(])|(?<-Open>[)]))*(?(Open)(?!))

(看看这篇优秀的文章，了解更多信息。)

case 2:不具有这些特性的实现:Javascript, Python的re模块，Java…

case 3:在理论意义上，"正则表达式"是对正则语言的描述。由于未确定的嵌套级别不是正则语言，因此不能用"正则表达式"来描述它。然而，重要的一点是，对术语"正则表达式"的接受与术语"regex"(或"正则表达式")没有多大关系，因为它通常被使用，这是对语言的误用。