乔姆斯基层级

定义

乔姆斯基层级(Chomsky Hierarchy)是语言学家 Noam Chomsky 于 1956 年提出的形式文法分类体系,按产生式的受限程度把文法与其生成的语言分为四级,能力逐级增强。

四个层级

3 型(正则文法)对应有限自动机,可被正则表达式识别;2 型(上下文无关文法)对应下推自动机,是编程语言语法的主要工具;1 型(上下文相关文法)对应线性有界自动机;0 型(无限制文法)对应图灵机,生成递归可枚举语言。

与编译的关系

编译器前端正是层级的工程落地:词法分析用正则语言切分记号,语法分析用上下文无关文法构造语法树;而「变量须先声明后使用」等上下文相关约束,则交由语义分析处理而非文法本身表达。

意义

该层级把语言、文法、自动机三者一一对应,是形式语言与自动机理论的骨架,也界定了各类解析技术的能力边界。