顾名思义，我们可能认为正则表达式只能匹配正则语言。但是我们在实践中使用的正则表达式包含一些我不确定是否可以用它们的理论对应物来实现的东西。例如，您将如何模拟反向引用？那么问题来了：我们在实践中使用的正则表达式的理论威力是什么？你能想出一个匹配的方法{(a^n)(b^n)|n>=0}吗？怎么样{(a^n)(b^n)(c^n)|n>=0}？
问问题
2157 次
2 回答
7
您的问题的答案是，允许反向引用的“正则表达式”语言既不是常规的也不是上下文无关的。（换句话说，正如你所指出的，你不能用正则语言模拟反向引用，也不能用 CFL。）事实上，维基百科说我们在实践中使用的许多“正则表达式”语言都是NP-Complete：
许多现代工具支持的具有无限数量的反向引用的模式匹配是 NP 完全的（参见
[11]定理 6.2）。
正如其他人所建议的那样，计算机语言和库中通常支持的正则表达式语言与形式语言理论中的正则表达式是不同的动物。Larry Wall 写了关于 Perl 的“正则表达式”
'正则表达式' [...] 与真正的正则表达式仅略有相关。尽管如此，这个术语随着我们模式匹配引擎的功能而增长，所以我不打算在这里与语言的必要性作斗争。但是，我通常称它们为“正则表达式”
您问，
你能想出一种方法来匹配 {(a^n)(b^n)|n>=0} 吗？{(a^n)(b^n)(c^n)|n>=0} 呢？
我不确定您是否正在尝试测试理论正则表达式语言是否可以匹配“正方形语言”，或者您是否正在寻找（实用）正则表达式语言的实现。这是为什么前者不可能的证据；这是对Java正则表达式的后者的详细解释和实现。
于 2010-09-28T20:24:22.037 回答
4
您暗示的正则表达式的基本困难是正则表达式对它们没有“记忆”。在最纯粹的形式中，没有真正的正则表达式应该能够识别这些语言中的任何一种。根据定义，任何可以解析这些语言的正则表达式都不是正则表达式。我认为您所说的“我们使用的正则表达式是练习”的意思是扩展的正则表达式，它在技术上不是正则表达式。
您的问题的问题在于，您要求将专门设计的理论场景应用于实际情况，这几乎总是以灾难告终。
所以我的回答是一个非回答，因为我是说你必须改写问题来询问扩展正则表达式才能得到答案。
一些可能有助于解决此问题的资源：
我还将我的答案作为社区 wiki，供任何想要为这一思路做出贡献的人使用。
于 2010-09-27T17:06:31.647 回答