现代编程语言中的“正则表达式”真的是“上下文相关语法”吗？

Question

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

Answer 1

特别是对捕获括号的反向引用使正则表达式比常规，无上下文或上下文敏感的语法更复杂。这个名字只是在历史上成长（尽可能多的单词）。另请参阅维基百科中的此部分以及来自Perl的示例说明。

Answer 2

我的看法是：

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

我确实知道正则表达式解析器允许您与解析器已经遇到的内容进行匹配，从而实现类似于上下文相关语法的功能。

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

期限 正则表达式, ，在我看来，主要是指 句法 用于表达那些常规语法（星号和问号）。

Answer 3

现代正则表达式实现中的一些功能违反了经典正则表达式的规则定义。

例如 Microsoft的.NET Balancing Group < ？代码>（小于 <代码> NAME1 <代码> - <代码> NAME2 <代码>＆gt;＆＃8230;） ：

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

此 匹配语言 L ＆＃8320;＆＃8321; = {＆＃949; ，01,0011,000111，＆＃8230; }。但根据抽水引理，这种语言并不常见。