企业官网建设流程全解析

第一次翻开编译原理的课本，迎头撞上的就是“语言的定义”。我当时是真的有点发懵：语言不是人类说话用的东西吗，怎么到了计算机课程里还要重新定义？等我把这一节反复啃了几遍才明白，编译原理里讲的“语言”，是形式语言——说白了，就是一组按照特定规则构造出来的字符串的集合。别小看这句话，它是整个编译器的理论地基，后面那些词法分析、语法分析、语法制导翻译，全部是从“语言的定义”这五个字上长出来的。

这篇文章算是把我整理的某高校那套经典编译原理课件里“语言的定义”重新梳理了一遍，加上了我复习时踩过的坑和总结出来的记忆方法。适合正在学编译原理、准备考研复试、或者想自己动手写编译器的同学。全文不依赖特定教材，你只要把里面的概念串起来，回头再看任意一本编译原理书，这一章都会变得特别好懂。

1. 语言的定义到底在定义什么

1.1 字母表与字符串，最小积木是约定出来的

我们先做一个生活化的类比。语言是用来表达意思的，而任何表达都需要“符号”。中文用汉字当基本符号，英文用字母，编程语言用 ASCII 字符。编译原理里把这些基本符号统称为“符号”，符号的集合叫“字母表”，通常记作 Σ（西格玛）。

字母表有两个硬性要求：非空、有穷。为什么非空？因为什么都没有就谈不上构造语言。为什么必须有穷？因为在真实计算机世界里，我们不可能枚举无穷多个符号。哪怕实际字符集很大，比如 Unicode，它也是有限集合。

有了一堆符号，我们还要把它们“排成串”才有意义。符号组成的有穷序列叫“字符串”，也叫“字”或“单词”。这里有个关键特例：长度为 0 的字符串，叫“空串”，记作 ε。ε 不是一个符号，它是“什么都没有”的序列，但它非常重要。后面讨论语言是否包含空串时，它是一切麻烦的源头。

字符串还有几个约定俗成的记号：

• 长度：|w|，比如 |abc| = 3，|ε| = 0。
• 连接：把两个串接起来，比如 x = “ab”，y = “cd”，则 xy = “abcd”。
• 幂运算：w^0 = ε，w^1 = w，w^2 = ww，依次类推。
• 字母表的闭包：Σ* 表示 Σ 上所有字符串的集合，包括空串；Σ+ 表示不包括空串的集合，即 Σ* - {ε}。

你可能会觉得这不过是一堆记号，但词法分析里到处是这些记号。一个标识符能不能以数字开头，一个数字串怎么切分，本质上都是在字符串集合的框架下讨论的。

1.2 形式语言，一组字符串的集合

有了字符串，语言的正式定义就非常简洁了：

设 Σ 是一个字母表，Σ* 上的任意一个子集 L，称为 Σ 上的一个语言。

换句话说，语言就是字符串的集合。这是整个形式语言理论的出发点，干净、严格、可计算。

但这里有个容易让初学者困惑的点：自然语言怎么也能用集合定义？中文是中文句子组成的集合，英文是英文句子组成的集合，理论上当然可以，但自然语言太复杂、太模糊，用形式化方法很难精确描述。编译原理关心的不是自然语言，而是像 C 语言、Python 语言那样有严格语法的“程序设计语言”。程序设计语言的语法规则足够机械，所以能用数学工具精确刻画。这就是为什么我们一上来就放弃“语言的直觉理解”，改用集合观点。

语言集合上还可以定义运算，常用的有三种：

• 并运算：L1 ∪ L2，两个语言的句子合并。
• 连接运算：L1L2 = { xy | x ∈ L1, y ∈ L2 }，第一个语言的句子接上第二个语言的句子。
• 闭包运算：L* = L^0 ∪ L^1 ∪ L^2 ∪ …，这里 L^0 = {ε}，表示把一个语言中的句子重复拼接任意多次（包括零次）。

这些运算不是摆设。你要判断两个正则表达式是否描述同一个词法规则，要判断一个文法生成的语言和另一个文法是否等价，背后都靠这套集合运算。

2. 文法，给语言装一台生成器

2.1 文法四元组，V、T、P、S 各管什么

