简介《编译原理学习指导》面向计算机专业本科生、考研复习者以及希望夯实编译器基础的开发者围绕词法分析、语法分析LL、递归下降与LR、语义分析、运行时环境、中间代码生成和代码优化等核心环节梳理学习路径并涉及正则表达式、自动机与抽象语法树等关键概念。文档重点评介《编译原理》龙书、《现代编译程序设计》和《编译原理及实践》三本经典教材比较三者在理论深度与实践侧重上的差异提示借助Tiny C以及Lex、Yacc理解编译器构建流程对教材选择困难、LR算法理解吃力或想通过小型编译器项目巩固理论的读者较有针对性。资源包共1个doc文件大小约34KB篇幅紧凑便于快速浏览、打印标注和课堂同步使用。目前已有153人学习可作为建立编译原理知识框架、安排复习顺序与规划实践的参考。1. 三本书摆在一张桌上先想清楚你要解决哪个问题编译原理这门课最劝退的地方不在理论本身而在于翻开书全是集合、闭包和自动机合上书不知道自己能写出什么。我带过几轮课程设计最常见的翻车现场是教材从头读到尾LR 分析表会手推真让写两百行扫描器就卡住。问题出在路径上——编译原理不是「读完再动手」而是每学一块理论就立刻用最小可运行的产物把它钉死正则表达式对应一个 flex 扫描器文法对应一棵语法树语法制导定义对应一次属性计算。这篇按我自己的踩坑顺序把三本经典教材的适用阶段、flex 与 bison 的配法、递归下降为什么必须先手写、以及语法树怎么变成堆栈式中间代码摊开讲。2. 三本教材怎么排顺序龙书打底、实践收口、现代设计补课网上对教材的答案通常是「先读龙书」这话对一半人是有害的。龙书的真正价值在于它开篇就用一个完整的小例子把前端到后端串了一遍让你先看见地图再看地形它的短板是把代码优化铺得太开本科阶段一头扎进数据流分析很容易出不来。另外两本恰好补的是龙书不擅长的部分——一个补现代语言特性一个补完整实现。三本书不是替代关系是流水线上的三道工序顺序错了就会反复返工。2.1 三本书各自解决什么问题先把定位摆清楚比空谈「哪本最好」有用得多。下表是我这几年给不同基础的人排书时反复改出来的版本判断维度只有三个你现在缺的是全局图景、工程细节还是完整实现经验。教材强项短板适合阶段过关标准《编译原理》俗称龙书开篇用一个例子串起全流程理论体系几十年没大变运行时环境一章讲得极细优化部分过深本科读不完也不必读完入门第一本能画出从源码到目标代码的完整流程图能解释每一步为什么存在《编译原理及实践》边讲原理边实现一个小型 C 子集编译器对 Lex/Yacc 的说明罕见地详细深度不如龙书部分章节点到为止第二本配合课程设计能跑通书里的扫描器和语法分析器能说清每个模块的输入输出《现代编译程序设计》偏工程覆盖垃圾回收、面向对象语言编译、函数式语言编译等现代话题前置要求高直接当入门书会劝退第三本按需挑章能说清自己项目里该不该引入某种内存管理或调用约定龙书最值得先读的是第一章和运行时环境那一章。第一章让你知道编译器有哪些阶段、每个阶段的输入输出是什么这是后面所有细节的挂靠点运行时环境那一章讲存储组织、存储分配策略、非局部名字的访问、参数传递、符号表、动态存储分配这些东西你写普通业务代码时天天在用却很少深究内部怎么完成读完会有一批「原来这个黑匣子是这么转的」的瞬间。这两章读透后面词法语法再难也有个坐标系。《编译原理及实践》的价值在「完整」。它带着你从零写一个能跑的小型编译器扫描器、递归下降分析器、符号表、代码生成一路走到底。国内不少教材的问题是从定义到定义读者看完不知道这些东西有什么用这本至少在每一章末尾都留下了一个能编译运行的东西。它对手工工具 Lex 和 Yacc 的讲解也是我见过最细的很多教材只提一句「可用工具生成」它会把规则文件怎么写、优先级怎么处理、常见冲突怎么消都讲清楚。《现代编译程序设计》的「现代」二字是关键。传统教材里看不到垃圾回收的具体算法看不到面向对象语言的虚函数表怎么布局看不到函数式语言的闭包怎么实现——这些内容在解释执行语言流行之后才真正变成刚需。如果你只是应付本科课程这本可以只挑垃圾回收和运行时组织两章如果你打算自己动手做一个带自动内存管理的语言这两章得反复读。2.2 一条八周能走完的路线选型定完剩下的是把时间切开。我给课程设计排的默认节奏是八周每周有可验收的产出验收不过就不往下走。这个节奏对自学同样适用只是可以把周期拉长到十二周。第一阶段两周只读龙书的前几章目标是建立图景。这两周不写代码但要动手画把「源程序 → 词法单元流 → 语法树 → 中间代码 → 目标代码」这条链画出来每一环标注输入输出和典型算法。画不出来说明没读懂回去重读。这一阶段结束时你应该能回答为什么词法分析要单独抽出来不直接塞进语法分析里。第二阶段四周跟着《编译原理及实践》实现。顺序是扫描器 → 递归下降分析器 → 符号表 → 三地址码或堆栈式中间代码。每完成一个模块就写三到五个测试用例用例要覆盖正常路径和至少一个错误路径。这四周是最容易卡住的阶段卡住时不要回去重读理论先看错误信息定位到具体模块再翻对应章节。第三阶段两周按需读《现代编译程序设计》。如果你做的语言有对象或闭包读对应章节如果只是过程式语言读垃圾回收和运行时组织即可。这一阶段的产出是一份短文档你的编译器在内存管理上做了什么选择为什么这么选代价是什么。2.3 中文版还是英文版这个问题被问得太多我的判断标准很简单理论部分读中文术语和公式回查英文。三本经典教材的中文版翻译质量整体可用读理论的效率远高于啃原文但术语对照必须自己建一张表比如 reduction、derivation、handle、viable prefix 这些词在不同译本里译法不统一做题和看论文时会打架。具体做法是读中文版时手边开一个纯文本文件遇到拿不准的术语就把中英文并列记一行遇到公式推导看不懂就去找英文版对应段落公式本身没有语言障碍难的是作者行文的逻辑连接词。我一般会建议在第二周结束前把这张术语表建到五十条以上后面读任何资料都顺。别为了「显得专业」硬读原版。理解理论的实质比理解表面的文字重要得多这句话放在这里依然成立。3. 词法分析落地从正则到 DFA再用 flex 生成第一个扫描器词法分析是整门课里最容易「以为自己会了」的部分。手写一个能跑的分词函数任何一个写过几个月代码的人都能做到但课程要你掌握的是从正则表达式到有限自动机的那条转换链以及为什么必须绕这么一圈。这条链不长正则表达式 → NFAThompson 构造→ DFA子集构造→ 最小化 DFA。每一步都有明确的算法也都有明确的代价。3.1 为什么不能跳过自动机直接写代码直接写代码的问题是没法维护。假设你要支持的关键字从十个涨到五十个手写一堆if/else分支还能勉强应付但一旦涉及「最长匹配」和「回退一个字符」手写逻辑就开始出错。正则表达式是声明式的它只描述「什么形态算一个词法单元」不描述怎么匹配DFA 是执行式的它是一张状态转移表读一个字符跳一个状态。中间那层自动机理论干的就是把声明翻译成执行。NFA 到 DFA 的子集构造本质是把「同时处于多个状态」这件事摊平成「一个状态集合」。这一步会带来状态数膨胀最坏情况是指数级但实际语言的词法规则不会走到最坏情况。DFA 最小化则是把等价状态合并让表变小。这三步在纸上手推一遍是必要的推完你才会明白为什么 lex 家族的工具都要求你写正则而不是写状态机——因为人是写不好状态机的工具写得比人好。有一个常被忽略的细节词法分析阶段就要开始维护行号和列号。很多课程设计到最后报错只能报「语法错误」没法报「第 12 行第 5 列」就是因为扫描阶段没存位置信息后面想补已经来不及。3.2 用 flex 生成扫描器flex 的规则文件分三段定义段、规则段、用户代码段。定义段放头文件、全局变量和正则的具名定义规则段一行一条「模式 动作」用户代码段放 main 和辅助函数。下面这个版本我用来做课程设计的第一版扫描器能跑通一个小型 C 子集的词法部分。%{ #include stdio.h #include stdlib.h #include string.h /* token 编号从 258 起避开单字符 ASCII方便和 bison 侧对齐 */ enum { TOK_IF 258, TOK_ELSE, TOK_WHILE, TOK_INT, TOK_ID, TOK_NUM, TOK_EQ, TOK_LE, TOK_GE }; static int line_no 1; /* 报错定位全靠它扫描阶段就得开始维护 */ %} %option noyywrap DIGIT [0-9] ID [a-zA-Z_][a-zA-Z0-9_]* NUM {DIGIT}(\.{DIGIT})? %% if { return TOK_IF; } else { return TOK_ELSE; } while { return TOK_WHILE; } int { return TOK_INT; } { return TOK_EQ; } { return TOK_LE; } { return TOK_GE; } {ID} { printf(ID(%s) , yytext); return TOK_ID; } {NUM} { printf(NUM(%s) , yytext); return TOK_NUM; } [-*/(){},;] { printf(OP(%s) , yytext); return yytext[0]; } [ \t] { /* 空白不产生 token直接吞掉 */ } \n { line_no; } . { fprintf(stderr, lex error at line %d: %s\n, line_no, yytext); } %% int main(int argc, char **argv) { if (argc 1 !(yyin fopen(argv[1], r))) { perror(argv[1]); return 1; } while (yylex() ! 0) { } /* noyywrap 时扫到文件尾返回 0 */ printf(\n); return 0; }保存成scanner.l两行命令就能出可执行文件flex -o lex.yy.c scanner.l # 生成 C 源文件-o 指定输出名 cc -O2 -o scanner lex.yy.c # 编译-O2 对状态机跳转有明显收益 ./scanner demo.c生成阶段有个参数值得单独说flex --header-filescanner.h scanner.l它会额外吐一个头文件里面是 token 宏和yylex声明。bison 侧的.y文件直接 include 这个头两边 token 编号就不会对不上——我见过太多课程设计因为手抄 token 编号抄错调了两天才发现是 258 写成了 259。规则段有三条隐性规则不写进注释里很容易翻车。第一flex 采用最长匹配同等长度下选规则表里靠前的那条所以关键字规则必须写在{ID}之前否则if永远被识别成标识符。第二yytext指向的是内部缓冲区需要长期保存的字符串必须strdup否则下一轮匹配就被覆盖。第三%option noyywrap省掉了yywrap函数的桩但也意味着只能扫一个文件多文件输入要自己维护栈。3.3 手写扫描器与生成器的边界工具不是万能的。什么时候该用 flex什么时候该手写我给一张对照表这张表在课程设计答辩时被问过好几次答清楚了说明你真的用过。维度flex 生成手写扫描器开发速度规则写完基本就能跑慢三到五倍可维护性加关键字改一行正则改分支逻辑容易漏最长匹配工具保证手写容易漏回退错误恢复弱非法字符只能报错退出可做跳过、补全、继续与解析器耦合需要头文件对齐 token完全自己控制性能状态表跳转稳定依赖写法写得好略快结论是词法规则稳定的语言用生成器需要复杂错误恢复的交互式场景手写。课程设计一般属于前者所以别在这上面耗时间把精力留给语法分析。验证扫描器有一组必测用例关键字与标识符的边界if与ifx、最长匹配不能被切成和、数字与点的歧义1.该不该是一个浮点数、注释跨行、非法字符。跑完这五组扫描器基本可以交付。4. 语法分析的两条路递归下降手写LR 交给 bison语法分析是编译原理里劝退率最高的一章LR 尤其。很多人卡在「活前缀」「句柄」这些概念上就放弃了其实这里有个认知错位课程要求你理解 LR 分析表怎么构造但不要求你手写一个 LR 分析器。这两件事的难度差一个数量级。真正该手写的是递归下降因为它简单、直观、错误信息友好而且在无数真实场景里够用。4.1 LL 与 LR 的选型理由LL 是自顶向下从开始符号出发每次选一个产生式往下推靠看下一个 token 决定选哪条。LR 是自底向上从左到右扫输入把符号往栈里移凑够一个产生式的右部就归约。表达力上 LR 严格强于 LL左递归文法 LL 处理不了LR 天然支持公共前缀 LL 要提左公因子LR 不用。但表达力不是唯一指标。手写解析器时LL 的错误信息能精确到「第 12 行期望)实际遇到;」LR 生成的解析器通常只能给一句「syntax error」。对于课程设计这种要演示、要写报告的场合错误信息的质量直接影响评分。所以我的建议是递归下降必须自己写一遍LR 用工具生成、理解原理即可。递归下降是 LL(1) 的手写形式。它有一个硬性前提文法不能有左递归不能有公共前缀。左递归会导致函数无限调用自己公共前缀会导致预测失败。改造方法固定左递归改写成循环公共前缀提取成新非终结符。这两步是纯机械操作练三五道题就熟了。4.2 递归下降手写下面这个解析器处理赋值、while、if 和四则表达式词法部分用正则手写方便和前面的 flex 版本对照。代码不长但每个方法对应一条文法产生式结构一目了然。import re # 正则里 必须排在单字符 前面否则会被切碎 TOKEN_RE re.compile(r (?PWS\s) | (?PNUM\d(?:\.\d)?) | (?PID[A-Za-z_]\w*) | (?POP|||[-*/(){},;]) , re.VERBOSE) KEYWORDS {if, else, while, int} def tokenize(src): 切成 (kind, text) 列表末尾补 EOF 让解析器有统一收口条件。 pos, out 0, [] while pos len(src): m TOKEN_RE.match(src, pos) if not m: raise SyntaxError(f非法字符 {src[pos]!r}位置 {pos}) pos m.end() kind, text m.lastgroup, m.group() if kind WS: continue if kind ID and text in KEYWORDS: kind text.upper() # 关键字单独成类解析时不必再查表 out.append((kind, text)) out.append((EOF, )) return out class Parser: def __init__(self, tokens): self.toks, self.i tokens, 0 def peek(self): return self.toks[self.i][0] def peek_text(self): return self.toks[self.i][1] def eat(self, kind): if self.peek() ! kind: raise SyntaxError(f期望 {kind}实际 {self.peek()}({self.peek_text()})) tok self.toks[self.i] self.i 1 return tok def eat_op(self, ch): 单字符运算符单独校验避免 ( 和 ) 混用同一套 eat。 if self.peek() ! OP or self.peek_text() ! ch: raise SyntaxError(f期望 {ch!r}实际 {self.peek_text()!r}) self.i 1 # expr : term (( | -) term)* def expr(self): node self.term() while self.peek() OP and self.peek_text() in (, -): op self.eat(OP)[1] node (bin, op, node, self.term()) return node # term : factor ((* | /) factor)* def term(self): node self.factor() while self.peek() OP and self.peek_text() in (*, /): op self.eat(OP)[1] node (bin, op, node, self.factor()) return node # factor : NUM | ID | ( expr ) def factor(self): if self.peek() NUM: return (num, float(self.eat(NUM)[1])) if self.peek() ID: return (var, self.eat(ID)[1]) if self.peek() OP and self.peek_text() (: self.eat_op(() node self.expr() self.eat_op()) return node raise SyntaxError(f表达式里出现意外 token{self.toks[self.i]}) # stmt : ID expr ; | WHILE ( expr ) block | IF ( expr ) block def stmt(self): if self.peek() ID: name self.eat(ID)[1] self.eat_op() e self.expr() self.eat_op(;) return (assign, name, e) if self.peek() WHILE: self.eat(WHILE) self.eat_op(() cond self.expr() self.eat_op()) return (while, cond, self.block()) if self.peek() IF: self.eat(IF) self.eat_op(() cond self.expr() self.eat_op()) return (if, cond, self.block()) raise SyntaxError(f语句只能以标识符 / while / if 开头实际 {self.toks[self.i]}) def block(self): self.eat_op({) body [] while not (self.peek() OP and self.peek_text() }): body.append(self.stmt()) self.eat_op(}) return (block, body) def program(self): body [] while self.peek() ! EOF: body.append(self.stmt()) return (block, body) if __name__ __main__: src x 1 2 * 3; while (x 0) { x x - 1; } print(Parser(tokenize(src)).program())几处关键设计。表达式用三层函数拆开expr管加减、term管乘除、factor管括号和原子这正好对应文法的优先级层级不需要额外的优先级表。循环代替左递归expr : expr term改写成先取term再while循环栈深度从 O(n) 降到 O(1)长表达式不会爆栈。eat_op单独抽出来是因为括号、分号、等号都是 OP 类混着eat(OP)会让错误信息变成「期望 OP」等于没说。这个解析器是 LL(1) 的判断靠peek()一个 token。stmt里三条分支的首 token 互不相同ID / WHILE / IF所以不会歧义。如果加elseif后面跟不跟else就要靠更复杂的手段或者干脆在这个位置引入一个小的优先级规则。4.3 用 bison 生成 LR 解析器bison 的规则文件和 flex 结构类似声明段、规则段、用户代码段。声明段里%token声明终结符%left/%right声明结合性和优先级%define api.value.type指定语义值类型。下面这个版本和前面的扫描器配套。%{ #include stdio.h #include stdlib.h int yylex(void); void yyerror(const char *s); %} %define parse.error verbose /* 默认报错太模糊调冲突时一定要开 */ %define api.value.type {double} /* 整个语言的语义值统一用 double够用 */ %token TOK_IF TOK_ELSE TOK_WHILE TOK_INT %token TOK_ID TOK_NUM TOK_EQ TOK_LE TOK_GE %left TOK_EQ %left - %left * / %right UMINUS %% program: stmt_list ; stmt_list: /* 空 */ | stmt_list stmt ; stmt: TOK_ID expr ; { printf(assign\n); } | expr ; { printf(expr stmt\n); } ; expr: expr expr { $$ $1 $3; } | expr - expr { $$ $1 - $3; } | expr * expr { $$ $1 * $3; } | expr / expr { $$ $1 / $3; } | expr expr { $$ ($1 $3); } | - expr %prec UMINUS { $$ -$2; } | ( expr ) { $$ $2; } | TOK_NUM { $$ $1; } ; %% void yyerror(const char *s) { fprintf(stderr, parse error: %s\n, s); } int main(void) { return yyparse(); }构建流程是两步串起来的bison -d -v -o parser.tab.c parser.y # -d 生成 parser.tab.h 供扫描器 include # -v 生成 parser.output冲突信息全在里面这是调冲突的唯一依据 cc -O2 -o calc parser.tab.c lex.yy.c%left和%right的顺序有讲究越靠后优先级越高。所以乘除在一行、加减在下一行乘除自然就优先。%prec UMINUS是给一元负号单独指定优先级否则-2*3会被解析成-(2*3)而不是(-2)*3——数值上一样但语义树不同涉及副作用时就会出错。语义动作里的$1、$3指的是产生式右部第几个符号的值$$是左部的值。这里有个时机问题动作在归约时执行此时右部符号已经全部出栈所以能安全读到它们的值。很多人第一次写 bison 会以为动作是在匹配到该符号时立刻执行结果在递归产生式里拿到空值这是一个典型的翻车点。4.4 冲突排查bison 报冲突时不要猜直接看parser.output。文件里会列出每个状态的所有项和冲突动作。shift/reduce 冲突最常见的三个来源悬空 else、表达式优先级没声明、文法本身有二义性。悬空 else 的解法是给else更高的移进优先级或者改写文法表达式优先级用%left解决文法二义性只能改写。如果冲突数量是状态数的量级别急着一个个消先怀疑文法写错了。我见过一个课程设计报了 47 个冲突最后发现是stmt_list写成了右递归改回左递归后冲突降到 2 个。冲突数量本身就是一个诊断信号。5. 排查清单五个让编译器课程设计卡三天的坑课程设计的坑有一个共同特征报错信息离真正的原因很远。你看到的是「语法错误」实际原因是扫描器的 token 编号对不上你看到的是「段错误」实际原因是语义动作里访问了已经出栈的符号。下面五条是我这些年被问得最多、也是我自己踩过的按「现象 → 原因 → 解决」写清楚。5.1 工具链与环境类坑一关键字被识别成标识符。现象输入if (x 0)解析器报「期望 ID实际 ID」或者干脆把if当成变量名处理语义检查时报「未定义的变量 if」。原因flex 的最长匹配加规则顺序。{ID}这条正则能匹配if如果它的规则写在if之前且两者匹配长度相同flex 选靠前的那条于是关键字永远进不了关键字分支。解决把所有关键字规则集中写在{ID}之前并在文件里加一行注释标明顺序不可调。更稳的做法是用一张关键字哈希表{ID}匹配后查表决定返回TOK_IF还是TOK_ID这样加关键字不用改规则段也不会因为插入位置出错。坑二Windows 上找不到 flex 和 bison。现象命令行敲flex提示「不是内部或外部命令」或者装完之后bison报缺少m4。原因这两个工具原生面向 Unix 系环境Windows 没有对应的可执行文件bison 的构建还依赖 m4 宏处理器只装 bison 不装 m4 会在生成阶段失败。解决装一个 POSIX 兼容层cygwin 里自带flex.exe和bison.exe装的时候把 devel 分类下的包勾上或者用 Windows 自带的 Linux 子系统包管理器一行命令装齐。不要去找所谓「绿色版」版本对不上时生成的代码和头文件会不匹配报错信息完全误导。5.2 文法与语义动作类坑三递归下降写成左递归程序直接卡死。现象解析一个稍长的表达式时进程无响应或者栈溢出崩溃短表达式却正常。原因expr : expr term这种写法在递归下降里就是函数自己调自己第一个 token 还没消费就再次进入expr无限递归。短表达式之所以「正常」往往是因为它走的是不需要递归的那条分支属于假象。解决改写成循环。先取一个term然后while看下一个 token 是不是或-是就再取一个term并组合成新节点。这个改法对所有二元运算符都适用且把递归深度从输入长度降到文法层级。坑四bison 报 syntax error但完全看不出位置。现象解析器对任何稍微复杂一点的输入都只说一句syntax error不知道是哪个 token、哪个状态出的问题。原因bison 默认的错误信息极简且没有维护位置信息。词法侧如果不记录行号列号语法侧就算想报也报不出来。解决三步。第一.y文件里加%define parse.error verbose错误信息会带上期望的 token 列表第二flex 侧维护line_no并在每次返回 token 时把位置写进全局变量第三在yyerror里把这个全局变量打出来。三步做完错误信息会从一句话变成「第 12 行第 5 列期望)或,实际遇到;」调试效率差好几倍。坑五LR 分析表手推对了程序跑出来结果全错。现象按教材手推的分析表逐格核对无误但程序对12*3求值得到 9 而不是 7。原因语义动作的执行时机理解错了。bison 的动作在归约时执行归约发生时右部符号已经全部出栈$1、$3取的是它们入栈时存下的语义值。如果文法有优先级声明缺失12*3会被归约成(12)*3表本身没错错的是文法没有告诉解析器乘号优先。解决先查 %left本文还有配套的精品资源点击获取
