问正则表达式的功能是什么？

EN

你的问题的答案是，允许反向引用的“正则表达式”语言既不是正则的，也不是上下文无关的。(换句话说，正如您所指出的，您不能使用常规语言或CFL来模拟反向引用。)事实上，维基百科说，我们在实践中使用的许多“正则表达式”语言都是

正如许多现代工具所支持的那样，具有无限数量的反向引用的

模式匹配是NP完全的(参见[11]定理6.2)。

正如其他人所建议的那样，计算机语言和库中通常支持的正则表达式语言与形式语言理论中的正则表达式是不同的。与Perl“正则表达式”相关的Larry Wall wrote

‘正则表达式’...与真正的正则表达式只有很小的关系。尽管如此，随着我们的模式匹配引擎的能力，这个术语已经增长了，所以我不打算在这里尝试与语言必要性作斗争。但是，我通常将它们称为“正则表达式”。

你问我，

你能想出一个匹配{(a^n)(b^n)|n>=0}的方法吗？{(a^n)(b^n)(c^n)|n>=0}怎么样？

在这里，我不确定您是否正在尝试测试理论上的正则表达式语言是否可以与“平方语言”相匹配，或者您是否正在寻找一种(实用的)正则表达式语言的实现。java正则表达式的Here's the proof why the former is not possible;和here's a long explanation and implementation of the latter。

您所暗示的正则表达式的基本困难在于，正则表达式对它们没有“记忆”。在最纯粹的形式中，没有任何真正的正则表达式能够识别这两种语言中的任何一种。根据定义，任何可以解析这类语言的正则表达式都不是正则表达式。我认为你所说的“我们使用的正则表达式就是实践”是扩展的正则表达式，从技术上讲，它不是正则表达式。

你的问题的问题是，你要求将一个特别设计的理论场景应用于实际情况，这几乎总是以灾难告终。

所以我的回答是一种非回答，我的意思是你必须重新表述这个问题，询问关于扩展正则表达式的问题，才能得到答案。

有几个资源可能会对这个问题有所帮助：

Helpful wikipedia article

Similar StackOverflow question

Good book with a chapter on this topic

我还将我的回答作为社区维基，供任何其他想要为这一思路做出贡献的人使用。