定义语言最直接的办法是枚举它的所有句子，但大部分有意思的语言都是无穷的，枚举不现实。所以我们需要一种“生成机制”，用有限规则描述无穷集合。这个机制就是文法。

文法的形式定义是四元组 G = (V, T, P, S)：

• V：非终结符集合。非终结符是“语法成分”，它不会被直接写出，而是会被进一步展开。你可以把它理解为句子结构里的占位符，比如“主语”“谓语”“表达式”。
• T：终结符集合。终结符是语言里真正出现的符号，比如关键字、运算符、括号。注意 V 和 T 互不相交，它们并起来叫词汇表。
• P：产生式集合。产生式的形式是 α → β，表示 α 可以替换成 β。α 必须至少含一个非终结符，β 可以是任意由终结符和非终结符组成的串，甚至可以是空串 ε。
• S：开始符号，S 必须属于 V。所有推导都从 S 出发。

举一个最简单的例子，定义“以字母开头、后面跟任意字母或数字的标识符”文法：

标识符 → 字母 余串 余串 → 字母 余串 | 数字 余串 | ε

这里“标识符”和“余串”是非终结符，具体的字母和数字是终结符，开始符号是“标识符”，产生式就是那三行。注意那个 ε，它表示余串最终可以变成空，从而结束递归。没有 ε，这个文法根本无法终止生成一个合法标识符。

2.2 推导、句型、句子，一条链路拿到语言

文法定义了，怎么从中得到语言？答案是推导。推导就是用产生式不断替换非终结符的过程。

• 如果一步就能把 α 换成 β，叫直接推导，记作 α ⇒ β。
• 如果经过多步替换，记作 α ⇒+ β（至少一步）或者 α ⇒* β（零步或更多步）。

从开始符号出发，推导出来的串有个名字叫句型。句型里可能还有非终结符没替换完。如果一个句型里只剩终结符，那它就叫句子。句子的集合就是文法生成的语言：

L(G) = { w | S ⇒+ w, 且 w ∈ T* }

注意两个细节：第一，推导至少一步，因为 S 本身不是句子；第二，w 必须全部由终结符组成。区分“句型”和“句子”是这门课最基础也最重要的语感，后面做语法树题目全靠它。

用刚才的标识符文法推一个“ab1”出来：

标识符 ⇒ 字母 余串 ⇒ a 余串 ⇒ a 字母 余串 ⇒ ab 余串 ⇒ ab 数字 余串 ⇒ ab1 余串 ⇒ ab1

每一步都是把最左边的非终结符展开，这种推导方式在后面构造语法分析器时会专门派上用场，叫最左推导。另一个极端是最右推导，两者最终都能得到同一个句子（在无二义文法下）。

2.3 递归，用有限规则描述无穷语言的关键

为什么文法能生成无穷语言？秘密全在产生式“递归”——非终结符的定义里直接或间接地用到了它自己。上面“余串”的产生式右部又出现了“余串”，一旦产生式允许这种自引用，语言规模立刻从有限变成无穷。

我举个例子方便感受。定义一个只含圆括号、并且括号匹配的语言：

S → (S) | SS | ε

这个文法能生成的句子包括 ε、()、()()、(())、(()())、((()))……无穷多个。但产生式只有三条。递归相当于给语言加了一个循环结构，循环次数没有上限，所以句子长度没有上限。如果没有递归，哪怕产生式再多，你能生成的句子总量也是有限的，一个产生式只能生成有限个符号序列的组合。

所以判断一个文法能否描述无限语言，最简单的方法就是看它有没有递归非终结符。词法规则里的标识符 → 字母 | 标识符 字母也是递归，道理完全一样。

3. Chomsky 文法体系，给语言分分类

3.1 四种文法类型，瓶子里的语言

语言有很多种，描述能力也分强弱。乔姆斯基（Chomsky）提出按产生式形式对文法分级，这是形式语言理论最有名的成果之一。分完以后，四种类型整整齐齐，你可以直接当表格背：

这里面层层包含：3 型 ⊂ 2 型 ⊂ 1 型 ⊂ 0 型。也就是说，凡是能用正规文法描述的语言，一定也能用上下文无关文法描述；反之不一定。所以正规文法的表达能力最弱，0 型文法最强。

