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

Question

我在这里看到了一些评论，它们提到现代正则表达式超出了正则语言所能表示的范围。这是怎么回事？

现代正则表达式的哪些功能不是正则的？举例说明会很有帮助。

Answer 1

首先想到的是反向引用：

(\w*)\s\1

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

此结构不是常规的(即:不能由regular grammar生成)。

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

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

这可以用来匹配括号和“a”(来自wikipedia)的任意组合。

Answer 2

下面是几个例子：

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

可能还有其他好的例子:-)如果你对外部堆栈结合正则表达式和平衡分组的一些实现细节更感兴趣，从而比有限自动机更高阶自动机，我曾经写过两篇关于这方面的短文(http://www.codeproject.com/KB/recipes/Nested_RegEx_explained.aspx和http://www.codeproject.com/KB/recipes/RegEx_Balanced_Grouping.aspx)。

不管怎样--不管是不是有限的--我相信这些额外的东西给常规语言带来的力量是巨大的:-)

Br.莫腾

Answer 3

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

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

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

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