regex - 现代编程语言中的“正则表达式”真的是“上下文敏感语法”吗？

Question

多年来，“正则表达式”模式匹配变得越来越强大，以至于我想知道：它真的只是上下文敏感的语法匹配吗？它是上下文无关语法匹配的变体/扩展吗？它现在在哪里，为什么我们不直接称它为旧的、限制性的“正则表达式”？

Answer 1

特别是对捕获括号的反向引用使正则表达式比常规的、上下文无关的或上下文敏感的语法更复杂。这个名字只是历史上成长的（和很多词一样）。另请参阅Wikipedia 中的此部分以及使用Perl示例的说明。

Answer 2

我的看法：

• 常规语言：
  • 由状态机匹配。在要匹配的语法中只能用一个变量来表示当前的“位置”：无法实现递归
• 上下文无关语言：
  • 由堆栈机匹配。语法中的当前“位置”由一种或另一种形式的堆栈表示。无法“记住”之前发生的任何事情
• 上下文相关语言：
  • 大多数编程语言
  • 所有大多数人类语言

我确实知道正则表达式解析器，它允许您匹配解析器已经遇到的东西，实现类似于上下文相关语法的东西。

尽管如此，正则表达式解析器，无论它们多么复杂，都不允许递归应用规则，这是上下文无关语法的明确要求。

在我看来，术语regex主要是指用于表达那些常规语法（星号和问号）的语法。

Answer 3

现代正则表达式实现中的一些特性打破了经典正则表达式定义的规则。

例如Microsoft 的 .NET平衡组 (?<name1-name2> … )：

^(?:0(?<L>)|1(?<-L>))*(?(L)(?!))$

这与语言L ₀₁ = { ε , 01, 0011, 000111, ... } 匹配。但是根据Pumping Lemma，这种语言不是规则的。