补充一个容易忽略的细节：3 型文法分为右线性和左线性。右线性是 A → aB 或 A → a，左线性是 A → Ba 或 A → a。一个重要约定是，同一个文法里不能同时混用右线性和左线性，否则生成的语言就不是正规语言了。做题时如果看到左线性规则和右线性规则混在一起，基本可以断定有问题。

3.2 上下文无关，为什么编译器偏偏看中它

四类文法里，2 型文法，也就是上下文无关文法（CFG），是编译原理当之无愧的主角。原因很简单：几乎所有程序设计语言的语法结构都能用 CFG 描述，而且它有足够高效的解析算法，比如递归下降、LL、LR，都建立在 CFG 之上。

“上下文无关”到底是什么意思？看定义就清楚了：产生式的左部是单个非终结符 A。这意味着只要在某处看到一个非终结符 A，不管它左边是什么、右边是什么、处在什么嵌套层次里，你都可以直接把它替换成右部 β，不需要“环顾四周”。这种局部替换的特性让语法分析变得可行——分析器可以一边从左到右扫描，一边做局部决策。

对比 1 型文法，产生式形式是 αAβ → αγβ，意味着 A 能否替换成 γ，取决于它左边必须是 α、右边必须是 β。这相当于替换行为受到上下文约束。虽然表达能力更强，但解析复杂度高得多，工程上用不起。所以程序员平时写的正则表达式对应的是 3 型语言，而语法规则对应的是 2 型语言。

再区分一下 2 型和 3 型。3 型文法里，非终结符在右部最多出现一次，而且只能在最左边或最右边。这意味着它只能描述“平铺的、从左到右线性发展”的结构。而像“括号配对”“if 和 else 配对”“函数调用时左右括号匹配”这种嵌套结构，必须允许非终结符出现在串的中间并且自我递归，所以必须用 2 型文法。一个经典反例是：正则表达式无法描述a^n b^n（n 个 a 后面跟 n 个 b），因为匹配到中间时正则引擎没有“计数器记忆”能力；而 CFG 用一条 S → aSb | ε 就搞定了。

3.3 文法分类不是纯理论，工程选型都靠它

很多同学觉得 Chomsky 分类只是考试考点，跟写编译器没关系。其实关系非常大。

词法分析器用的工具是基于正则表达式的，正则表达式正好和 3 型文法等价。为什么词法敢用正则？因为标识符、关键字、数字、字符串这些“词”的结构是平铺的，没有嵌套，用 3 型文法足够。而语法分析必须处理嵌套结构，比如括号嵌套、if-else 嵌套、表达式嵌套，所以语法分析器用的工具必须支持上下文无关文法。你看编译器的经典架构：词法分析用最大匹配和状态机，语法分析用 CFG 和自顶向下/自底向上算法。这个分工不是拍脑袋定的，是形式语言分类在指导工程决策。

另一个直观例子是你手上的文本编辑器。写代码时括号自动配对高亮，编辑器需要识别嵌套结构，这本质上是 2 型语言的问题。而搜索替换功能里的正则表达式只能做 3 型匹配，所以如果你用正则去解析一个嵌套的 JSON，写出来的模式会绕到怀疑人生，最后大概率还会在深层嵌套时翻车。

4. 把语言定义落到编译器上

4.1 正规式，词法分析的地基

语言的定义和文法说起来抽象，但它们最直接的落地就是词法分析和语法分析。先看词法分析。

词法分析器要从源代码里切出一串 token，比如标识符、关键字、整数、运算符。每个 token 类型都可以用正规式描述：

• 标识符：letter (letter | digit)*
• 无符号整数：digit digit*，也就是一个数字开头，后面接任意个数字
• 关系运算符：< | > | <= | >= | == | !=

这里的*就是字母表闭包思想的延伸。正规式的三要素——字符、连接、闭包，和集合运算一一对应。词法分析器拿到这些正规式以后，会把它转换成 NFA、再转成 DFA，最后用 DFA 做状态转移来切词。整个过程完全建立在“语言是字符串集合”这个定义上。

实际工程项目里你可能用现成词法器生成器，不用手写状态机，但你仍然需要写正规式。写错一个闭包，比如把digit*写成digit digit*之外的形式，就会导致空串被误认为合法 token，扫描器在空输入上报错。这类问题追根溯源，都是语言定义没抠清楚。

