编译原理学习笔记02：文法与语言，为什么说“形式化”是一切的起点
如果你正在啃编译原理，或者刚被词法分析实验折磨过，那么“文法”和“语言”这两个词你一定不陌生。很多同学在这块就开始犯迷糊：文法不就是一堆产生式嘛？语言不就是字符串集合嘛？这有什么好学的？但恰恰是这两章，决定了你后面看语法分析、LL(1)、LR(1)的时候是“懂”还是“背”。我当年学到这里时也没太当回事，结果到预测分析表构建那节课直接听天书，回头补了三天文法基础才缓过来。这篇笔记就把“文法和语言”这块掰开揉碎讲清楚，结合我教学和做实验过程中的一些体会，希望能帮你把地基打牢。
这篇文章适合正在学编译原理的本科生、准备考研复试的计算机学生，以及想自底向上把编译原理吃透的入门开发者。不需要你有很深的数学基础，但要有耐心，因为形式化这个东西，就是慢工出细活。
1. 先搞懂一个关键问题：为什么语言需要“文法”来描述？
大家学习计算机这么久，肯定接触过C语言、Java、Python这些高级语言。你有没有想过一个问题：同样是字母和符号组成的字符序列，为什么int a = 1;是一句合法的C语言代码，而int int = 1;在某些语境下就报错？为什么你写的代码能被编译器识别成“正确的程序”？这里面的底层机制，就是文法。
1.1 自然语言与形式语言：语感的“直觉” vs 规则的“精确”
我们先来做个类比。你学中文、学英语，靠的是语感——听多了、读多了自然就能判断“我今天吃了饭”是通顺的，“饭吃今天了我”不通顺。这种判断是概率性的，是模糊的，没人能给出100%精确的规则集，因为自然语言本身就在不断演化，例外太多。
但计算机不一样。编译器看不懂“语感”，它必须有一套精确的、无歧义的规则来判定哪些字符序列是合法的程序、哪些不是。这套精确规则就是形式文法。形式文法与其描述出来的语言合称形式语言，它和自然语言最大的区别就是：没有例外，规则说了算。
1.2 为什么不能靠“关键字列表”来识别语言？
可能有人会问：程序语言结构不都是规定的吗？我直接枚举所有合法形式不就行了？比如C语言的for循环是for(;;)，我拿模板去匹配不就可以了？这种思路在简单场景下勉强可行，但程序语言是无穷的。变量名可以无限取，表达式可以无限嵌套，例如下面的代码：
a = b + c * d - (e + f) / g;你能枚举出所有可能的赋值表达式吗？不可能。你需要的是用有限的规则去描述无限的合法句子集合。这正是文法的核心价值：用有限的产生式（规则），递归地定义出无穷多个合法的符号串。递归赋予了文法“以有限描述无限”的能力，这是语言能被机械识别和生成的基础。
从本质上说，编译原理中的所有内容——从词法到语法到语义——都是在“形式语言”这个框架下展开的。文法就是给“语言的集合”画的一条边界线：属于这条线内的就是合法程序，线外的就不是。
2. 文法的五大基本构件：终结符、非终结符、产生式、开始符号、推导
正式的定义我不绕弯子：文法G是一个四元组G = (V_N, V_T, P, S)，其中V_N是非终结符集合，V_T是终结符集合，P是产生式集合，S是开始符号。加上产生式推导的过程，我们展开说。
2.1 终结符与非终结符：一个是原子，一个是变量
终结符（Terminal）是语言中不可再分割的最小单位。在C语言里，关键字int、运算符+、分号;、标识符abc、数字常量123，这些都是终结符。它们是词法分析器（Lexer）输出的“单词”类型，也是语法树叶子节点上挂的内容。
非终结符（Nonterminal）则是语法成分的“占位符”或者“变量”，它代表一类语法结构。比如“表达式”、“赋值语句”、“循环语句”，这些都不是具体的字符，而是抽象的语法范畴。非终结符必须由产生式进一步展开，直到全部展开为终结符为止。
初学者最容易混淆的就是：终结符是“形式语言”这个集合里的字母，非终结符只是推导过程的中间标记。一个符号串如果还含有非终结符，那它就不是“语言中的句子”，只是“句型”。
2.2 产生式：文法最核心的灵魂
产生式又叫重写规则，形如α -> β，读作“α定义为β”。注意这里α和β都是符号串（可以是终结符和非终结符的混合）。产生式的本质是“替换”：在任何出现α的地方，都可以用β来替换。
举一个最简单的算术表达式文法例子：
E -> E + T | E - T | T T -> T * F | T / F | F F -> (E) | id这里E代表表达式（Expression），T代表项（Term），F代表因子（Factor），id代表任意标识符或数字。竖线|是或的意思，相当于多条产生式的简写。这个文法的奥妙在于：它用优先级层次（E -> T -> F）巧妙地规定了+、*、括号在运算中的优先级和结合性。为什么E + T而不是E + E？因为如果写成E -> E + E，会产生二义性：1 + 2 * 3可以被理解为(1+2)*3也可以理解为1+(2*3)，编译器就不知道听谁的了。这个“分层降级”的技巧几乎贯穿所有高级语言的文法定义中，后面我会再提。
2.3 推导与规约：一个从抽象到具体，一个从具体到抽象
给定文法G，如果符号串v中的某个非终结符用某条产生式的右部替换后得到w，就记作v => w，读作“v直接推导出w”。从开始符号S出发，连续进行多次替换，最终得到一个只含终结符的串，这个过程就叫做推导（Derivation）。反之，从终结符串出发，不断用产生式左部替换右部，最终归约到开始符号S，这个过程叫做规约（Reduction）。
推导是自顶向下的，规约是自底向上的。这两条路线分别对应编译器的两种核心分析方法：LL分析（自顶向下）和LR分析（自底向上）。很多同学学到语法分析时觉得“推导好懂，规约绕”，但只要你理解了“推导是规约的逆过程”，再学LR分析时会轻松很多。后面做自底向上语法分析实验的时候，你会反复体会到这种逆过程的思维。
2.4 句型、句子和语言：三者的净化过程
从开始符号S出发，每经过一步推导得到的中间串（可能含非终结符）叫句型（Sentential Form）；如果这个句型全部由终结符组成，就叫句子（Sentence）。所有句子构成的集合就是该文法定义的语言L(G)。
所以你看，从S到句子的过程，就像是一个“净化”过程：开始时全是抽象的非终结符，不断替换，最终变成纯终结符组成的句子。反过来说，判断一个字符串是否为某个文法的句子，就是看能否从S出发推出该字符串（或能否将其规约到S）。实际编译器做词法分析时，实际上就是在判断“字符流是否是语言的句子”的局部问题；语法分析则是在判断“Token串是不是语法范畴定义的句子”。
3. 文法的分类：乔姆斯基体系和各类型的特点
形式文法理论中，乔姆斯基（Chomsky）体系按产生式限制的严格程度，把文法分成了4类。这个分类在考试中几乎必考，面试也常问，一定要做到能默写、能举例子。
3.1 0型文法（短语结构文法）与1型文法（上下文有关文法）
0型文法对产生式没有任何限制，α -> β，只要α至少含一个非终结符即可。它定义的语言类也叫递归可枚举语言，对应图灵机。1型文法限制产生式α -> β必须满足|α| <= |β|，也就是右部不能比左部短，且替换时需要考虑上下文环境。所以名字叫“上下文有关”：β是否能替换α，取决于α周围是什么字符。
1型文法的典型例子：
aA -> ab意思是：只有当前面是a时，A才能替换成b。这种文法在描述自然语言时很有用，但实际程序设计语言几乎不用，因为它的分析复杂度太高。
3.2 2型文法（上下文无关文法）：高级语言的骨架
2型文法要求产生式左部必须是一个单一的非终结符，即A -> β。因为左部只有一个非终结符，替换它时不依赖周围环境，所以称为“上下文无关”。这个性质太好了——它允许我们用递归下降或者自底向上移进规约等高效算法进行语法分析，复杂度是多项式的。
绝大多数程序设计语言的核心语法结构，都用上下文无关文法描述。比如前面那个算术表达式文法就是一个标准的2型文法。到了词法层面，标识符、数字等token也常用正则文法描述，但语法层面基本就是上下文无关文法的天下。
注意一个常见误区：2型文法不是“与上下文无关的语言”，而是“规则本身不需要上下文”。语言本身可能有上下文相关的约束，比如C语言中“变量必须先声明后使用”，这属于语义阶段（符号表）检查的范畴，不完全由文法来描述。很多教材会提及“C语言不是完全的上下文无关语言”，也是这个道理。
3.3 3型文法（正规文法）与正则表达式的关系
3型文法又叫正规文法，分为右线性和左线性两种。右线性文法形式为A -> aB或A -> a，即产生式右部最多一个非终结符且在最右侧。3型文法定义的语言正好是正则语言，与正则表达式、有限自动机等价。
这就是为什么词法分析可以用正则表达式实现：因为词法规则（标识符、关键字、无符号数）基本都是3型文法描述的。我也在实验里让学生用Flex去写词法规则，本质上就是在用一种“正则文法”的变体。
四种文法的包含关系：3型 ⊂ 2型 ⊂ 1型 ⊂ 0型，每种文法的识别能力对应不同的自动机。一句话记忆：0图灵机、1线性有界自动机、2下推自动机、3有限自动机。这个对应关系在考试中经常考简答题。
4. 二义性：文法的“歧义”问题，以及为什么要消除它
二义性（Ambiguity）是文法理论中一个十分重要的考点，也是实际操作中必须避开的坑。如果一个文法存在某个句子可以对应两棵不同的语法树（或者说两个不同的最左推导），就称该文法是二义性的。
4.1 为什么会产生二义性？两个经典例子
第一个经典例子就是E -> E + E | E * E | id。对于id + id * id，你可以先展开左边的E为E * E，也可以先展开为E + E，结果就是同一个句子能推导出两种不同结构的语法树。在编译器里，这种歧义直接导致无法确定+和*谁先算、如何结合。这显然是不能接受的。
第二个经典例子是if语句。假如文法定义如下：
S -> if E then S | if E then S else S | other那么对if E then if E then S else S，else既可以匹配内层if，也可以匹配外层if，形成经典的“悬空else（dangling else）”问题。C语言中约定else匹配最近的未匹配if，这就是一种消除二义性的策略。
4.2 消除二义性：改写文法 vs 附加规则
消除二义性主要有两条路。一条是改写文法，让每个产生式都天然没有歧义，比如用优先级分层的表达式文法替代E -> E + E | E * E。这种方法的好处是不改变语法树的结构含义，坏处是文法可能变复杂。
另一条是附加外部规则，比如规定优先级、结合性，或者像C语言那样规定else的匹配规则。这种方法不改变文法，而是在分析器中加入额外的逻辑来解决冲突。实际编译器往往两种方法混用：文法尽量清晰，再配合优先级声明和特殊规则。
我在实际做语法分析实验时，比如用Yacc/Bison定义表达式时，一般就直接用%left和%right来说明运算符结合性，比费心改写文法快得多。但考试和面试时，经常要求你能手写消除二义性的文法改写方案，所以两层功夫都要练。
这里说一下我做教学时候的血泪教训：很多学生一遇到二义性文法就问“是不是这个语言本身有问题？”其实文法二义性与语言本身的二义性不是一个概念。一个语言可能存在二义性文法，也可以存在无二义性文法。只有当一个语言不论怎么定义文法都有二义性时，才叫做“固有二义性语言”。判断一个语言是否固有二义性是不可判定的（这是停机问题的推论）。考试中让你判断“某文法是否有二义性”，通常只需要找一个句子能画出两棵不同的语法树即可。
4.3 语法树与二义性的直觉理解
语法树（Parse Tree）是推导过程的可视化表示：根节点是开始符号，叶子节点是终结符，内部节点是非终结符。如果有两个不同的推导对应不同的语法树，那就是二义性。
这里有个小细节：如果两种推导只是调整了同层非终结符的展开顺序，但语法树形态相同，则不算二义性。比如最左推导和最右推导可以得到同一棵树，这种情况是正常的。判定二义性的标准永远落在“是否存在两棵不同的语法树”上。
5. 从文法到语言的关系：这部分的习题与面试题思路
学完基本概念，接下来得会做题、会用。考试和面试常出几类题，我帮你梳理一下解题思路。
5.1 给定文法，求该文法描述的语言
这类题通常给你一组产生式，让你写出它定义的语言集合。方法是从S开始，把所有可能的推导都列举出来，找规律。举一个非常经典的例子：
S -> aS | ε这里ε表示空串。反复套用S -> aS，最后再套用S -> ε，你会得到ε, a, aa, aaa, ...，所以语言是L = { a^n | n >= 0 }——注意n可以是0，因为可以直接用S -> ε推导出空串。
再复杂一点的例子：
S -> 0S1 | ε这个文法定义的语言是{ 0^n 1^n | n >= 0 }。它的巧妙之处在于，每套用一次S -> 0S1，就在左边多一个0、右边多一个1，从而保证0和1数量相等且0在左、1在右。这类题目要多做题找感觉，重点是掌握“利用递归产生成对符号”的套路。如果你发现一个文法能同时控制多个位置的符号数量，那么这个字符串就有“上下文有关”的味道了，只不过这里是用上下文无关文法“递归生成”实现的。
5.2 给定语言，设计一个文法
反向题更考验构造能力。比如让你设计文法描述L = { a^n b^m | n >= 1, m >= 1 }，你可以拆成两步：先要一个或多个a，再要一个或多个b。可以构造：
S -> AB A -> aA | a B -> bB | b再如语言L = { a^n b^n | n >= 0 }，这就要用“成对生成”的思路：
S -> aSb | ε总结一下设计文法的常用招数：外层拆分（多个部分的连接就用多个非终结符拼接）、递归生成同形串（用于成对或重复的结构）、终结符保证数量（如A -> aA | a表示至少一个a）。多练几道题之后你会发现，文法设计其实很像做拼图，规则有限但组合方式无穷。
5.3 近些年的考研与面试趋势
现在很多高校的编译原理考试不仅考计算，还考理解。比如：“请解释为什么程序设计语言用上下文无关文法而不是上下文有关文法来描述？”“什么是二义性？日常开发中如何避免？”这类问题背后考察的是对编译全流程的理解。因为编译器的语法分析器倾向于基于上下文无关文法构建，若文法过于复杂（如上下文有关），语法分析效率会很差，很难做到线性时间。这个取舍思维在工程里特别常见：不是把所有信息都塞进文法，而是把语义规则放到后续阶段处理。
实际公司在招聘时如果问编译原理，也常围绕着“你如何设计一个DSL（领域特定语言）的词法和语法”来展开。这时候文法和语言的基本功就决定了你能否设计出“既好用又不会让解析器炸掉”的语法。我自己用Yacc/Bison写小工具时，就经常先把语法用文法草稿写出来，再转换成工具代码，这样可以提前发现很多二义性和冲突问题，省去大量调错时间。
6. 学习文法时的常见误区与避坑笔记
作为过来人，我想把踩过的一些坑摆在明面上，希望大家能少走弯路。
6.1 误区一：把“终结符”和“关键字”划等号
终结符不只是关键字，还包括运算符、分隔符、标识符、数字常量等。在语法分析层面，终结符通常就是token类型的集合。更抽象地说，终结符就是该语言字母表上的符号。哪怕你自创一门语言，定义foo为一个特殊符号，那它也可以是终结符。对应地，词法分析器的任务就是从字符流中识别这些“终结符实例”，而语法分析器不再关心“字符本身”，只关心token类型。所以理解“终结符属于语法层、字符属于词法层”是打通两章的要点。
6.2 误区二：把“推导”和“展开”混为一谈
推导是“根据产生式将某个非终结符替换为另一串符号”，而很多人理解成“把顶层符号拆开”就够了，忽略了推导顺序的概念。最左推导（每次替换最左边的非终结符）和最右推导（每次替换最右边）不只是做题术语，它们分别和自顶向下分析与自底向上分析相关。比如LR分析器实质上是在模拟“最右推导的逆过程”，理解这一点之后，你就会发现shift-reduce冲突、reduce-reduce冲突这些概念不再抽象。
6.3 做实验的碎碎念：从文法到代码
如果你正在做词法分析或语法分析实验，我的建议是：先写好文法，再写代码。很多同学一上来就用if-else硬写状态机，写着写着就晕了。但如果你先把token的正规文法列出来，再将状态转换图画出来，代码的逻辑会清晰很多。语法分析实验更是如此，先用纸笔把表达式文法写清楚（带优先级分层的那种），再用递归下降程序一步一步翻译成代码。编译原理的实验核心是“从形式化定义到程序实现的映射”，而不是比拼谁的状态机写得漂亮。
6.4 教材和配套资料怎么用
经典的教材比如陈火旺的《编译原理》（那本蓝色封面），对文法和语言的讲解非常系统。但教材偏理论，有些地方比较晦涩。建议配合网课（比如哈工大、国防科大的编译原理课程）一起看，老师会画语法树、演示推导过程，直观很多。另外强烈推荐用一个小工具辅助理解：可以用Python写一个简单的文法推导生成器，或者直接在Bison/Yacc里写一个小计算器试试，亲手改一改文法看它报什么冲突，会大大加深记忆。
7. 这一章和后续章节的衔接：你的编译器学习地图
文法与语言的部分就像是编译原理的“底层操作系统”，后面所有章节都建立在这套形式化体系上。简单串一下：词法分析器是有限自动机+正规文法；语法分析器是下推自动机+上下文无关文法；语义分析基于语法树和属性文法；中间代码生成也依赖语法树结构。你越早把文法和语言搞懂，后面学起来就越通透。
举个例子，很多同学学到LL(1)文法和LR(1)文法时，又要回头翻教材看FIRST集和FOLLOW集的定义。但实际上这两个集合的概念就来自“文法推导产生式右部能推出的终结符集合”，本质上还是在跟终结符、非终结符、推导打交道。所以这一步基础扎实，后面不过是通过算法自动化地判断“某文法是否是某类可解析的文法对象”。
我个人非常喜欢一句话：编译原理是一门“精确描述与机械实现”的学科。文法给了你精确描述的手段，而编译器就是机械实现的产物。理解这句话，学编译原理的整个心态就不一样了——你不是在背算法，你是在理解一门语言“如何从文本变成机器可执行的指令”。
这一篇就写到这里。下一篇我会继续整理词法分析和正规文法的实战经验，包括如何快速写出一个支持多种token的扫描器，以及我实测踩过的一些坑。如果你正在啃编译原理，欢迎在评论区分享你遇到的看不懂的知识点，我来帮你拆。
