企业官网建设流程全解析

简介：《编译原理学习指导》是一份面向计算机专业本科生、考研复习者及自学编译技术读者的doc文档，围绕编译原理课程的重点与难点梳理学习路径。正文从编译器基本工作流程出发，串联词法分析、语法分析与语义分析、运行时环境、中间代码生成和代码优化等环节，并对龙书、《现代编译程序设计》《编译原理及实践》三本经典教材的特点、实践侧重与适用人群作出比较，便于读者按自身基础选择参考书。压缩包内共1个doc文件，大小约34KB，篇幅精炼，适合作为课程复习提纲、入门阅读索引或考研知识点梳理材料。已有153人学习，可帮助读者快速建立编译原理知识框架，理解正则表达式与自动机、LL与LR分析等算法要点，并结合Tiny C等实践线索安排后续学习。

1. 编译原理：真正写编译器的人少，靠它运用的人多

一个反直觉的事实是：学完编译原理的人里，最终去写编译器的人不到百分之一，但这门课的产出物几乎渗透在每个开发者每天都在用的东西里——正则引擎、JSON 解析器、SQL 解析器、IDE 的语法高亮与自动补全、模板引擎、配置文件的 DSL，本质上都是编译原理那几个阶段的裁剪版。它之所以是本科必修、考研必考，不是因为编译器本身有多重要，而是因为「把一段无结构文本，机械地、可证明地转换成另一种结构」这件事，被它抽象成了一套可以复用的算法。这套算法的价值，远远超过一个能跑起来的编译器。理解这一点，后面的龙书、Tiny C、Lex 与 Yacc 才不是散落的知识点，而是一条线上的不同环节。

2. 词法分析与语法分析：一串字符是怎么被压成语法树的

编译器前端要解决的第一个问题是：程序员写下的东西对机器来说是纯粹的字节流，而后续所有处理都希望拿到结构化的数据。这个转换被切成两步——词法分析把字符流压成记号流，语法分析把记号流压成语法树。切两刀而不是一刀，是整门课里第一个值得琢磨的工程决策。

2.1 为什么要把「认单词」这件事单独拆出来

如果只有一个阶段，那么文法里每一条产生式都得从单个字符写起。一个if关键字要写成'i' 'f'，一个标识符要写成letter (letter | digit)*的展开，一个浮点数字面量更是要写出一大串状态。结果就是上下文无关文法的规模成倍膨胀，语法分析器的状态数跟着爆炸，冲突也会成倍增加。把这一层剥出去之后，词法层用正则文法（3 型）解决，语法层用上下文无关文法（2 型）解决，两层各用各自领域里最成熟的算法，互不干扰。这本质上是乔姆斯基层级在工程上的一次落地：能用弱模型描述的部分，就不要丢给强模型。

词法分析器的输出是一串 token，每个 token 至少要带三样东西：类别（关键字、标识符、整数、运算符）、词素（原始文本）、位置（行号、列号）。前两个供语法分析用，第三个平时没人注意，但一旦你要做错误提示——「第 12 行第 8 列：期望)」——它就是唯一的依据。很多手写扫描器最后被嫌弃，不是因为扫得慢，而是因为位置信息没维护好，报错报到姥姥家去了。

词法层有两条不成文但必须遵守的规则。第一是最长匹配：遇到>=，不能先返回>再返回=，必须一路吃到不能再吃为止。第二是规则优先级：当if既能匹配关键字规则又能匹配标识符规则时，按声明顺序取先声明的那个。几乎所有「为什么我的if被当成变量名」的问题，根子都在第二条上。

2.2 正则表达式到有限自动机：一条可以机械执行的路径

词法规则用正则描述，但正则不能直接跑。真正在跑的是一台有限自动机。中间的转换路径是固定的两步：先用 Thompson 构造把正则变成带 ε 边的 NFA，再用子集构造把 NFA 变成 DFA。这条路径之所以重要，是因为它全程机械，不需要任何灵感——这正是编译器这门课反复想传达的东西：只要形式化到位，构造过程就可以交给程序。

子集构造的核心思想是：NFA 在读完某个前缀后，可能同时处于多个状态，那就把这「一组状态」整体当成 DFA 的一个状态。ε 边意味着不读入字符也能跳转，所以要先做 ε-闭包。