4.2 上下文无关文法与语法分析

语法分析阶段拿到的输入是 token 流，任务是判断这个 token 流是不是某个句子。怎么判断？上课时老师会讲各种解析算法，但无论哪种算法，核心都是寻找一个从开始符号出发的推导，或者等价地从句子反向规约回开始符号。这就是“语言定义”在语法分析中的直接体现。

这里有个避不开的问题：二义性。同一个句子，如果文法能给出两棵不同的语法树，就说这个文法是二义的。最经典的例子是简单的算术表达式文法：

E → E + E | E * E | (E) | i

对句子i + i * i，你可以先算加法，也可以先算乘法，得到两棵不同的语法树。二义性对编译器是致命的，因为同样的输入会产生不同的语义。程序员的解决办法是改写文法，强制出优先级和结合性：

E → E + T | T T → T * F | F F → (E) | i

这个改写之后，i + i * i就只有一棵语法树，乘法必须先于加法完成。为什么能这么改？本质上是因为我们调整了产生式，让语言的定义更精确了。注意，这里我们讨论的仍然是“语言”本身，即字符串集合没有变（还是能生成所有正确的算术表达式），但文法变了，句子的结构分析就唯一了。语言和文法的关系在这里体现得非常清楚：同一个语言可以由不同的文法定义，但编译器必须挑一个适合生成分析器的文法。

4.3 从语言定义到语义，语法树只是个开始

语法分析器确认了一个句子在文法上合法，并且构造出语法树。语法树是语言定义和语义之间的桥梁。树的内部节点对应非终结符，叶节点对应终结符，整棵树其实就是推导过程的可视化。

但语言定义只解决“这句话合不合语法”，不解决“这句话什么意思”。比如a = b + c，文法能告诉你这是一个赋值语句，但变量 a 和 b 是什么类型、相加是否合法、内存怎么分配，文法本身管不了。这些属于语义分析。为了让语义分析和语法分析协同工作，编译器会在语法树节点上附加信息，比如类型、地址、符号表条目。这引出属性文法和语法制导翻译——每个产生式可以关联一段语义动作，每当分析器使用某条产生式做推导或规约，就执行对应的语义动作。

所以你会发现，整个编译前端的流程就是一条链：源代码 → 词法（正规语言） → 语法（上下文无关语言） → 语义（属性文法）→ 中间代码。链条的起点就是语言的定义。没有集合语言观，后面所有步骤都缺少精确的数学基础。

5. 实操环节，怎么判断自己真的懂了

5.1 四个高频混淆点，踩过的人特别多

我复习时遇到的问题，总结下来集中在四处理论细节上。

第一，句型和句子分不清。句型是推导中间任意状态，可能还有非终结符；句子必须全部是终结符。判断一个串是不是某个文法生成的句子，只能看它是否全部由终结符组成，并且能从 S 推导出来。很多人做错不是因为不会推，而是根本没意识到“句子”和“句型”是两个不同概念。

第二，文法书写里的竖线含义搞混。产生式里面的A → α | β是“或”的缩写，表示 A 可以替换成 α，也可以替换成 β。这跟正则表达式里的a|b是一回事。但有的初学者会把它理解成“同时成立”，导致推导时两个右部都写上，就完全错了。

第三，Σ和 Σ+ 的区别在讨论空串时失手*。Σ* 包含空串 ε，Σ+ 不包含。如果题目问“语言 L = { w | w ∈ Σ* 且 w 中至少含一个 a }”，那么 ε 显然不在 L 里。如果题目没有特别说明，很多同学会把 ε 无条件算进去或者无条件排除，都是不对的，必须按定义判断。

第四，空串 ε 不等于空集，也不等于空语言。{ε} 是一个只含一个元素的集合，这个元素就是空串；而 ∅ 才是空语言，里面一个句子也没有。这两个集合差别极大。文法 S → ε 生成的语言是 {ε}，文法 S → S（如果只这一条且不允许空串，其实生成的是空语言）生成的才是 ∅。做题时这两个必须分开写。

5.2 做题翻车现场，来看看这几个反例

“给定语言，写出文法”是这门课最常考的小题，翻车点非常集中。

