简介面向计算机专业学生与编译原理课程设计学习者这份来自南京航空航天大学的课设资料围绕词法分析与语法分析模块展开提供从需求理解、源码实现到报告撰写的完整参考适合正在完成课程设计或希望梳理编译前端实现思路的读者。压缩包共32个文件约961KB包含c、cpp、h源码exe可执行程序obj、pdb等编译中间文件以及doc报告、ppt答辩文稿和txt说明文件兼顾代码阅读、运行验证与文档参考。已有752人学习下载说明其在校内课设场景中具有一定参考价值。资料中词法部分与语法部分分目录组织配有可执行程序、头文件与符号表相关实现描述称经检验程序无BUG可帮助读者对照理解扫描器、token处理、语法分析流程及调试方法报告与答辩PPT也便于整理设计思路和总结实验过程。1. 编译原理课程设计到底在做什么从几十行源码到能跑的目标程序期末前四周某高校的编译原理课程设计任务书发下来要求实现一个类 C 语言子集的编译器输入一段几十行的源码中间过程完成词法、语法、语义三道分析最后输出四元式或者目标机汇编能在测试用例上跑出正确结果。多数人拿到题目第一反应是翻教材找算法真正卡住进度的往往不是算法而是接口层面的约定词法记号怎么定义边界、AST 节点怎么统一形状、符号表什么时候进栈出栈、四元式的跳转地址怎么回填。编译原理课程设计训练的核心能力是把一个模糊需求拆成一条可验证的数据流让字符串一路变成可执行结构并且每一步都能单独拉出来看。这套拆法不只服务于课程设计脚本引擎、配置解析器、表达式求值组件、领域 DSL 解释器用的都是同一条链路。下面按一个能跑通的最小编译器展开新手照步骤能复现熟手可以直接看参数边界和错误恢复那几节。2. 词法分析器先落地状态机、最长匹配与行号定位词法分析是整条链路的入口也是最容易被轻视的一环。很多人觉得正则表达式一把梭就能搞定结果在被切成和、注释跨行、字符串里的转义符这几处反复翻车。我的习惯是先把记号表和字符类定死再写扫描循环最后才补错误处理。顺序反过来后面每改一次规则就要重跑一遍全部用例。2.1 先把记号表和字符类定死记号表不是一个形式化的东西它同时被后面三个模块引用语法分析用它判断往前看几个记号语义分析用它区分字面量和标识符错误报告用它把内部枚举翻译成人话。所以这张表要在动手写代码之前落到文档里改一次同步改三处。记号类别词法规则示例备注KW命中关键字表ifwhileint先按标识符扫再查表ID字母或下划线开头后接字母数字下划线count_tmp大小写敏感NUM十进制整数42负数交给语法层处理OP双字符优先于单字符顺序不能反SE界符( ) { } ; ,一一对应EOF输入结束—必须有方便语法层收尾关键字不单独占一个类别而是命中关键字表后改记号为KW这是为了让语法分析少写一堆if text if。也有人把每个关键字都做成独立枚举好处是语法层写起来更像自然语言坏处是加一个关键字要改四处代码课程设计阶段不划算。2.2 手写扫描循环状态机其实就是一层 while最小可跑的词法分析器只有一个主循环循环里按「当前字符属于哪一类」分派每一类走完之后把下标往前推。这不是教科书里的 DFA 表驱动法但本质相同状态隐含在代码位置里转移就是continue。KEYWORDS {if, else, while, int, return, void, print} TWO_CHAR_OPS {, , , !, , ||} class Token: __slots__ (kind, text, line, col) def __init__(self, kind, text, line, col): self.kind, self.text, self.line, self.col kind, text, line, col def __repr__(self): return fToken({self.kind},{self.text!r},{self.line}:{self.col}) def tokenize(src): tokens [] i, line, col, n 0, 1, 1, len(src) while i n: c src[i] # 空白只在同一行内推进列号 if c in \t\r: i 1; col 1; continue if c \n: i 1; line 1; col 1; continue # 单行注释吞到行尾不产生记号 if src.startswith(//, i): while i n and src[i] ! \n: i 1; col 1 continue # 标识符或关键字这里做的是「最长匹配」 if c.isalpha() or c _: j i while j n and (src[j].isalnum() or src[j] _): j 1 word src[i:j] kind KW if word in KEYWORDS else ID tokens.append(Token(kind, word, line, col)) col j - i; i j; continue # 整数课设阶段不支持浮点遇到小数点直接报错 if c.isdigit(): j i while j n and src[j].isdigit(): j 1 tokens.append(Token(NUM, src[i:j], line, col)) col j - i; i j; continue # 双字符运算符必须先判否则 会被拆成 和 if i 1 n and src[i:i 2] in TWO_CHAR_OPS: tokens.append(Token(OP, src[i:i 2], line, col)) i 2; col 2; continue if c in -*/!: tokens.append(Token(OP, c, line, col)) i 1; col 1; continue if c in (){};,[]: tokens.append(Token(SE, c, line, col)) i 1; col 1; continue raise SyntaxError(f非法字符 {c!r} 在 {line} 行 {col} 列) tokens.append(Token(EOF, , line, col)) return tokens这段代码里有三个参数值得单独说。i是全局读指针所有分支必须保证它严格前进否则会死循环line和col是可观测状态只在实际消耗字符时推进不要在一开始就算好n提前缓存避免循环里反复取长度。双字符运算符的判断放在单字符之前是这段代码里唯一有顺序依赖的地方写反了就会出现「看起来能跑、遇到就错」的玄学 bug。2.3 最长匹配词法规则里唯一不能妥协的原则最长匹配的意思是在当前位置能匹配多个记号的时候永远选最长的那个。和都能从前两个字符开始匹配选长的while和wh都可能是一个标识符的开头但wh后面接ile所以整个while是一个记号。这条原则写进代码只需要一处标识符和数字的循环写成while 下一个字符仍属于当前类别运算符表先查两字符。真正容易出问题的是边界情况。比如ab中间没有空格读指针在位置时如果先走单字符分支后面就永远补不回来了。再比如1..2这种输入数字扫描会在第二个点停下然后词法层报非法字符报错位置指向第二个点这个定位是对的但信息不够友好可以在报错信息里把前一个记号也带上。课程设计里的用例往往包含大量紧凑写法对手写扫描器来说最稳妥的验证方式是构造一组对照用例每条只测一个边界、ab、x-1、/* 未闭合注释。跑一遍看输出哪条不对就改哪条分支比盯着代码猜快得多。2.4 行号列号不跑偏错误信息才有意义错误定位是课程设计评分里很看重的部分但它的实现成本极低只需要保证line和col在一次消耗之后同步更新并且所有报错都走同一个格式化函数。class CompileError(Exception): def __init__(self, msg, line, col, src_line): super().__init__(f{line}:{col}: {msg}\n {src_line}\n { * (col - 1)}^)把源码行一起带出去报错时能直接指出列位置。这个细节在调试语法分析时特别值钱递归下降解析器抛出的错误往往只告诉你「期望)实际是;」加上列号之后能立刻定位到是哪个括号没闭合。还有一个隐藏坑如果源文件里有制表符按字符数算出来的col和编辑器里看到的列不一致。常见做法是把\t展开成固定宽度比如 4 个空格再计算列号只在显示层做不影响扫描逻辑。3. 语法分析选型与落地改写成 LL(1) 后用递归下降手写到语法分析这一步选型比实现更影响进度。课程设计常见的三种做法是手写递归下降、用 yacc/bison 生成、用现成的解析库。三种都能交差但调试体验差别很大尤其是在要给出友好错误信息的时候。我一般推荐递归下降理由不是它更「正统」而是它的调用栈就是语法树出错时打印栈就能知道当前在哪个产生式里。3.1 先改文法消除左递归和提取左公因子教材上的表达式文法通常写成左递归形式因为它最直观E - E T | T T - T * F | F F - ( E ) | id | num左递归没法直接写递归下降会无限递归下去。改写成右递归只需要两步把E - E T | T拆成E - T E和E - T E | εE - T E E - T E | - T E | ε T - F T T - * F T | / F T | ε F - ( E ) | id | num改写之后每个非终结符的第一个候选都不再以自己开头可以按 first 集直接分派。这一步看着像形式化练习实际收益是你不需要维护任何解析表代码结构直接对应文法结构改文法就是改函数。提取左公因子解决的是另一类问题。比如语句id expr;和id(args);都以id开头向前看一个记号分不出来就要么把公共前缀提出来要么多看几个记号。课程设计里更省事的办法是把函数调用从语句里去掉只保留赋值和打印这样语句层的分派只看第一个记号就能定。3.2 AST 节点设计与递归下降骨架AST 节点的形状决定了后面语义分析和代码生成好不好写。常见做法是用一个基类加若干子类每个子类只存自己需要的字段不要为了统一而塞一堆None。from dataclasses import dataclass dataclass class Num: value: int dataclass class Var: name: str dataclass class BinOp: op: str; left: object; right: object dataclass class Assign: name: str; expr: object dataclass class Decl: name: str dataclass class Print: expr: object dataclass class While: cond: object; body: list dataclass class If: cond: object; then: list; orelse: list解析器持有一个记号列表和一个位置指针所有parse_*函数都遵循同一个模式先看当前记号决定走哪个分支消耗掉再递归解析子结构。class Parser: def __init__(self, toks): self.toks, self.pos toks, 0 def peek(self): return self.toks[self.pos] def check(self, kind, textNone): t self.peek() return t.kind kind and (text is None or t.text text) def accept(self, kind, textNone): if self.check(kind, text): self.pos 1 return True return False def expect(self, kind, textNone): if not self.accept(kind, text): t self.peek() raise SyntaxError(f期望 {text or kind}实际 {t.text!r} {t.line}:{t.col}) return self.toks[self.pos - 1] # stmt_list - stmt stmt_list | ε def parse_stmts(self, stop): out [] while self.peek().kind ! EOF and self.peek().text not in stop: out.append(self.parse_stmt()) return out def parse_stmt(self): if self.accept(KW, int): name self.expect(ID).text self.expect(SE, ;) return Decl(name) if self.accept(KW, print): e self.parse_expr() self.expect(SE, ;) return Print(e) if self.accept(KW, while): self.expect(SE, () cond self.parse_expr() self.expect(SE, )) return While(cond, self.parse_stmts({}) if self.accept(SE, {) else [self.parse_stmt()]) if self.check(ID): name self.expect(ID).text self.expect(OP, ) e self.parse_expr() self.expect(SE, ;) return Assign(name, e) t self.peek() raise SyntaxError(f无法识别的语句开头 {t.text!r} {t.line}:{t.col}) def parse_expr(self): return self.parse_or() def parse_or(self): node self.parse_and() while self.accept(OP, ||): node BinOp(||, node, self.parse_and()) return node def parse_and(self): node self.parse_cmp() while self.accept(OP, ): node BinOp(, node, self.parse_cmp()) return node def parse_cmp(self): node self.parse_add() while self.peek().kind OP and self.peek().text in (, , , , , !): op self.toks[self.pos].text; self.pos 1 node BinOp(op, node, self.parse_add()) return node def parse_add(self): node self.parse_mul() while self.peek().kind OP and self.peek().text in (, -): op self.toks[self.pos].text; self.pos 1 node BinOp(op, node, self.parse_mul()) return node def parse_mul(self): node self.parse_primary() while self.peek().kind OP and self.peek().text in (*, /): op self.toks[self.pos].text; self.pos 1 node BinOp(op, node, self.parse_primary()) return node def parse_primary(self): if self.accept(NUM): return Num(int(self.toks[self.pos - 1].text)) if self.accept(ID): return Var(self.toks[self.pos - 1].text) if self.accept(SE, (): node self.parse_expr() self.expect(SE, )) return node t self.peek() raise SyntaxError(f期望表达式实际 {t.text!r} {t.line}:{t.col})这段代码里parse_add里的while循环是关键它让左结合自然成立a - b - c会被解析成(a - b) - c而不是a - (b - c)。expect抛出异常而不是返回None是为了让错误在最早的地方暴露而不是留到后面变成一个看不出来源的NoneType错误。3.3 错误恢复同步记号集比直接抛异常好用课程设计里通常会给一组「应报错」的用例要求编译器不能崩、要报错、最好还能继续往下分析。最简单有效的办法是 panic mode 加同步记号集在语句级别用try/except包住出错后丢弃记号直到遇到;或}然后从这个位置继续。def parse_program(self): stmts [] while self.peek().kind ! EOF: try: stmts.append(self.parse_stmt()) except SyntaxError as e: print(f[语法错误] {e}) # 同步丢弃到分号或右花括号保证不卡在同一位置 while self.peek().kind ! EOF and self.peek().text not in (;, }): self.pos 1 if self.peek().text in (;, }): self.pos 1 return stmts同步记号集的选择有讲究分号是最常见的语句结束符右花括号是块结束符两个都收进来能覆盖大部分恢复场景。要避免的是把)也塞进同步集那样括号不匹配时会跳到错误的位置产生一连串假的后续错误看起来像编译器本身有问题。3.4 要不要上 yacc/bison一张表看清适用边界维度手写递归下降yacc/bison 生成文法限制需改写成 LL(1)不能有左递归支持 LALR(1)表达式可以保持原样错误信息可以自定义带行号列号和期望集合默认信息较粗要自己挂钩子调试难度调用栈就是语法结构需看生成的y.output状态机改文法成本改函数即可改.y后重新生成冲突要手动消解适合场景文法小、要精确报错、要交源码文法大、以功能正确为主课程设计的文法通常只有十几条产生式手写完全可控。如果导师明确要求用生成器那就把词法部分交给 flex语法部分交给 bison注意在.y里把%union和%token的定义跟词法层的枚举对齐否则会出现类型不匹配的编译错误这类错误信息很难读。4. 语义分析与中间代码生成符号表、类型检查与四元式回填语法分析只保证结构合法语义分析才决定程序有没有意义。这一层做三件事建符号表、查类型、生成中间代码。三件事必须在一个遍历里完成拆成三次遍历会让「先声明后使用」这类规则的实现变得别扭。4.1 符号表作用域栈加哈希桶符号表最直观的实现是一个列表每进一个块append一个字典出块pop。查找时从栈顶往下扫先找到的优先这样内层遮蔽外层的行为自然成立。class SymbolTable: def __init__(self): self.stack [{}] # 栈底是全局作用域 def enter(self): self.stack.append({}) def leave(self): if len(self.stack) 1: raise RuntimeError(全局作用域不能弹出) self.stack.pop() def declare(self, name, ty): cur self.stack[-1] if name in cur: raise SyntaxError(f重复声明 {name}) cur[name] ty def lookup(self, name): for scope in reversed(self.stack): if name in scope: return scope[name] return Nonedeclare只查当前层lookup从内向外查这两个行为不能混。很多翻车案例是把重复声明检查写成了全栈查找结果内层块里声明一个和全局同名的变量就报错而语言规范通常允许遮蔽。类型信息在课程设计阶段只需要区分int和void复杂一点可以加数组和指针。用字符串存类型就够了不必为了「正规」去写一个类型类层次那会让类型相等判断变成一次递归。4.2 类型检查表达式类型推导和赋值兼容类型检查的本质是给每个表达式算一个类型遇到不兼容的组合就报错。二元运算的规则可以写成一张小表查表比一堆if清晰。ARITH {, -, *, /} CMP {, , , , , !} LOGIC {, ||} def type_of(node, table): if isinstance(node, Num): return int if isinstance(node, Var): t table.lookup(node.name) if t is None: raise SyntaxError(f使用未声明的变量 {node.name}) return t if isinstance(node, BinOp): lt, rt type_of(node.left, table), type_of(node.right, table) if node.op in ARITH and lt rt int: return int if node.op in CMP and lt rt: return int # 比较结果当 0/1 用 if node.op in LOGIC and lt rt int: return int raise SyntaxError(f运算符 {node.op} 不支持 {lt} 和 {rt}) raise TypeError(f未知节点 {type(node).__name__})比较运算返回int而不是bool是为了让后面的四元式统一用整数表示真假省掉一套布尔类型。这是课程设计里的常见简化代价是if (a b)和if (1)在语义上没有区别如果题目要求严格区分就得单独加一个布尔类型并在赋值时做兼容检查。4.3 四元式与回填if 和 while 的跳转地址怎么补四元式的形式是(op, arg1, arg2, result)够表达算术、赋值、跳转和打印。控制流的难点在于生成跳转指令的时候目标地址还没算出来只能先留空等后面补上这个动作叫回填。class Quad: __slots__ (op, a1, a2, res) def __init__(self, op, a1None, a2None, resNone): self.op, self.a1, self.a2, self.res op, a1, a2, res def __repr__(self): return f({self.op}, {self.a1}, {self.a2}, {self.res}) class Emitter: def __init__(self): self.quads, self.tmp [], 0 def new_temp(self): self.tmp 1 return ft{self.tmp} def emit(self, op, a1None, a2None, resNone): self.quads.append(Quad(op, a1, a2, res)) return len(self.quads) - 1 # 返回下标供回填使用 def patch(self, idx, target): self.quads[idx].res target有了patchwhile的生成逻辑就很直接先记下循环体的起始下标生成条件表达式发一条jf占位生成循环体发一条无条件跳回起点最后把jf的目标补成当前末尾。def gen_stmt(node, em, table): if isinstance(node, While): begin len(em.quads) cond gen_expr(node.cond, em, table) jf em.emit(jf, cond, None, None) # 占位先不填 for s in node.body: gen_stmt(s, em, table) em.emit(jmp, None, None, begin) em.patch(jf, len(em.quads)) # 跳出循环的位置gen_expr负责把表达式规约成一个临时变量名二元运算先算左右两边再发一条以临时变量为结果的四元式。临时变量用递增计数器生成不要用源码里的变量名拼接否则同名变量在不同作用域里会撞车。4.4 一百行的栈式虚拟机让四元式真的跑起来中间代码不可执行验证起来很麻烦。写一个极简的栈式执行器几十行就够能把「四元式正确」这件事变成可观测的事实。def run(quads, outprint): mem, pc {}, 0 def val(x): if x is None: return 0 return x if isinstance(x, int) else mem.get(x, 0) while pc len(quads): q quads[pc] if q.op assign: mem[q.res] val(q.a1) elif q.op in (, -, *, /): a, b val(q.a1), val(q.a2) mem[q.res] {: a b, -: a - b, *: a * b, /: a // b}[q.op] elif q.op in (, , , , , !): a, b val(q.a1), val(q.a2) mem[q.res] int({: a b, : a b, : a b, : a b, : a b, !: a ! b}[q.op]) elif q.op jmp: pc q.res; continue elif q.op jf: if val(q.a1) 0: pc q.res; continue elif q.op print: out(val(q.a1)) pc 1这个执行器只支持整数除法和无符号场景边界条件都没处理但足够跑通课程设计的用例。jf的判断写成 0 则跳转跟「假跳转」的语义一致如果后面要加jt注意别把条件写反这是最容易出现的 off-by-one 式错误。5. 避坑排查课程设计里最容易翻车的五处细节下面五条都是我在指导别人做课设时反复见到的每条按现象、原因、解决写能对上号就直接改对不上号也能当检查清单扫一遍。5.1 现象ab被切成三个记号语法分析报「无法识别的语句」原因几乎总是词法层的分支顺序写反了先判单字符运算符再判双字符一旦被消耗后面的就变成独立记号。还有一种变体是双字符表里漏了!只写了遇到!时第一个!被当成非法字符直接抛异常。解决分两步把双字符判断提到单字符之前并且在单字符分支里排除掉所有能作为双字符前缀的符号。更稳妥的做法是写一个最小用例集每次改词法都跑一遍。cases { ab: [ID, OP:, ID], a!b: [ID, OP:!, ID], x-1: [ID, OP:, OP:-, NUM], } for src, want in cases.items(): got [f{t.kind}:{t.text} if t.kind OP else t.kind for t in tokenize(src)[:-1]] assert got want, f{src} - {got}, 期望 {want}5.2 现象a b * c算出来的结果不对但代码看起来完全正确原因在语法分析不在语义分析。递归下降的层级顺序决定了优先级parse_add必须调用parse_mulparse_mul再调用parse_primary顺序写反就变成乘法优先于加法反向。另一种情况是parse_cmp放在了parse_add上面导致a b c被解析成a (b c)。解决方法是打印 AST 看一眼树形而不是盯着表达式结果猜。加一个dump(node, indent0)递归打印a b * c应该长出BinOp(, Var(a), BinOp(*, Var(b), Var(c)))的形状。5.3 现象块内声明的变量在块外还能用或者反过来全局变量在函数里查不到符号表的作用域进出没配对。while的花括号、if的花括号、函数定义的花括号每一对都要对应一次enter和leave少一次或者多一次都会让作用域错位。最常见的是if语句的else分支忘记单独enter导致两个分支的局部变量混在同一个作用域里。解决方法是把作用域进出封装成上下文管理器用with保证异常路径也能正确弹出。from contextlib import contextmanager contextmanager def scope(table): table.enter() try: yield table finally: table.leave()5.4 现象while循环执行两次就停了或者死循环不退出回填的目标地址差了一条指令。jf的目标应该指向循环体之后的第一条指令而jmp的目标应该指向条件表达式的起始位置这两个下标都容易写成len(quads)或者len(quads) - 1。差一位的表现很有迷惑性短循环看起来正常次数一多就露馅。解决方法是打印带下标的四元式列表人工核对手算的跳转目标。更省事的做法是在patch里加断言检查目标下标是否落在合法范围内。5.5 现象中文全角符号导致词法报错定位偏移错误信息指向错误的行根源是列号计算没有区分字节和字符。如果源文件按字节读入一个中文字符占三字节col的推进就跟编辑器里看到的列不一致。另一种情况是文件里混了\r\n只处理\n会让\r被当成非法字符。解决方法是统一用文本模式读文件并且在扫描循环里把\r和\n都算作换行。如果题目强制要求处理全角符号就在词法层给出明确提示而不是让它落到「非法字符」这种笼统报错里。6. 让编译器自己说话三档 dump 开关与用例对拍脚本课设做到后期真正省时间的是可观测性。我的习惯是在动手写功能之前先加三个开关--dump-tokens、--dump-ast、--dump-ir分别打印词法结果、语法树和四元式。功能每完成一块就用开关看一眼中间产物问题定位从「猜」变成「看」。这套习惯在真实项目里同样成立一个 DSL 解析器如果连中间产物都打印不出来排障成本会高得离谱。对拍脚本不用复杂框架一个 bash 循环就够#!/usr/bin/env bash # cases/ 下放 xxx.lang期望输出放 xxx.exp pass0; fail0 for src in cases/*.lang; do name$(basename $src .lang) got$(python3 compiler.py --run $src 21) want$(cat cases/$name.exp) if [ $got $want ]; then pass$((pass1)) else fail$((fail1)) echo FAIL: $name diff (echo $want) (echo $got) | head -20 fi done echo pass$pass fail$fail--run走完整链路并执行四元式输出直接和期望文件比对。diff只打前二十行避免一个用例刷屏。用例覆盖的顺序建议是纯算术、赋值与打印、if/else、while、嵌套作用域、五个故意写错的语法用例。前四个保证功能后两个保证错误路径不崩。还有一个具体技巧四元式打印时带上源码行号和缩进while的循环体缩进两级跳转目标用L3这种标签而不是裸数字。人眼读得懂比对也方便出问题时能直接对着源码找位置。我自己在这上面踩过的坑是反过来的一开始为了省事只打印裸四元式结果一个jmp目标错了翻了两个小时才在第十二条指令里找到差一的位置。后来所有中间表示都加标签和缩进再没在这类问题上耗过时间。希望帮到你。本文还有配套的精品资源点击获取