# 子集构造：NFA -> DFA # nfa 用邻接表表示：{状态: {输入字符: {目标状态集合}}}，'' 键表示 ε 边 def epsilon_closure(nfa, states): """从一组状态出发，沿 ε 边走到底能得到的所有状态""" stack = list(states) closure = set(states) while stack: s = stack.pop() for t in nfa.get(s, {}).get('', ()): if t not in closure: closure.add(t) stack.append(t) return frozenset(closure) def subset_construction(nfa, start, accepts): start_set = epsilon_closure(nfa, {start}) dfa, dfa_accept = {}, set() queue, seen = [start_set], {start_set} while queue: cur = queue.pop(0) if cur & accepts: # 集合里含任一 NFA 接受态，DFA 该状态即接受 dfa_accept.add(cur) # 收集当前状态集合上所有可能的出边字符 symbols = set() for s in cur: symbols |= {c for c in nfa.get(s, {}) if c != ''} trans = {} for c in symbols: nxt = set() for s in cur: nxt |= nfa.get(s, {}).get(c, set()) nxt = epsilon_closure(nfa, nxt) if nxt: # 空集是死状态，直接丢弃 trans[c] = nxt if nxt not in seen: seen.add(nxt) queue.append(nxt) dfa[cur] = trans return dfa, dfa_accept

这段代码里，epsilon_closure的复杂度是 O(状态数 + ε 边数)，subset_construction的最坏状态数是 2 的 n 次方，但实际词法规则都是局部的短正则，几乎不会触发爆炸。dfa_accept单独用一个集合存，是因为 DFA 状态本身是个 frozenset，不能直接打标记。生成完 DFA 之后还可以做一次最小化（Hopcroft 算法按等价类划分），把状态数再压一轮，这一步在工具链里是默认开的。

为什么非要走到 DFA 不可？因为 DFA 的每个状态对每个输入字符最多只有一条出边，扫描一个长度为 n 的输入就是 n 次查表，O(n) 且不需要回溯。NFA 则要同时维护一个状态集合，每读一个字符都要对集合里每个元素做转移，虽然也能跑，但常数大得多，而且没法直接做成一张二维表。flex 这类工具干的事，就是把你的正则规则编译成一张状态 × 字符的转移表，再配一张状态 → 接受的动作表；运行期就是一个while循环加两次数组下标。

2.3 手写扫描器还是让工具生成

这是新手第一个真正的选择点，两条路都有人走通，但适用场景差别很大。

手写扫描器最容易被低估的一点是前瞻（peek）。比如你看到/，它可能是除号，也可能是注释开头，必须再看一个字符才能定。手写时用一个peek()函数就能解决，而用工具生成时，这类跨字符的上下文判断反而要绕一圈，通常得靠更长的正则去覆盖。反过来，一旦词法规则上到几十条，手写版本的分支会变得难以测试，漏掉某个边界组合是常有的事，这时候工具生成的确定性优势就体现出来了。

3. 语法分析：LL 和 LR 的分岔，为什么大多数人卡在 LR

词法层交出来的是扁平的 token 序列，语法层要把它变成树。这一步是整个前端里理论密度最高的地方，也是自学最容易折戟的地方。两条主流路线——自顶向下的 LL 和自底向上的 LR——不是难度递进关系，而是两种完全不同的思维方式。

3.1 自顶向下：递归下降为什么值得先写一遍

LL 的核心是「从开始符号出发，不断用产生式替换非终结符，直到匹配上输入」。落到代码上就是递归下降：每个非终结符写成一个函数，函数体的结构直接照抄产生式的右部，遇到终结符就吃掉一个 token，遇到非终结符就调用对应的函数。

这种写法几乎没有门槛，唯一需要处理的是左递归。形如expr := expr '+' term的产生式，直接翻译成函数就是函数第一句调用自己，栈立刻爆掉。标准做法是改写成循环：

# 递归下降：按优先级分层，用循环消化左递归 class Parser: def __init__(self, tokens): self.toks, self.pos = tokens, 0 def peek(self): return self.toks[self.pos] if self.pos < len(self.toks) else ('EOF', '') def eat(self, kind): tok = self.peek() if tok[0] != kind: # 错误信息带上实际 token，便于定位 raise SyntaxError(f'期望 {kind}，实际 {tok}') self.pos += 1 return tok # expr := term (('+' | '-') term)* def expr(self): node = self.term() while self.peek()[0] in ('+', '-'): # 循环等价于消除左递归 op = self.eat(self.peek()[0])[0] node = ('bin', op, node, self.term()) # 边读边折叠，保证左结合 return node # term := factor (('*' | '/') factor)* def term(self): node = self.factor() while self.peek()[0] in ('*', '/'): op = self.eat(self.peek()[0])[0] node = ('bin', op, node, self.factor()) return node def factor(self): tok = self.peek() if tok[0] == 'NUM': self.eat('NUM') return ('num', tok[1]) if tok[0] == '(': self.eat('(') node = self.expr() self.eat(')') return node raise SyntaxError(f'意外的 token: {tok}')

