刚学编译原理那阵子我和“0型、1型、2型、3型”这四个词较了很久的劲。课堂上老师一带而过PPT上全是形式化定义但一到做题总会碰到那种“看着像2型实际上因为左部多了个终结符而变成1型”的阴险题目。后来我把课程再刷了一遍又把一堆例子在手边逐条推导才算把这套分类真正吃透。这篇文章就是把我最终整理出来的东西写下来文法的四级分类到底在分什么、怎么快速判定、考试喜欢怎么考、以及它跟词法分析和语法分析到底是什么关系。不管你是正在刷编译原理课程的学生还是工作几年后回来补基础的人希望这篇笔记能帮你少走一点弯路。1. 编译前端里的文法分类到底扮演什么角色1.1 词法分析和语法分析为什么都离不开文法编译器前端要解决两件事一是把源码拆成一个个单词也就是词法分析二是把这些单词按语法规则拼成语法树也就是语法分析。不管是哪个阶段背后都需要一套“规则”来描述合法输入长什么样。这套规则在编译原理里就叫文法。你可以把文法理解成“句子生成器”。比如规定S → aS | b意思是从起始符号 S 出发可以选择生成一个 a 后面再接一个 S也可以选择直接生成 b。反复使用这些规则就能生成b、ab、aab、aaab这些字符串。反过来看这组规则也精确地描述了一类字符串的集合也就是一种语言。文法的分类就是按产生式约束的松紧程度把这套规则分成从宽到严的四档。档位不同识别这种语言的计算模型也不同处理难度更是天差地别。很多人一开始只把它当成死记硬背的概念题等到学词法分析、自顶向下分析、LR分析的时候才发现当初没理解透的地方全都成了坑。1.2 从“0型到3型”看语言约束的松紧这四个等级本质上是在回答一个问题每一条产生式 α → β可以有多自由0型文法几乎不设限只要左侧 α 至少含一个非终结符怎么写都行甚至允许左侧比右侧长。1型文法加了一条核心约束替换后符号串不能变短也就是 |α| ≤ |β|。2型文法进一步要求左侧必须是一个单独的非终结符替换时不关心周围是什么。3型文法最严格左侧是单个非终结符右侧也必须是“一个终结符加一个非终结符”或“一个终结符”这种固定形态。约束越多能描述的语言集合越小。所以存在一个著名的包含关系3型语言 ⊂ 2型语言 ⊂ 1型语言 ⊂ 0型语言。换句话说3型文法能生成的句子2型文法也能生成2型文法能生成的句子1型文法也能生成依次类推。判断一个文法属于哪一型千万不要靠感觉而是按“3型 → 2型 → 1型 → 0型”的顺序逐项排查。能够满足更严格条件就归到更严格的类型能写成3型就不写2型能写成2型就不写1型。后面我会专门展开讲这套操作流程。1.3 这门课为什么把它放在靠前位置在我上的那门编译原理课程里文法分类出现在词法分析附近。老师当时的说法是先建立“形式化描述语言”的视角后面讲有限自动机、下推自动机、语法分析算法时才接得上。后来回头看这个顺序安排非常关键。词法分析处理的是单词结构本质上就是3型文法描述的正规语言语法分析处理的语句结构本质上就是2型文法描述的上下文无关语言。如果你在文法分类这块只背了结论没搞懂产生式约束的含义学到自顶向下的递归下降分析和自底向上的LR分析时就会反复卡壳。LR分析器为什么能处理某些文法、不能处理另一些文法根子就在2型文法的框架内。2. 从0型到3型四大文法的产生式长什么样2.1 形式文法四件套VT、VN、P、S先统一一下记号。一个形式文法 G 是一个四元组G (VT, VN, P, S)。VT是终结符集合代表语言里的基本符号比如字母、数字、运算符最终生成的句子只由终结符组成。VN是非终结符集合代表可以继续展开的语法成分比如一个“句子”或“表达式”。P是产生式集合每条规则形如 α → β说明符号串 α 可以被替换成 β。S是开始符号属于非终结符所有句子的生成都从 S 出发。举个例子G ({a, b}, {S, A}, {S → aA, A → b}, S)。从这个文法出发S 先替换成 aA再把 A 替换成 b最后得到句子ab。整个过程只有一条路所以它描述的语言就是{ab}。2.2 0型文法除了“左边得有非终结符”基本不管0型文法又叫无限制文法或短结构文法。它的唯一硬性要求是每条产生式 α → β 的左侧 α 必须至少包含一个非终结符。至于 α 和 β 的长度谁大谁小、里面混不混终结符全都不管。比如下面这个文法S → aB aB → Ab Ab → ab第二条产生式aB → Ab的左侧既有终结符 a 又有非终结符 B这仍然合法因为里面确实有非终结符。第三条还出现了长度缩短左侧长度是2右侧长度也是2长度相等合法如果写成Ab → ε让左侧变没0型也允许。0型文法对应的计算模型是图灵机它描述的语言类叫递归可枚举语言。工程里很少拿0型文法来定义编程语言因为它太自由几乎没法高效解析。理解它主要是为了把理论体系的“天花板”立起来在它之上任何形式文法都逃不出这个范围。2.3 1型文法长度不递减上下文有关1型文法也叫上下文有关文法。核心约束是除了特殊情况S → ε任何产生式 α → β 都必须满足 |α| ≤ |β|。也就是说一次替换不能让符号串变短。为什么叫“上下文有关”因为1型文法通常能改写成这种形态α1 A α2 → α1 β α2意思是只有当非终结符 A 出现在 α1 这个“上文”和 α2 这个“下文”之间时才能把 A 替换成 β。替换动作依赖邻居符号所以叫“上下文有关”。举一个典型的1型文法例子A → aB aB → ab第二条aB → ab的左侧有两个符号右侧也有两个符号长度没有缩短但它不是2型文法因为左侧不是单个非终结符。这个产生式表达的含义是只有当 B 前面有一个 a 时才能把 B 替换成 b。这就是典型的上下文有关行为。识别1型语言的计算模型是线性有界自动机。这类语言在编译器领域很少直接用到但它在形式语言理论里占据重要位置很多自然语言句法研究也会用到这个模型。2.4 2型文法左侧单个非终结符搞定2型文法就是大名鼎鼎的上下文无关文法。它的要求是每条产生式左侧必须是一个非终结符右侧可以是任意符号串包括空串。A → γ这里的 γ 由终结符和非终结符任意组成。典型例子S → aSb | ε从 S 出发可以生成aSb再展开 S 又得到aaSbb最后用 ε 收尾生成aa...ab...b这种 a 和 b 数量相等的串。这个语言{anbn | n ≥ 0}用3型文法描述不了但用2型文法一句话就写完了。“上下文无关”的意思是替换 A 的时候完全不用看它左边右边是谁只要遇到 A就按规则展开。正因为这种独立性编程语言的语法几乎都用2型文法来定义。表达式、语句、函数定义全都是上下文无关这一层。语法分析阶段的递归下降、LL、LR等算法全都建立在2型文法的基础上。还要注意一点2型文法是1型文法的子集。几乎所有2型文法都天然满足 |α| ≤ |β|因为左侧长度就是1右侧长度基本不会比1短除非是 A→ε但1型给 S→ε 开了特例其他空串产生式在一些教材里也不允许。所以判断时能归到2型就别写“它也是1型”要写最能体现约束特点的那个类型。2.5 3型文法只许 A→aB 或 A→a 这种形态3型文法也叫正规文法或正则文法。它是在2型文法基础上进一步限制右侧形态。通常分成两种写法右线性文法每条产生式要么是A → aB要么是A → a。其中 a 是终结符B 是非终结符也可以允许A → ε。左线性文法每条产生式要么是A → Ba要么是A → a。注意一个3型文法只能统一用右线性或统一用左线性不能一会儿右线性一会儿左线性混着来。混用往往会导致生成的语言超出正规语言的范围到时候反而判不成3型。举个例子标识符的简单文法S → aA | bA | cA | ... | zA A → a | b | ... | z | 0 | ... | 9 | ε这就是典型的右线性文法每次只追加一个终结符然后继续保留一个非终结符往下走。它生成的正是那些由字母开头、后面跟任意字母数字的标识符。3型文法对应的计算模型是有限自动机这也是词法分析器的理论基础。后面你会看到正则表达式、NFA、DFA这一整套东西底子就在3型文法上。2.6 一张表记住整个谱系把四种类型放到一张表里对照起来记会清楚很多类型产生式约束计算模型语言类典型例子0型左侧至少含一个非终结符无长度限制图灵机递归可枚举语言S → aB, aB → Ab1型左侧至少含一个非终结符且左侧长度 ≤ 右侧长度S→ε除外线性有界自动机上下文有关语言A → aB, aB → ab2型左侧是单个非终结符下推自动机上下文无关语言S → aSb, S → ε3型左侧是单个非终结符右侧为 aB 或 a统一右线性或左线性有限自动机正规语言S → aA, A → b每次做完题把这道题对应的文法往表里套一遍判断依据就清楚了。3. 文法类型判定实战三步筛查法3.1 判定顺序与具体动作拿到一组产生式我的习惯是三步走从最严格的3型开始往下过滤查3型先看每条产生式是否都满足右线性格式A → aB | a或者都满足左线性格式A → Ba | a。这一步要特别留意左右线性混用的情况。查2型不满足3型再看左侧是否都是单个非终结符。如果是且右侧怎么写都行基本就是2型。查1型左侧不是单个非终结符那就看所有产生式是不是都满足“左侧长度 ≤ 右侧长度”但要注意给S → ε单独开绿灯。落到0型如果连长度不递减都不满足那就是0型。这个顺序不能乱。因为满足3型的一定同时满足2型、1型、0型如果一上来就查1型很可能会把该判成3型的题误判成1型。考试和作业里一般要求“最精确”的那个类型所以从严格到宽松筛查最稳妥。3.2 四个典型例子现场走一遍光说步骤不够拿四个例子实际过一遍。例1S → aS S → b第一条S → aS符合右线性A → aB的格式第二条S → b符合A → a的格式。所以它是3型文法描述的语言是{anb | n ≥ 0}。例2S → AB A → a B → bS → AB的右侧是两个非终结符不符合3型的格式。但是左侧都是单个非终结符所以是2型文法。例3aS → aA A → b第一条aS → aA的左侧是“终结符 a 非终结符 S”两个符号不是单个非终结符所以不可能是2型。再看长度左侧长度2右侧长度2满足“不递减”所以是1型文法。这个例子的含义是只有当 S 前面有 a 时才能把它替换成 A。例4S → aSb S → εS → aSb不是右线性格式排掉3型。左侧是单个非终结符满足2型条件。所以判2型。如果老师额外问“它是不是1型”答案是“是”因为除了S → ε这条特例所有产生式都不缩短长度。但更精确的类型是2型。3.3 S→ε 和空串产生式的处理产生式里出现空串是很多人的纠结点。分情况说2型文法允许A → ε只要 A 是非终结符就行没有额外限制。3型文法部分教材允许A → ε部分教材要求必须用A → a结尾。如果题目明确说“ε产生式不算正规文法”就要按课程约定来判。1型文法只有S → ε是允许的例外而且通常还要求 S 不能出现在任何产生式的右侧。如果 S 出现在右边又允许 S→ε就会破坏长度不递减的约束。判断时先看清楚题目约定不要拿着不同教材的规则套在同一种题型上。3.4 老师最爱挖的三个坑我在刷课做题时遇到最多的坑基本可以归成三类。坑一左侧多了个终结符。比如aS → aA很多人看到 S 前面多了个 a就下意识觉得“这个是上下文有关吧”于是判成1型。这一步没问题但有一部分人会把1型和0型的区别搞混认为只要左侧有终结符就是0型。其实只要长度不递减、左侧含非终结符就是1型。坑二左右线性混用。比如S → aA A → Bb第一条是右线性第二条是左线性。这种文法不能判成3型即使它生成的语言可能是正规语言。题目问的是“这个文法”属于哪一类不是“它生成的语言”属于哪一类。坑三忘了0型也要求左侧含非终结符。0型不是完全没规则如果某条产生式左侧全是终结符比如ab → ba它连0型都不算顶多叫“无类别文法”。考试一般不会出这种题但概念辨析题里出现过。4. 一门编译原理课上的考点与备考心得4.1 最常见的四类出题方式结合我上的那门课文法分类这个章节的题目主要有四类判断归类题给定一个文法问它属于0、1、2、3型中的哪一类。这种题最基础把三步筛查法练熟就能拿下。构造题给定一个语言描述让你构造对应类型的文法。比如“构造一个生成anbn的上下文无关文法”。等价改写题把某个文法改写成同类型的等价文法。比如把左线性文法改写成右线性文法或者消除某类产生式。关系辨析题判断某一类语言是否一定是另一类语言或者给两种文法让你比较能力大小。前两类出现频率最高后两类往往混在选择题和判断题里。复习时不要只背定义要拿笔把每个例子推一遍。4.2 从语言构造文法的通用思路构造题其实有套路可循。如果是正规语言优先画有限自动机再从自动机反推右线性文法。比如要生成anb画一个从状态0经 a 回到状态0、再经 b 到终态的状态图对应文法就是S → aS | b如果是上下文无关语言核心思路是“递归结构”。anbn这种配对嵌套结构用S → aSb | ε就能表达。括号匹配表达式、回文串、算术表达式也都是用递归产生式来构造。如果是上下文有关语言通常需要依赖多个非终结符在上下文中配合替换。这类题课程里讲得少考试一般只要求判断类型不要求现场构造。4.3 把谱系和自动机对应起来记课程里很爱考“某某文法对应什么自动机”这种连线题。备考时我把对应关系单独抄了一份文法类型自动机模型识别能力3型有限自动机DFA/NFA正规语言2型下推自动机上下文无关语言1型线性有界自动机上下文有关语言0型图灵机递归可枚举语言记法上有个小窍门自动机的存储能力越强对应的文法约束越宽松。有限自动机没有额外存储下推自动机多了一个栈所以能处理嵌套结构线性有界自动机有了可增长的存储带图灵机则是无限存储的终极形态。4.4 我复习时用过的笨办法分享一个笨办法但实测很有效把课程PPT里的所有文法例子抄到纸上每个例子强制自己写出三条判定理由——“为什么不是3型”“为什么不是2型”“为什么是1型/0型”。写不出来就回去翻定义。这个过程不需要做太多题二十个例子左右判型速度就会明显上来。第一次可能很慢每道题要写三五行字但写到后面会发现常见产生式长什么样一眼就能认出来。考试时看到A → aB就知道是右线性看到aS → aA就知道要查长度思路基本是条件反射。5. 跳出考试从工程角度看四种文法5.1 词法分析在跟3型文法打交道实际写编译器时词法分析器很少用手工逐字判断的更多是用正则表达式描述 token然后交给工具生成自动机。比如标识符可以写成[A-Za-z_][A-Za-z0-9_]*关键字、数字、运算符也各自对应一条正则。这套做法的理论基础就是3型文法正则表达式描述的是正规语言可以自动转换成有限自动机。这也是为什么教材说词法分析器可以使用工具自动生成。只要token模式是正则的DFA的状态数和转移关系就能自动算出来不需要手写状态迁移表。反过来说如果某个token模式不具备正规性比如需要数括号配对正则表达式就搞不定了那已经不是词法分析阶段的活得上语法分析了。5.2 语法分析的主战场是2型文法语法分析阶段处理的是嵌套结构表达式里有括号语句块里有语句函数定义里有参数表。这种结构用2型文法表达最自然。后端工具里常见的BNF、EBNF格式本质就是上下文无关文法的书写形式。比如简单的算术表达式可以写成E → E E | E * E | ( E ) | id语法分析器拿到 token 流之后根据这套产生式构建语法树。自顶向下分析用产生式做展开自底向上分析用产生式做归约无论哪条路核心都是2型文法。工程中没有人会拿1型文法去定义通用编程语言的语法因为解析成本太高而且语法分析算法在上下文无关这一层已经非常成熟。5.3 0型和1型到底还有什么用看到这里你可能会问0型和1型既然工程里基本不用学它还有什么价值从理论层面看它们是形式语言谱系的一环。搞清楚0型和1型能让你理解为什么有些语言“理论上存在”但“实际上没法高效解析”也能帮你理解计算理论里“可判定性”和“复杂度”的边界。比如图灵机停机问题就和一个0型语言上的判定问题相关。从应用层面看1型文法在自然语言处理的一些句法模型里仍有位置比如某些语言现象需要“上下文有关”的约束才能描述。编译器方向的工作确实用不到它们但作为计算机科学从业者了解这个谱系能让你在面对“语言能力”问题时更有底气。5.4 一个串起四种类型的生活类比给刚接触的人一个通俗类比0型文法像没有交通规则的路段你想怎么开就怎么开行李可以越换越少甚至把车拆了都行。1型文法像有“变道要看前后车距”的规定符号替换时得看周围环境。2型文法像每个路口有独立指示牌只要你到了这个路口不看前后车也能决定怎么走。3型文法像单行道上的接力跑每次只能向前传一棒规则极其固定。更重要的是越严格的规则越好自动化和优化。编译器优先选择3型和2型正是因为它们可以对应到有限自动机和下推自动机可判定、可实现、效率也可控。5.5 学完这里下一站是哪里文法分类不是终点它是编译原理课程前半段的支点。学会判型之后接下来顺理成章要接触的是正规表达式到有限自动机的转换、上下文无关文法的化简、LL(1)文法的判定、LR文法的构造。再往后就是属性文法和语法制导翻译。属性文法在2型文法的基础上给每个产生式挂上语义规则这样语法分析的同时就能生成中间代码或计算属性值。可以说如果文法分类的地基没打好后面这些框架都很难真正理解透。6. 常见问题速查与避坑实录6.1 高频疑问速查表整理一份速查表覆盖我见过的高频问题疑问结论文法里有 S→ε还能算1型吗通常允许但要求 S 不出现在任何产生式右侧A→ε 属于2型吗属于上下文无关文法允许空串产生式左线性右线性混用算什么不能直接算3型即使生成语言是正规的2型文法一定是1型吗是但做题时应该归到更精确的2型二义性文法属于哪种类型二义性不影响归类2型文法也可以有二义性判断时看语言还是看文法看文法本身同一语言可以有不同类型的文法这些问题的通病是把“语言”和“文法”搞混了。语言是句子的集合文法是生成句子的规则。同一个语言完全可以用不同类型的文法来描述题目问的是其中某一个具体文法所以要按产生式形态来判断。6.2 我实际踩过的一个归类错误说一个我真实踩过的坑。有一道题给了这样一个文法S → aS S → A A → ε我第一眼看到S → A和A → ε直觉反应是“左侧都是单个非终结符应该算2型”。然后我就忽略了一个关键点S → A这种产生式右侧只有一个非终结符它不满足3型右线性A → aB的格式因为右侧缺少终结符开头但也不是完全够不着。实际上题目老师想考的是判断时A → ε在部分教材里不算正规文法的合法产生式而S → A也不能归入右线性。最后归类要按课程定义来。那次错让我养成了一个习惯每道判型题先写出题目的文法约定再逐条检查。不要跳步不要依赖“看起来像”。6.3 给新手的三个判型习惯最后分享三个我在实操中沉淀下来的习惯习惯一先把所有产生式抄成列表。不要边看边判容易漏。抄完再在每条产生式旁边标注它符合哪种格式。习惯二用排除法写“否定理由”。判断成一个类型前先写一句“它不是3型因为哪条不符合”。这样做能逼自己去核对约束条件而不是靠感觉。习惯三拿增广文法做练习。自己给文法加一个S → S的起始规则再看类型是否变化这能帮你理解“增广文法”和原文法之间的关系。很多自动机构造题都建立在增广文法的思路上。我自己复习到最后最大的体会是文法分类不靠背靠“对着产生式逐条找约束”。把四条规则当成四个漏斗从最严的开始筛筛到哪层就是哪层。课程里那些看着吓人的题目其实都是在同一个流程上加了点干扰项而已。学完这个章节再回去看词法分析、语法分析你会明显感觉到整个编译前端的地基稳了很多。