正则表达式可用于识别任何上下文无关语言吗？

Question

[我知道正则表达式包不仅可以识别常规语言，还可以识别更多种语言，但是Python regex to find arithmetic expressions in text strings中使用递归正则表达式使我想知道是否可以使用正则表达式识别any上下文自由语言，并且如果没有，有人可以提供反例吗？

Answer 1

基本上这个答案来自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课程以来已有一段时间，所以如果有错误，请纠正我：）