这段代码里有两个细节值得说。第一，优先级不是靠一张表算出来的，而是靠函数的调用层次硬编码出来的：expr调用term，term调用factor，层级越深优先级越高，天然形成结合律。第二，node = ('bin', op, node, ...)这个折叠顺序决定了左结合，如果想改成右结合，就得先递归再构造。递归下降写起来舒服，代价是它只能处理 LL(1) 文法——每遇到一个非终结符，光看下一个 token 就必须能唯一确定走哪条产生式。做不到就要提左公因子，或者退化成带回溯的写法，而回溯在语法分析里基本等于性能灾难。

普通的 LL(1) 走不通时，还有一个工程上更常用的变体：算符优先 + 优先级爬升。它不按文法分层，而是给每个运算符一个优先级数字，用一次循环加递归处理所有二元运算。很多手写的表达式解析器最后都收敛到这个形态，因为它的代码量和可维护性都明显更好。

3.2 自底向上：LR 的移进-归约在维护什么

LR 走的是反方向：从输入串出发，不断把「句柄」归约成非终结符，直到归约到开始符号。它维护两个栈，一个状态栈一个符号栈，每一步看栈顶状态和当前输入符号，查一张 ACTION 表，决定是移进（把符号压栈）还是归约（按某条产生式把栈顶若干个符号换成左部）。

这张 ACTION 表怎么来的，就是 LR 劝退人的地方。构造过程是：给文法加一个增广开始符号，为每个产生式在每个位置生成「项目」，用闭包和 GOTO 函数把所有项目集算出来，每个项目集就是自动机的一个状态。归约项里那个「点」后面的展望符，决定了你是 LR(0)、SLR、LR(1) 还是 LALR。

这几者的差别是纯粹的取舍。LR(0) 不看展望符，状态最少，但冲突最多；SLR 在归约时额外检查 FOLLOW 集，能消掉一批冲突，代价很小；LR(1) 给每个项目带上精确的展望符，冲突最少，但状态数可能翻几倍；LALR 把 LR(1) 里「核心项目相同、展望符不同」的状态合并，状态数回到 LR(0) 的量级，代价是可能引入新的归约-归约冲突。工业界的工具基本都选 LALR，因为它在表大小和表达能力之间取了个实用的平衡点。

理解到这一层，其实就够了。真正手算项目集 closure 的场合，除了考试，几乎不存在。

3.3 冲突从哪来：移进-归约与归约-归约

冲突是 LR 构造过程中必然遇到的东西，也是最容易让人怀疑自己算错的地方。它只有两种。

移进-归约冲突的经典例子是悬空 else：if E then S和if E then S else S两条产生式，在遇到else时，既可以归约成不带 else 的语句，也可以移进继续构造带 else 的版本。几乎所有语言都约定「else 就近匹配」，也就是默认移进。

归约-归约冲突则通常意味着文法本身有问题：两个不同的非终结符在同一个状态下都能归约，说明存在二义性或者文法没有做适当的因子提取。表达式文法的E := E + E | E * E | id就是典型，它同时有二义性和优先级缺失。

排查这类问题，最有效的手段不是盯着文法看，而是让工具把状态机打出来。以 bison 为例，加上-v参数会生成一个.output文件，里面列出每个状态的项目集、转移关系和冲突标记，直接定位到是哪两条规则在打架。解决方式无非三种：改文法消除二义性、用%left%right%nonassoc声明优先级和结合性把冲突交给工具自动裁决、或者显式指定默认动作并接受它。

4. 语义分析与运行时环境：类型检查与栈帧背后的账

语法树只保证了「形状对」，不管「意思对不对」。把浮点数赋给整型变量在语法上完全合法，编译器必须在语义阶段把它拦下来。这一阶段做的事看起来零散——类型检查、符号表、作用域——但它们共享同一个底层结构：属性。

4.1 语法制导翻译：把语义挂在语法树上

属性文法的思路是给文法符号挂属性，再用一组方程描述属性之间怎么算。综合属性由子节点算父节点，适合自底向上；继承属性由父节点或兄弟节点算自己，适合自顶向下。类型检查就是最典型的应用：一个表达式节点的类型，由它两个子表达式的类型和运算符共同决定。

