我知道正则表达式包不仅可以识别常规语言，还可以识别更多种语言，但是在Python regex to find arithmetic expressions in text strings中使用递归正则表达式使我怀疑是否可以识别 any 上下文使用正则表达式的免费语言，如果没有，有人可以提供反例吗？
michaelmars 回答：regex可以用于识别任何上下文无关语言吗？
基本上，此答案摘自this个很棒的博客文章。
所以简短的答案是带有递归扩展的正则表达式可以识别任何上下文无关的语法。
表明这一点的目的是展示一种从上下文无关的语法构造正则表达式的方法。
(?<name> ...)定义了一个正则表达式模式，以后可以与(?&name)重用。
任何上下文无关的语法都可以编写为以下形式的规则集：
-
A -> BC -
A -> a
如果我们可以将这些规则编写为正则表达式，则正则表达式可以识别任何上下文无关的语言。唯一有趣的规则是第一个规则。
首先，如果规则是左递归，则由于正则表达式仅支持右递归，因此我们需要将其重写为右递归规则。始终可以进行这种重写。现在我们可以编写所有这样的规则，如下所示：
A -> BC
A -> DE
(?<A>(?&B)(?&C)|(?&D)(?&E))
这允许定义任意CFG规则，因此我们只需要全部定义它们，然后匹配初始规则即可。
(?(DEFINE)define rules here)^(?&initial)$
这里(?(DEFINE)...)声明了不匹配的规则，而initial则是语法的初始规则。
自从我听说过理论CS课程以来已经有一段时间了，所以如果有错误，请纠正我：）