regex - 现代正则表达式方言不是正则吗？

Question

我在这里看到一些评论提到现代正则表达式超出了常规语言可以表示的范围。这是怎么回事？

现代正则表达式的哪些特征不是正则的？例子会很有帮助。

Answer 1

首先想到的是反向引用：

(\w*)\s\1

（匹配一组单词字符，后跟一个空格字符，然后是之前匹配的同一组）例如：hello hello匹配，hello world不匹配。

这个构造不是规则的（即：不能由规则的语法生成）。

---

Perl Compatible RegExp (PCRE) 支持的另一个不规则特性是递归模式：

\((a*|(?R))*\)

这可用于匹配平衡括号和“a”的任何组合（来自维基百科）

Answer 2

几个例子：

• 正则表达式支持分组。例如在 Ruby 中：/my (group)/.match("my group")[1]将输出“组”。将某些东西存储在一个组中需要一个外部存储，而有限自动机没有。
• 许多语言（例如 C#）支持捕获，即每个匹配项都将在堆栈中捕获 - 例如，该模式(?<MYGROUP>.)*可以执行多个“.”捕获。在同一组。
• 正如上面用户 NullUserException 所指出的，分组用于反向引用。反向引用需要一个或多个具有下推自动机功能的外部堆栈（您必须能够将某些内容推送到堆栈上，然后再查看或弹出它。
• 一些引擎有可能单独推送和弹出外部堆栈并检查堆栈是否为空。在 .NET 中，实际上(?<MYGROUP>test)是压栈，而(?<-MYGROUP>)弹出栈。
• 像 .NET 引擎这样的一些引擎有一个平衡的分组概念——外部堆栈可以同时被推送和弹出。平衡分组语法是(?<FIRSTGROUP-LASTGROUP>)从 FIRSTGROUP 堆栈上的 LASTGROUP 索引弹出 LASTGROUP 并推送捕获。这实际上可以用来匹配无限嵌套的结构，这绝对超出了有限自动机的能力。

Probably other good examples exist :-) If you are further interessted in some of the implementation details of external stacks in combination with Regex's and balanced grouping and thus higher order automata than finite automata, I once wrote two short articles on this (http://www.codeproject.com/KB/recipes/Nested_RegEx_explained.aspx and http://www.codeproject.com/KB/recipes/RegEx_Balanced_Grouping.aspx).

Anyway - finitieness or not - I blieve that the power that this extra stuff brings to the regular languages is great :-)

Br. Morten

Answer 3

确定性或非确定性有限自动机仅识别由正则表达式描述的正则语言。正则表达式的定义很简单。让S是一个字母。那么空集、空字符串和S的每个元素都是正则表达式（超过S）。设u和v为正则表达式。那么 u 和 v 的并集 ( u | v )、连接( uv ) 和闭包 ( u *)是S上的正则表达式. 这个定义很容易扩展到常规语言。没有其他表达式是正则表达式。正如所指出的，一些反向引用就是一个例子。有关常规语言和表达式的 Wikipedia 页面是很好的参考。

本质上，某些“正则表达式”不是正则的，因为无法构造特定类型的自动机来识别它们。例如，语言

{ a^ i b^ i : i <= 0 }

不规律。这是因为接受自动机需要无限多的状态，但接受常规语言的自动机必须有有限数量的状态。