# 类型检查：在语法树上递归求类型，顺便做兼容性判定 def check(node, env): tag = node[0] if tag == 'num': return 'int' if tag == 'bin': _, op, left, right = node lt, rt = check(left, env), check(right, env) if lt != rt: if {lt, rt} == {'int', 'float'}: # 隐式提升：窄类型向宽类型靠拢，这是 C 系语言的常见策略 return 'float' raise TypeError(f'{op} 两侧类型不兼容: {lt} vs {rt}') return lt if tag == 'assign': _, name, value = node vt = check(value, env) declared = env.lookup(name) if declared is None: raise NameError(f'未声明的变量: {name}') if not assignable(vt, declared): raise TypeError(f'不能把 {vt} 赋给 {declared} 类型的 {name}') return declared raise TypeError(f'未知节点: {tag}')

env是符号表，check是一个纯递归函数，返回值就是该子树的类型。assignable决定宽窄转换规则，这段逻辑在不同语言里差别极大：C 允许隐式截断，只给警告；强类型语言直接报错；支持多态的语言还要在这里做重载决议。类型系统一旦引入参数化类型或者子类型，这套递归就要扩展成约束求解，复杂度是另一个量级。

类型等价也有两种判定方式。结构等价看两个类型的构造方式是否一致，名字等价看它们是不是同一个声明。前者实现简单但容易出现「两个字段完全相同的结构体被当成同一个类型」的诡异行为，后者实现复杂但语义清晰。绝大多数现代语言走的是名字等价加上某种形式的别名展开。

4.2 符号表：作用域是怎么被压栈弹栈的

符号表在实现上通常是一个哈希表加一个作用域栈。进入一个块就压一层，离开就弹一层；查找时从栈顶往下扫，第一个命中的就是当前可见的定义。这个「从内往外找」的过程，正好对应语言里的名字遮蔽规则。

非局部名字的访问是这里的难点。一个函数里引用了外层函数的变量，运行时怎么找到它？两种主流方案：静态链（每个活动记录里存一个指针指向定义它的外层活动记录）和 display 表（一个按嵌套深度索引的全局数组，直接存各层活动记录的地址）。静态链省空间但访问要顺着链走，嵌套越深越慢；display 表访问是 O(1)，但要额外维护一个数组。选择哪一个，本质上是时间换空间的经典取舍。

4.3 活动记录：一次函数调用在内存里长什么样

这是编译原理里最容易被低估、但实际收益最大的部分。一次函数调用发生时，栈上会分配一块连续内存，叫活动记录，布局大致如下。

参数传递方式直接影响这块内存的语义。值传递复制一份，函数里改不动外面的；引用传递传地址，改得动；值-结果在进入时复制、返回时写回，看起来像值传递但能影响外部；名字传递则是每次访问都重新求值，实现复杂，现代语言基本不用了。

再往外一层是堆。malloc和new拿到的内存不遵循栈的后进先出规则，生命周期由程序自己控制或者交给垃圾回收。这一点在传统的编译原理教材里往往一笔带过，因为早期的编译目标语言没有自动内存管理；但现代语言几乎都带 GC，堆上的对象布局、根集合扫描、分代回收策略，已经成了编译器后端不可回避的一部分。选教材时这也是一个区分点：偏原理的老教材讲不到这里，偏工程的新教材会专门开章节。

5. 自己动手写编译器：五个最容易翻车的地方

理论看完，真正动手的时候，坑几乎都集中在几个固定的位置。下面这几条是反复被踩出来的。

5.1 现象：啃了两周 LR 表的构造，还是写不出一行解析代码

原因在于把「理解」和「手推」混为一谈了。LR 项目集的闭包计算是给工具用的，不是给人用的；课程要求你理解它在干什么，不要求你拿纸笔把一张表的每个格子算出来。卡在这里的人，往往是把手段当成了目的。

解决路径是先绕过去：写一个只支持加减乘除和括号的递归下降解析器，一百行以内跑通，建立「解析器就是一个吃 token 的函数」这个直觉。回头再看 LR，关注点就变成「它比 LL 强在哪、为什么会冲突」，而不是「这个 closure 怎么算」。等真的需要 LR 的时候，用工具生成，把它当黑匣子，只看输入文法和输出的冲突报告。

5.2 现象：照着教程装工具，命令一跑就报一堆看不懂的错

