简介：这份《北邮编译原理课程设计》面向学习编译原理、需要完成课程设计或自建小型编译器的读者，以Pascal语言为示例，覆盖词法分析、语法分析、语义检查、符号表管理、错误处理与代码生成等核心环节。压缩包为rar格式，共83个文件、约123KB，包含21个h头文件、19个cpp源文件、8个pas示例程序、8个asm汇编文件及8个bin可执行或二进制文件，另有rez资源脚本等，便于对照编译器各模块的实现。已有1196人学习，说明其在校内课程与自学场景中具有一定参考价值。读者可据此梳理Pascal编译器的整体结构，观察高级语言到汇编或机器指令的转换路径，并借鉴虚拟执行、测试样例与界面资源组织方式，为完成同类课程设计、理解编译流程和排查实现问题提供较完整的实践参照。
1. 编译器课设的真相：跑通只是及格线，契约稳才是分数
编译原理课程设计最反直觉的一点是：把一段几十行的文法跑通，通常只花掉总工期的三成，剩下七成全耗在三层之间的数据契约上——词法给语法的是不是带着位置信息的 token，语法给语义的是不是一棵能回溯到源码位置的语法树，语义给后端的是不是已经消解了作用域的四元式。这些接口一旦含糊，后面每加一条文法都要把旧代码重新翻一遍，血泪经验基本都出在这儿。搞懂这条链路上的机制，比背下 LL(1) 的构造算法有用得多：它决定了编译器报错时你能不能看懂它在抱怨什么，也决定了你半夜改文法时会不会把已经跑通的用例全弄翻。这套课设资料的价值，正在于它把这条链路的每一环都摊开成了可读的实现，而不是把结论糊在 PPT 上。
2. 词法分析：正则表达式为什么最终要落成一张 DFA 表
几乎所有人第一次写词法分析器，都是从一个巨型if-else链开始的：先判断是不是数字，再判断是不是字母，然后判断是不是双字符运算符。这段代码跑起来没问题，但它和课本上的正则表达式、NFA、DFA 之间隔着一层看不见的等价关系——手写的if-else链其实就是一个 DFA，只不过状态被藏进了程序计数器里。
理解这层等价关系，是后面所有调试工作的前提。因为一旦你的扫描器在某个字符上报错，你需要的不是加一个if，而是问：当前状态是什么，这个字符属于哪个等价类，转移表里为什么没有出边。这个问题只有把扫描器当成表来看，才回答得清楚。
2.1 子集构造到底在合并什么
正则表达式到 DFA 的标准路径是三段：Thompson 构造把正则变成带 ε 边的 NFA，子集构造把 NFA 的状态集合压成 DFA 的单个状态，最小化再去掉等价状态。课设里最容易被跳过、又最影响后续性能的是子集构造这一步。
它的核心动作是「把一组 NFA 状态当成一个 DFA 状态」。因为 NFA 在同一时刻可以处在多个状态上，而 DFA 只能有一个当前状态，所以要让 DFA 模拟 NFA，就必须把「可能同时处在的状态集合」整体打包。走一步ε-闭包，读一个字符，再求一次闭包，得到的新集合如果没见过，就分配一个新状态编号。
状态爆炸的来源也在这里。一个含 k 个状态的 NFA，理论上最多能炸出 2^k 个 DFA 状态，实际工程里靠两件事压住：一是把字符按等价类合并（所有数字是同一类，所有字母是同一类，所有没被任何正则用到的字符统统归到「其它」类），二是很多子集压根不可达。课设里的词法规则通常只有关键字、标识符、整数、浮点、运算符、界符这几类，压缩之后转移表往往只有几十行。
提示：字符等价类不是可选的优化，而是子集构造能落地的关键。不做等价类，转移表的列数等于字符集大小，可读性和体积都会失控。
手写扫描器和表驱动扫描器的差别，本质是「状态转移到代码里」还是「状态转移到数据里」。前者调试靠打断点，后者调试靠打印一行表。
2.2 最长匹配与回退：一个字符的 lookahead 值多少钱
词法分析里最容易翻车的一条规则叫最长匹配，也叫 maximal munch：扫描器必须吃掉尽可能多的字符，再决定这是什么 token。if既是关键字也是合法标识符，123abc里的123是整数但整个串非法，>>=不能被拆成>和>=。这些判断都依赖同一件事——记住最后一次「处在一个接受状态」的位置。
于是扫描器的主循环变成：一直往前读，每进入一个接受状态就记下当前位置，一旦走进死状态就回退到最近一次接受点。这个回退动作在源码里通常只有一行赋值，但它是所有「双字符运算符被误切成两个单字符」问题的根源。
# 表驱动扫描器：正则被"编译"成转移表，运行期只做查表 # class_of 把字符映射成等价类，等价类来自子集构造时的字符合并 def class_of(c): if c.isdigit(): return 0 # 数字类 if c.isalpha() or c == "_": return 1 # 标识符字符类 return 2 # 其它：单字符运算符与界符 # TRANS[state][class] = next_state，负数表示该状态没有出边 TRANS = [ [1, 3, 2], # 0 起始状态 [-1, -1, -1], # 1 接受"整数"，不再有出边 [-1, -1, -1], # 2 接受"单字符运算符/界符" [3, 3, -1], # 3 标识符中间态：数字和字母都能继续吃 ] ACCEPT = {1: "INT", 2: "OP", 3: "ID"} def scan(src, i): state, start = 0, i accept_state, accept_end = None, start while i < len(src): to = TRANS[state][class_of(src[i])] if to < 0: break state = to i += 1 if state in ACCEPT: # 记录最长匹配的落点，供后面回退使用 accept_state, accept_end = state, i if accept_state is None: raise SyntaxError(f"非法字符 {src[start]!r}，位置 {start}") # 注意这里返回 accept_end 而不是 i：i 可能已经越过接受点 return ACCEPT[accept_state], src[start:accept_end], accept_endTRANS的每一行对应一个 DFA 状态，每一列对应一个字符等价类，这是子集构造的直接产物；ACCEPT把接受状态映射回 token 类型，是「哪个状态算数」的声明。scan的返回值里第三个是新的读取位置，调用方必须用它推进游标，而不是自己+1，否则回退逻辑会被外部破坏。
关键字识别的经典做法不在表里做：扫描器先按标识符规则吃掉整个串，再查一张关键字哈希表，命中就改类型。这样TRANS不用为每个关键字开一条独立路径，新增关键字只改表不改状态机。
位置信息（行号、列号）必须在扫描阶段就算好，别指望语法分析器回头去数换行。语法树节点的行列号是报错时唯一的坐标，缺了它，所有错误信息都只能写成「某处有语法错误」，这种输出在验收现场基本等于没写。
2.3 手写扫描器与生成器怎么选
课设里两条路都有人走。手写扫描器代码短、调试直观、错误恢复好做（可以直接跳过非法字符继续扫），缺点是文法一变就得改代码。用生成器（如 lex 系工具）则把规则集中在一处，改文法只改规则文件，缺点是生成出来的表和源程序脱节，出了错只能对着表猜。
常见的实现思路是折中：扫描器主体手写，但把转移表抽成数据，让TRANS和ACCEPT独立于主循环存在。这样既保留了手写的可读性，又保留了「改规则只改表」的便利，调试时把表打出来就能看出状态机长什么样。
3. 语法分析：递归下降和 LR 表驱动到底差在哪
词法分析交付的是一串带位置的 token，语法分析要做的是把这串线性输入还原成树。所有语法分析算法的本质都是同一个问题：在只看到有限个 token 的前提下，怎么确定该用哪条产生式。这个「有限」就是 lookahead，它决定了你的分析器能处理多复杂的文法，也决定了你会在什么时候撞上冲突。
课设里最常见的两种选择是递归下降（配 LL(1)）和表驱动 LR（SLR/LALR）。它们的分歧点不在算法难度，而在「冲突暴露给谁」——递归下降把冲突暴露给写文法的人，LR 把冲突暴露给构造分析表的人。
3.1 LL(1) 的确定性边界
递归下降之所以能一句话对上一条产生式，靠的是 FIRST 集和 FOLLOW 集。当非终结符 A 有两条候选A -> α和A -> β时，只要 FIRST(α) 和 FIRST(β) 不相交，看一个 token 就能决定走哪条；如果某条候选能推出空串，还得保证 FIRST(α) 和 FOLLOW(A) 也不相交。
这条边界非常硬。if E then S else S这种文法能过，因为then和else是显式终结符；但经典的悬空 else 文法在 LL(1) 下直接冲突，因为else既可能启动内层 if 的 else 分支，也可能是外层 if 的 else 部分。这不是实现 bug，是 lookahead 长度不够导致的本质信息缺失。
课程设计里撞上 FIRST/FOLLOW 冲突，一般三条路：改写文法（提左公因子、消除左递归）、增加 lookahead（LL(2) 或回溯）、改用 LR。被讲得最多的是消除左递归，因为它顺带把「表达式左结合」这件事从算法层面变成了文法层面。
3.2 LR(1) 项目集族与 LALR 合并的代价
LR 分析器的能力来自「已经看过的东西」——它用状态栈记录到目前为止匹配过的句型，用分析表决定移进还是归约。LR(1) 项目形如[A -> α·β, a]，点表示当前解析位置，a是向前看符号，它比 SLR 强的地方在于归约只看该状态真正允许的 follow 符号，而不是全局 FOLLOW 集。
代价是状态数。带向前看符号的项目集族规模通常比 LR(0) 大好几倍，LALR(1) 的应对办法是把「同心项目集」合并——所有核心项目相同、只有向前看符号不同的状态合并成一个。合并之后状态数降到和 LR(0) 一致，但会引入一类新冲突：归约-归约冲突。原本在两个状态里各自合法的归约，合并后挤在同一个状态里，向前看符号重叠了。
这就是「LALR 比 LR(1) 弱一点」的具体含义。对课设规模的文法（表达式、语句、声明）来说，LALR 几乎总能压住，所以大多数教学实现走到 LALR 就够了。真正的难点不在构造算法，而在冲突报告怎么读。
3.3 冲突消解：优先级写进文法还是写进分析表
表达式文法是冲突高发区。E -> E + E | E * E | id这条文法用任何分析法都会冲突，因为a + b * c有两个合法的语法树。消解方式有两种，选哪种直接决定了后面怎么加新运算符。
第一种是在文法层面分层。把表达式拆成E -> T (+|-) T、T -> F (*|/) F、F -> id | (E)这样的层级，优先级由层级的深浅表达，结合性由左递归或循环表达。第二种是把优先级和结合性作为元信息挂在运算符表上，让分析器在冲突时查表决定。
递归下降天然适合第一种，因为每层优先级就是一个函数：
# 每一层函数对应一级优先级：优先级低的函数在调用链上层 # 文法已消除左递归：E -> T {('+'|'-') T} def parse_expr(self): node = self.parse_term() while self.peek().kind == "OP" and self.peek().text in ("+", "-"): op = self.advance().text right = self.parse_term() # 左结合：新节点包住已建好的左子树，再挂右子树 node = Node("BinOp", op=op, left=node, right=right) return node def parse_term(self): node = self.parse_factor() while self.peek().kind == "OP" and self.peek().text in ("*", "/"): op = self.advance().text node = Node("BinOp", op=op, left=node, right=self.parse_factor()) return nodeparse_expr调用parse_term，parse_term再调用parse_factor，调用链的深度就是优先级的高低，不需要额外的优先级表。while循环实现左结合：a - b - c第一次循环建出(a-b)，第二次循环把它当成新的左子树，得到((a-b)-c)。如果要右结合（比如赋值运算符），把循环改成递归，让右子树先建完再回来挂左子树。
表驱动 LR 则倾向第二种做法：文法保持自然形态，冲突用%left、%right、%nonassoc这类声明消解。好处是文法可读性高，加运算符只加一行声明；坏处是分析器的行为被藏进了生成器，出错时只能看冲突报告。
注意：优先级表里同级运算符必须声明为左结合或右结合，不能只给优先级。
a - b - c的两种结合方式在语法上都能建树，只有结合性声明能选出其中一个。
4. 语义分析到中间代码：符号表为什么必须和作用域一起设计
语法树只是结构，它是没有「意思」的。a + b里的a到底是一个整数变量、一个数组、还是一个未声明的名字，语法树自己不知道。语义分析要做的事就是给每个名字找到绑定，检查类型是否自洽，然后把树翻译成一种不再依赖语法细节的形式——四元式。
这三件事必须一起设计。符号表的生命周期决定了作用域规则，作用域规则决定了类型检查在哪个时刻能看到哪些名字，而四元式的生成顺序又必须和作用域的进出严格对齐，否则临时变量的作用域会串味。
4.1 作用域链：为什么不是一张大哈希表加撤销栈
最省事的符号表实现是一张全局哈希表，进入语句块时插入，离开时删除。这个方案在简单语言里能跑，但一遇到「同一名字在内层遮蔽外层」就出问题：你删掉的是内层的那个，还是外层的那个？如果内层没定义过这个名字，你在清理时会把外层的错误删掉。
作用域链把这个问题从「删不删」变成「在哪一层找」：
class Scope: def __init__(self, parent=None): self.table = {} self.parent = parent def define(self, name, sym): # 同一作用域内重复定义才是错误，跨作用域遮蔽是合法的 if name in self.table: raise SemanticError(f"符号 {name} 重复定义于本作用域") self.table[name] = sym def lookup(self, name): s = self while s is not None: if name in s.table: return s.table[name] s = s.parent return None # 一路走到最外层都没找到，才算未声明parent指针构成链，define只写当前层，lookup由内向外逐层找。退出作用域时不需要任何删除动作，把当前指针指回parent就行——内层那个Scope对象被丢弃，外层的表从未被碰过，这正是「遮蔽」应有的语义。
这套结构还有一个隐性好处：离开作用域时天然支持一次性回收。函数有几十个局部变量时，不需要逐个撤销，整个Scope对象直接释放。
作用域进出的时机必须和语法制导翻译的时机严格对应。进入一个{就push一层，离开}就pop；函数参数属于函数体那一层，不属于外层；for循环里声明的循环变量属于循环体那一层，循环结束就该消失。这些规则在语法树上看起来都很清楚，但在自底向上的分析器里，实际触发点是归约动作，稍不留神就会晚一步或者早一步。
4.2 类型检查的求值顺序：属性依赖不能靠猜
语法制导翻译把每个节点看成带属性的对象，综合属性从子节点往上传，继承属性从父节点往下传。类型检查是典型的综合属性：一个BinOp节点的类型由左右子树的类型和运算符决定，子树不先算完，父节点无从下手。
问题出在继承属性上。像int a[10]这种声明，数组维度的合法范围、变量实际类型，既要看父节点给的上下文（这是不是一个类型声明），又要看子节点（维度和初值）。这类属性没法靠一次遍历算完，要么多遍扫描，要么在构造节点时把上下文显式传下去。
课设里比较稳的做法是给每个节点一个check(ctx)方法，ctx装着当前作用域和当前函数返回类型，父节点调用子节点的check时把ctx传下去，子节点的返回值是它自己的类型。这样综合属性和继承属性共用一条调用链，顺序由调用关系自然保证，不需要额外做拓扑排序。
类型规则本身不需要写得多完备，但必须写清楚。隐式类型转换（整型提升、数值类型混算）是最容易出隐蔽 bug 的地方：int + float到底转成什么，赋值时窄类型往宽类型转是否合法，这些规则的每一条都应该有一个对应的测试用例，否则等到代码生成阶段再发现，错误会以「指令选择失败」的面目出现，完全看不出根因。
4.3 四元式：为什么中间表示要「最小」
四元式的形式是(op, arg1, arg2, result)，每条只做一件事：一次运算、一次赋值、一次跳转。a = b + c * 2会被拆成三条：
# 四元式生成：每条指令只有一个运算符，临时变量按序编号 # a = b + c * 2 # ('*', 'c', '2', 't1') # ('+', 'b', 't1', 't2') # ('=', 't2', '', 'a') def emit(self, op, arg1, arg2, result): self.quads.append((op, arg1, arg2, result)) def new_temp(self): self.temp_id += 1 return f"t{self.temp_id}"拆成三条看起来啰嗦，价值在于每一条都是「无歧义、无嵌套」的。语法树是有层次的，四元式是线性的；树上的每个父子关系都被临时变量显式化了。后面做控制流分析、活跃变量分析、常量折叠，处理的都是这条线性序列，不需要在树上递归。
临时变量的编号策略也值得想一下。全局递增最简单，但会生成大量永不复用的名字；按作用域重置编号能压缩数量，代价是要保证不同作用域的临时变量不会在同一段代码里互相覆盖。课设规模下全局递增完全够用，只要在生成目标代码时把临时变量正确映射到寄存器或栈槽。
从四元式到目标代码，最朴素的映射是「一个四元式一段汇编」：('+', 'a', 'b', 't1')翻成LOAD r1, a; ADD r1, b; STORE t1, r1。这个版本能跑但寄存器压力大，改进方向是表达式树求值——按 Sethi-Ullman 编号决定先算哪棵子树，用最少的寄存器完成整棵树的求值。这一步是从「能跑」到「像编译器」的分水岭。
5. 排查清单：课设里最容易翻车的五个地方
调试编译器有个特点：错误现象出现的位置，往往离真正的原因隔了好几层。一个「代码生成结果不对」的问题，根因可能是词法阶段少记了一个位置，导致语法树的节点全错位。下面五条是按实际踩坑频率排的，每条都按现象、原因、解决写清楚。
5.1 前端：词法与语法阶段的三个坑
坑一：双字符运算符被切成两个单字符。现象是a >= b被解析成a > = b，语法分析器报「意外的=」。原因是扫描器在读到>之后没有继续往前看，直接按单字符接受返回了。解决的关键是落实最长匹配：主循环必须持续读到死状态，并且用accept_end而不是当前游标做切片，只要最后一处接受点是>=那个状态，返回的就是完整的两字符 token。这类 bug 的隐蔽之处在于单运算符测试全部通过，只有复合运算符的用例才会暴露。
坑二：关键字被当成标识符。现象是if (a) ...里if被识别成变量名，语义分析报「未声明的标识符 if」。原因是扫描器把关键字和标识符混在同一条正则里，或者关键字表在标识符识别之后才查。解决方式是在标识符接受之后立刻查关键字表并改写 token 类型，同时保证关键字表是大小写敏感的完全匹配，不做前缀匹配——否则iff会被误判成if。
坑三：错误信息定位到错误的行。现象是报错说第 42 行有问题，实际错误在第 40 行。原因是行号统计放在语法分析阶段，按语法树节点的位置反推，而空行和注释里的换行没被计入。解决办法是把换行计数放在扫描器里，读到一个\n就自增，每个 token 出发前把当前的(line, col)存进 token，语法树节点直接继承子节点的位置。这条改动成本很低，收益是之后所有报错都可信。
5.2 后端：语义与代码生成阶段的两个坑
坑四：内层作用域的变量退出后仍然可见。现象是{ int x; } x = 1;这种代码通过了语义检查。原因是作用域退出时只把符号表指针指回父层，但某个缓存或者闭包里还留着指向内层Scope的引用，查找时绕过了链式回溯。解决是把查找路径统一收敛到lookup一个入口，禁止任何代码直接访问scope.table；退出作用域时只改指针，不保留任何对内层表的引用。
坑五：四元式顺序和执行顺序不一致。现象是短路求值a && b在a为假时仍然计算了b，导致除零或者空指针。原因是语法制导翻译在遍历子树时先递归生成了右子树的四元式，再插入跳转指令，顺序彻底颠倒。解决是把控制流的生成拆成两段：先申请标号、生成左子树、发射条件跳转，再生成右子树、回填标号。回填（backpatch）机制就是为这个场景准备的——跳转指令先写一个占位标号，等目标位置确定后再统一改写。
注意：回填列表一定要在函数或语句结束时检查是否全部回填完毕。漏回填的跳转指令在最终输出里会指向一个不存在的标号，这种错误在汇编阶段才报，排查成本极高。
6. 取舍：把编译器写成「能改的」比写成「能跑的」难
课设结束时回头看，真正拉开差距的不是谁实现了更多文法特性，而是谁的代码在最后一刻还能改。递归下降和 LR 表驱动在这件事上的表现完全不同：
| 维度 | 手写递归下降 | 表驱动 LR |
|---|---|---|
| 实现成本 | 低，每个非终结符一个函数 | 高，需要项目集族构造与表压缩 |
| 文法改动成本 | 改文法就要改函数 | 改文法只需重新生成表 |
| 错误恢复 | 容易，可直接跳过 token 继续 | 较难，需要在状态栈上做弹出 |
| 可读性 | 高，调用链就是文法结构 | 低，行为藏在表里 |
| 冲突暴露时机 | 写代码时 | 构造表时 |
我的取舍是：前端用递归下降，把优先级和结合性写成函数层级，让文法结构在代码里一眼可见；语义分析和中间代码生成做成独立的两遍，中间用四元式解耦。这样即使语法分析器重写，后端一行都不用动。
验证方法上，最有效的一条是给每个阶段做「单阶段可测」。扫描器能单独喂字符串输出 token 流，语法分析器能单独喂 token 流输出语法树（用 S-表达式打印），语义分析能单独喂树输出符号表和四元式。任何一层出问题，都能在它的边界上定位，而不是从头跑一遍再靠猜。这套习惯让我在后来的项目里少走了很多弯路。
那次课设我最后悔的一件事，是为了赶进度跳过了错误恢复，把所有非法输入都直接raise掉。验收时老师输入了一个少写分号的程序，编译器吐了一个空白的异常栈，我在旁边站了半分钟不知道说什么。从那以后我每次写解析器，都强制先实现一条「至少能报告行列号和期望 token 集合」的错误路径，再回去补功能。这份课设资料里把错误处理和各阶段边界都写得很细，值得拿去对着源码走一遍。希望帮到你。
本文还有配套的精品资源，点击获取
