regex - 正则表达式和嵌套模式 : what's the definitive answer?

Question

这question and its answers这里建议两者:

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

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

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

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

真的匹配嵌套模式吗？

有人问 - 我在 vim(和 JavaScript)中尝试了上面的方法，但它不起作用。尽管可能需要将其转换为不同的语法。引用它的答案有 9 个赞成票。

Answer 1

你必须区分三件事:

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

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

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

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

(?1)引用捕获组1(在自身内部获得递归)

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

• 一个堆栈系统，就像在 .net 中一样:

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

(查看 this excellent post 了解更多信息。)

情况 2: 没有这些特性的实现:Javascript、Python 的 re 模块、Java...

案例 3: 在理论上，“正则表达式”是对正则语言的描述。由于不确定层级的嵌套不是正则语言，所以不能用“正则表达式”来描述。然而，重要的一点是，这种对术语“正则表达式”的接受与术语“正则表达式”(或“正则表达式”)没有太大关系，因为它是常用的，这是对语言的误用。