原因通常有两个。一是工具链的环境假设和你所在的环境不一致，词法/语法生成工具长期生长在类 Unix 环境里，换个平台之后路径、换行符、可执行文件后缀全都会出问题。二是文件格式本身写错了，.l和.y文件都是三段式结构，用%%分隔，少一个百分号或者多一个空行，报错信息就会指向完全无关的行号。

解决方式是先做最小验证：写一个只有三条规则、能识别int和标识符的.l文件，跑通生成和编译两步，确认工具链本身没问题，再往上加规则。报错时永远先看第一个错误，后面的多半是连锁反应。如果环境实在不顺，纯手写扫描器加递归下降是完全可行的替代路线，语言选一个自带字符串处理的就行，不必卡在工具上。

5.3 现象：语法文件写到几百行，工具报出几十个冲突，改一个冒出来三个

原因是文法本身有二义性，或者左递归没消除，或者优先级没有声明。手写一门语言的完整文法是极高难度的工作，包含大量边界情况和历史包袱，从零开始写几乎必然陷入「改一处崩三处」的循环。

解决办法是站在现成的肩膀上。公开可获取的文法文件非常多，常见语言和若干教学用的迷你语言都有成熟版本，直接拿来改是最省时间的做法。如果一定要自己写，就先把语言裁剪到一个极小的子集——只有整数、赋值、if、while、函数调用——把冲突清零，再逐步加特性，每加一个跑一次冲突检查。

5.4 现象：决定直接生成机器码，然后卡在寄存器分配上一个月没进展

原因是后端和前端的难度不在一个量级。寄存器分配本质上是图着色问题，属于 NP 完全问题，工业级实现要用上活跃变量分析、干涉图、溢出处理一整套机制。前端你还能靠直觉推进，后端一旦进入这个层面，没有系统的方法就是原地打转。

务实的做法是先做栈式中间代码：所有操作数都从栈上取、结果压回栈上，不存在寄存器不足的问题，生成过程就是一次后序遍历。等这条链路完全跑通、程序能正确算出结果了，再考虑要不要往寄存器方向走。绝大多数教学项目做到栈式虚拟机这一步，收益已经拿满了。

5.5 现象：项目做到一半发现要做的东西越来越多，最后烂尾

原因是目标定得太大。「写一个 C 编译器」这个目标里藏着预处理、结构体、指针、函数指针、可变参数、链接，任何一项单拎出来都能耗掉几周。范围失控是自学项目最常见的死法。

正确的做法是把目标砍到能端到端跑通的最小闭环：一门只有整数、四则运算、if、while、函数定义和调用的语言，能编译成字节码并由一个两百行的虚拟机执行。先让「源码进、结果出」这条链路完整走通，再按特性一个个加。每加一个特性都有可回退的基线，比一次性设计一个宏大架构然后卡在某个细节上要稳得多。

6. 选书的取舍：原理、技术实践、工程实践，你缺的是哪一块

三本经典教材的定位差异，本质上不是深浅之分，而是「你想拿它解决什么问题」之分。

选书的取舍点在于：先读一本建立坐标系，再按缺口补第二本，不要三本并读。我的血泪经验是三本同时开，结果每本都读到第三章就换，半年下来脑子里只有三套不同的符号约定。后来改成先把原理型那本从头到尾过一遍，哪怕后半部分的代码优化看得一知半解也硬着头皮读完，建立完整地图；然后跟着实践型那本把迷你编译器敲一遍，卡在哪一步再回头查对应章节。这个顺序的关键是「先有地图再走路」，反过来先动手，很容易在细节里迷失方向，不知道自己写的这坨代码在整体里处于什么位置。

验证自己有没有真学会，有个很朴素的办法：给你一段有语法错误的源码，你能不能说出编译器会在哪个阶段、以什么方式报错，报错信息里应该包含什么。说不出来，说明那条链路上的某一环还是黑匣子。从那以后我每次读完一个阶段，都会强制自己写一句「这一阶段的输入是什么、输出是什么、失败了会怎样」，写不出来就回去补，不糊弄过去。

这份学习指导里整理的三本教材定位、各阶段的重点划分，以及实践路线的先后顺序，基本就是上面这条路径的展开版，配套的说明对「哪部分该精读、哪部分知道就行」划得比较清楚。需要的话可以取来对照着自己的进度过一遍，比自己摸索该跳哪一章要省事。希望帮到你。

本文还有配套的精品资源，点击获取