上下文无关语言和下推自动机

上下文无关文法生成具有嵌套、递归结构的语言，而下推自动机通过将有限控制器与一个无界堆栈相结合，精确地识别这些语言。

Definition

上下文无关语言是由其规则独立于上下文重写单个非终结符号的文法生成的，它由下推自动机识别，下推自动机是一种配备有堆栈的有限自动机，该堆栈提供无界深度的后进先出存储器。

Scope

本主题涵盖上下文无关文法和推导、分析树和歧义、上下文无关文法与下推自动机的等价性、乔姆斯基范式等范式、上下文无关语言的泵引理，以及将此类语言与正则语言区分开来的闭包和判定性质。

Core questions

• 哪些嵌套或递归模式需要堆栈而非有限内存？
• 为什么上下文无关文法和下推自动机在能力上是等价的？
• 文法何时是模糊的，以及歧义对解析为何重要？
• 上下文无关语言的哪些判定问题是可解的，哪些是不可解的？

Key theories

文法-自动机等价性

当且仅当一种语言能被某个下推自动机接受时，它才是上下文无关的，因此生成文法视图和堆栈机器视图描述的是同一类语言。

乔姆斯基范式

每个上下文无关文法都可以重写，使得每条规则要么产生两个非终结符，要么产生一个终结符，这种范式是解析算法和关于该类语言的归纳证明的基础。

上下文无关语言的泵引理

上下文无关语言中每个足够长的字符串都可以被分割，使其中的两部分可以一起泵出，这种性质对于需要超出堆栈内存的语言不成立，因此证明它们不是上下文无关的。

Clinical relevance

上下文无关文法规定了几乎所有编程语言和许多数据格式的语法，而下推式解析算法将这些文法转化为编译器和解释器核心的语法分析器，使本主题成为编程语言处理的理论基础。

History

乔姆斯基于20世纪50年代后期在他的层级理论中引入了上下文无关文法，巴科斯和瑙尔独立地使用它们来定义ALGOL编程语言的语法。与下推自动机的等价性以及该类语言的结构理论在20世纪60年代得到了完善。

Key figures

• Noam Chomsky
• John Backus
• Seymour Ginsburg
• Sheila Greibach

Seminal works

• sipser2013
• hopcroft2006

Frequently asked questions

为什么解析编程语言需要堆栈？

程序包含括号、代码块和函数调用等嵌套结构，其匹配深度是无界的。堆栈记录每个未完成的结构并在其关闭时弹出，这正是下推自动机提供而有限自动机缺乏的内存管理方式。

文法模糊意味着什么？

当某个字符串具有多个分析树时，即它可以通过真正不同的结构推导出来，则该文法是模糊的。歧义对于编程语言来说是不希望的，因为它使代码的含义不明确，因此语言设计者会寻求无歧义的文法或添加消歧规则。