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

Question

多年来,"正则表达式"模式匹配越来越强大,我想知道:它真的只是上下文敏感 - 语法匹配吗？它是无上下文语法匹配的变体/扩展吗？它现在在哪里,为什么我们不称之为旧的,限制性的"正则表达式"？

Answer 1

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

Answer 2

我的看法是：

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

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

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

术语正则表达式，在我看来，主要是指语法来表达那些正规文法（星星和问号）。