第一个翻车点：漏了空串。题目要求生成语言{ a^n b^n | n ≥ 0 }，很多人直接写S → aSb | ab，完事。但 n ≥ 0 意味着 n = 0 时句子是空串，你的文法里根本没有生成空串的路径。正确答案应该是S → aSb | ε。注意ab那一条被ε替代后，最后一步推导正好能生成ab，所以ab并没有丢。

第二个翻车点：产生式的非终结符从来没有被定义。比如写S → A | B，然后只写了 A 的产生式，B 的产生式忘了。严格来说，B 没有任何产生式，它永远无法展开成终结符，语言里根本不会有由 B 生成的句子。很多批改严格的老师会直接判这个文法不合法，因为每个非终结符都应该至少出现在某条产生式的左部。

第三个翻车点：把右线性写错。3 型文法的右线性要求 A → aB 或 A → a，左线性要求 A → Ba 或 A → a。如果题目要求写正规文法，你却写了A → aBc，这就不是 3 型了。还有混用左、右线性的情况，也一定要避免。判断写出来的规则到底属于几型，其实方法很简单：逐条看产生式右部有几个非终结符、在哪里，一次就能筛出来。

5.3 一套可以复用的自检思路

我给自己的做题流程是三步走，你可以直接套用。

给一个文法求它生成的语言时，第一步先用最短的推导枚举几个最小句子，第二步寻找句子之间的模式，比如长度、前后缀、嵌套关系，第三步写出集合式表达。注意一定要检查空串是不是句子，这经常是题目想挖的坑。比如上面那个S → aSb | ε，n = 0 就是空串，别漏。

给一个语言写文法时，反向操作。第一步观察语言里句子的“骨架”，找出最小的原子串；第二步决定递归方式，是尾部递归（类似 a^n b 这种）还是嵌套递归（类似 a^n b^n 这种）；第三步特判空串，n ≥ 0 这类条件意味着 ε 大概率属于语言，需要补一条 S → ε 或在其产生式中兼容空串。第三步往往是很多人忽略导致丢分的。

最后验证时，不要只验证题目的那个目标串，要挑三类串测：最短的串、长度为 1 或 2 的边界串、明显不属于语言的非法串。能正确识别这三类，文法一般就八九不离十了。

6. 我的复习心得与记忆锚点

6.1 四个文法类型怎么记才不混

Chomsky 分类考得最多的就是“某条产生式属于几型”和“包含关系”，记忆关键是看产生式右部的形状限制从松到紧。

• 0 型：几乎不管，只要左部有非终结符就行。
• 1 型：加上一条“长度不缩减”，也就是替换不能把串变短。
• 2 型：左部必须缩成一个非终结符，此时不再管上下文。
• 3 型：右部进一步缩到至多一个非终结符，且必须在最左端或最右端。

你把这个过程理解成“逐步收紧规则”，比死记硬背稳得多。动笔判断时，按顺序检查：右部非终结符数量和位置是不是受限制？左部是不是单个非终结符？串长是不是不缩减？三步跑完，类型就定了。

6.2 学习顺序上的一个建议

如果学习这块觉得乱，我建议按“集合 → 文法 → 分类 → 识别器”的顺序走，不要从自动机倒着学。

先接受“语言是字符串集合”这个定义，然后理解“文法生成语言”这个机制，再看不同文法形态对语言描述能力的影响，最后看每一类语言对应什么自动机模型。自动机和文法是等价的，但先从文法入手更贴近编译器的直觉。等你把文法吃透，再回头学 NFA、DFA、下推自动机，会发现它们就是一个个“识别语言的机器”，理解成本会低很多。

6.3 最后分享一个我自己的小窍门

做题、读代码、看正则表达式的时候，永远先问自己三个问题：什么是字母表？什么是目标串的集合？这个集合是有限还是无限？只要这三个问题想清楚，“语言的定义”这条主线就不会断。

我自己吃了很多亏之后才意识到，编译原理这门课最怕的是概念之间互相打架，而“语言的定义”恰好是所有概念的公约数。你后面遇到正规式和文法的转换、NFA 转 DFA、LR 分析表的构造，哪怕题目再复杂，最后都可以落回这个原点：语言的集合是什么，这个集合怎么生成或者怎么识别。抓住这个锚点，整门课的路就顺了。