简介这份资源面向学习编译原理、需要完成课程设计的高校学生围绕SLR(1)分析法实现一个小型编译程序解决从高级语言源程序到四元式程序翻译的实践问题。资源包共14个文件压缩后约22KB以c源码、dat测试数据、asm汇编输出、med中间结果和txt说明文档为主分别对应编译主程序、输入用例、目标代码与运行记录结构紧凑便于对照调试。目前已有2775人学习下载说明其在同类课设中具有较高参考价值。读者可借助其中的SLR(1)分析表实现思路、表达式分析过程记录以及四元式与汇编程序输出样例理解词法分析、语法分析与中间代码生成的衔接方式并在此基础上自行改进。资源同时给出参考书籍与习题解析线索适合作为编译原理上机与课程设计的起步模板。1. 从「实现一个小型编译程序.zip」说起为什么我劝你手写一遍而不是背龙书很多人第一次搜「实现一个小型编译程序.zip」心里想的其实是有没有一份能直接跑通的代码把词法、语法、语义、代码生成串起来让我看看一个编译器到底长什么样。我当年也是这么想的结果下载了一堆压缩包解压出来要么是半成品要么是某个课程作业跑起来报错都不知道从哪查。后来我干脆自己从零写了一个才发现真正的门槛不在算法多难而在于「每一层怎么衔接、错误怎么定位、中间表示怎么设计」这些书上不会细讲的东西。这篇笔记就围绕「实现一个小型编译程序」这件事把我在一线做工具链和 DSL 时反复用到的方案拆开讲。目标很明确让你能在一个周末内跑通一个支持变量声明、四则运算、条件分支和函数调用的迷你编译器输出可执行的类汇编或字节码。适合有 C/C/Python 基础、学过编译原理但没动手写过的同学也适合想给自家 DSL 加个编译后端的工程师。我不会假装手里有某个具体 zip 的源码而是按最常见的可靠路径把每一步的命令、参数和踩坑点写清楚。2. 先定架构再写代码小型编译程序的四层拆分与选型2.1 为什么我坚持「手写递归下降 栈式虚拟机」而不是一上来就上 LLVM小型编译程序最容易翻车的地方是选型太贪。很多人一上来就想接 LLVM结果 IR 还没生成明白先被 LLVM 的版本和 API 折腾掉一周。我的血泪经验是如果你的目标是「理解编译全流程并跑通」那就手写递归下降解析器 生成栈式虚拟机的字节码。这套组合的优点是每一层都透明出错时你能直接看到 token 流、AST 和指令序列没有黑匣子。具体分层是这样的第一层词法分析把源码切成 token第二层语法分析用递归下降构建 AST第三层语义分析做符号表管理和类型检查第四层代码生成把 AST 翻译成栈机指令。栈机的好处是代码生成规则极其规整每个表达式节点对应几条 push/pop/运算指令新手也能写对。等你把这套跑通再去接 LLVM 或生成 x86 汇编心里就有底了。选型上还有几个具体决定词法用手写扫描器而不是 lex因为小型语言的 token 规则简单手写反而更好调试语法用递归下降而不是 yacc/bison因为错误恢复和报错信息可控目标用自定义字节码而不是直接生成汇编因为字节码可以用 Python 或 C 写个 200 行的解释器来验证。这些选择在「实现一个小型编译程序」这个场景下是投入产出比最高的。2.2 用 Python 搭出词法分析器30 行代码和三个必调参数下面是我常用的词法分析器骨架用 Python 写方便你直接复制运行。它支持标识符、整数、四则运算符、括号和分号。import re TOKEN_SPEC [ (NUMBER, r\d), (ID, r[A-Za-z_]\w*), (ASSIGN, r), (PLUS, r\), (MINUS, r-), (MUL, r\*), (DIV, r/), (LPAREN, r\(), (RPAREN, r\)), (LBRACE, r\{), (RBRACE, r\}), (SEMI, r;), (IF, rif), (ELSE, relse), (WHILE, rwhile), (SKIP, r[ \t\n]), (MISMATCH, r.), ] def tokenize(code): tokens [] pos 0 while pos len(code): for name, pattern in TOKEN_SPEC: regex re.compile(pattern) match regex.match(code, pos) if match: text match.group(0) if name ! SKIP: tokens.append((name, text)) pos match.end() break else: raise SyntaxError(fUnexpected character at {pos}) return tokens这段代码的逻辑是按顺序尝试每个正则第一个匹配上的就作为当前 token。参数上你需要注意三点一是TOKEN_SPEC的顺序关键字必须放在标识符前面否则if会被当成 ID二是SKIP要放在最后但要在MISMATCH之前否则空格会报错三是MISMATCH用来捕获非法字符方便定位错误位置。我一般会在 tokenize 里加一个行号追踪把(name, text, line)存下来后面报错时能直接指出第几行。2.3 递归下降解析器把 AST 节点和优先级爬升写对语法分析我用递归下降加优先级爬升处理四则运算的优先级和结合性。核心是每个非终结符对应一个函数表达式用parse_expr(min_prec)统一处理。class ASTNode: def __init__(self, kind, **kwargs): self.kind kind self.__dict__.update(kwargs) class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): return self.tokens[self.pos] if self.pos len(self.tokens) else (EOF, ) def next(self): tok self.peek() self.pos 1 return tok def expect(self, kind): tok self.next() if tok[0] ! kind: raise SyntaxError(fExpected {kind}, got {tok}) return tok def parse_expr(self, min_prec0): left self.parse_primary() while True: tok self.peek() prec {PLUS: 1, MINUS: 1, MUL: 2, DIV: 2}.get(tok[0], -1) if prec min_prec: break op self.next()[0] right self.parse_expr(prec 1) left ASTNode(BinOp, opop, leftleft, rightright) return left def parse_primary(self): tok self.peek() if tok[0] NUMBER: self.next() return ASTNode(Number, valueint(tok[1])) elif tok[0] ID: self.next() return ASTNode(Var, nametok[1]) elif tok[0] LPAREN: self.next() expr self.parse_expr() self.expect(RPAREN) return expr else: raise SyntaxError(fUnexpected token {tok})这里的关键参数是min_prec它控制当前解析的表达式最低优先级。prec 1保证左结合如果你想支持右结合比如赋值就传prec而不是prec 1。我踩过的坑是忘记在parse_primary里处理括号导致(12)*3解析成12*3。另外peek在末尾返回(EOF, )是个好习惯避免索引越界。3. 语义分析与符号表类型检查和作用域怎么落地3.1 符号表用栈式结构每个作用域一个字典语义分析阶段我一般用一个栈式符号表进入块时压入新字典退出时弹出。每个变量记录类型和是否初始化。class SymbolTable: def __init__(self): self.scopes [{}] def enter_scope(self): self.scopes.append({}) def exit_scope(self): self.scopes.pop() def declare(self, name, typ): if name in self.scopes[-1]: raise SemanticError(fDuplicate declaration: {name}) self.scopes[-1][name] {type: typ, initialized: False} def lookup(self, name): for scope in reversed(self.scopes): if name in scope: return scope[name] raise SemanticError(fUndeclared variable: {name}) def mark_initialized(self, name): for scope in reversed(self.scopes): if name in scope: scope[name][initialized] True return raise SemanticError(fUndeclared variable: {name})参数上要注意declare只检查当前作用域是否重复允许内层遮蔽外层lookup从内向外找符合词法作用域规则。我一般会在 AST 遍历时维护一个current_type遇到赋值就检查左右类型是否一致。小型语言里我只支持 int 和 bool类型检查规则简单但足以让你理解语义分析在干什么。3.2 遍历 AST 做类型检查三个必须拦截的错误类型检查我写成一个递归函数check(node)返回节点的类型。必须拦截的错误有三类未声明变量、重复声明、类型不匹配。下面是一个简化版。def check(node, symtab): if node.kind Number: return int elif node.kind Var: sym symtab.lookup(node.name) if not sym[initialized]: raise SemanticError(fVariable {node.name} used before initialization) return sym[type] elif node.kind BinOp: left_type check(node.left, symtab) right_type check(node.right, symtab) if left_type ! int or right_type ! int: raise SemanticError(fType mismatch in {node.op}) return int elif node.kind Assign: right_type check(node.right, symtab) sym symtab.lookup(node.left.name) if sym[type] ! right_type: raise SemanticError(fCannot assign {right_type} to {sym[type]}) symtab.mark_initialized(node.left.name) return right_type else: raise SemanticError(fUnknown node kind: {node.kind})这段代码里mark_initialized很关键它保证变量先赋值后使用。我见过很多课程作业忽略这一点导致生成的代码里出现未初始化就读取的指令。另外check返回类型而不是布尔值方便父节点继续推导。如果你要支持 bool就在BinOp里根据运算符区分算术和比较。3.3 作用域嵌套的坑块级作用域和变量遮蔽小型语言如果支持{}块就要处理作用域嵌套。我一般会在解析Block节点时调用enter_scope和exit_scope。这里有个容易翻车的地方变量遮蔽。比如外层有x内层又声明x内层赋值不应该影响外层。我的做法是declare只写当前作用域lookup从内向外找mark_initialized也只标记找到的第一个。这样内层x和外层x是两个独立条目互不干扰。另一个坑是函数调用。如果你支持函数符号表里要记录参数类型和返回类型调用时检查实参类型。我一般把函数签名存在全局作用域函数体进入新作用域时把参数声明进去。这样递归调用也能正确解析。4. 代码生成与虚拟机把 AST 翻译成可执行字节码4.1 栈机指令集设计12 条指令够用我设计的栈机指令集只有 12 条PUSH、POP、ADD、SUB、MUL、DIV、LOAD、STORE、JMP、JZ、CALL、RET。每条指令操作一个操作数栈。代码生成时表达式节点递归生成指令最后栈顶就是结果。def gen(node, code): if node.kind Number: code.append((PUSH, node.value)) elif node.kind Var: code.append((LOAD, node.name)) elif node.kind BinOp: gen(node.left, code) gen(node.right, code) op_map {PLUS: ADD, MINUS: SUB, MUL: MUL, DIV: DIV} code.append((op_map[node.op],)) elif node.kind Assign: gen(node.right, code) code.append((STORE, node.left.name)) elif node.kind If: gen(node.cond, code) jz_index len(code) code.append((JZ, None)) gen(node.then, code) if node.else_: jmp_index len(code) code.append((JMP, None)) code[jz_index] (JZ, len(code)) gen(node.else_, code) code[jmp_index] (JMP, len(code)) else: code[jz_index] (JZ, len(code)) return code参数说明JZ和JMP的目标地址在生成时先填None后面回填。这是最常用的回填技术避免两遍扫描。STORE从栈顶弹出值存入变量LOAD把变量值压栈。我一般会在生成完所有指令后把变量名映射成栈帧偏移但小型语言直接用字典存变量也行虚拟机里用一个env字典。4.2 虚拟机执行循环30 行跑通所有指令虚拟机就是一个 while 循环不断取指令、执行、更新 pc。def run(code, envNone): if env is None: env {} stack [] pc 0 while pc len(code): op, *args code[pc] pc 1 if op PUSH: stack.append(args[0]) elif op POP: stack.pop() elif op ADD: b, a stack.pop(), stack.pop() stack.append(a b) elif op SUB: b, a stack.pop(), stack.pop() stack.append(a - b) elif op MUL: b, a stack.pop(), stack.pop() stack.append(a * b) elif op DIV: b, a stack.pop(), stack.pop() stack.append(a // b) elif op LOAD: stack.append(env[args[0]]) elif op STORE: env[args[0]] stack.pop() elif op JZ: if stack.pop() 0: pc args[0] elif op JMP: pc args[0] elif op CALL: # 简化处理直接跳转实际需要保存返回地址 pc args[0] elif op RET: break return stack[-1] if stack else None这段代码里ADD的弹出顺序是b, a stack.pop(), stack.pop()然后a b因为栈是后进先出。JZ弹出条件值为 0 就跳转。CALL和RET我做了简化实际实现函数调用需要维护调用栈保存返回地址。你可以先跑通表达式和赋值再加函数。4.3 从源码到运行一个完整示例的端到端命令把前面几段拼起来写一个compile_and_run(source)函数依次调用 tokenize、Parser、check、gen、run。下面是一个测试用例。source x 10; y 20; if (x y) { z x y * 2; } else { z 0; } tokens tokenize(source) parser Parser(tokens) ast parser.parse_program() # 需要你补全 parse_program symtab SymbolTable() check(ast, symtab) code gen(ast, []) result run(code) print(result) # 输出 50运行前你需要补全parse_program它循环调用parse_statement直到 EOF。parse_statement处理赋值、if、while 和块。我一般会先写一个只支持赋值和表达式的版本跑通后再加控制流。这样每一步都有可验证的输出不会一上来就被复杂语法卡住。5. 避坑与排查小型编译程序最常见的五类翻车5.1 词法分析把关键字识别成标识符现象if被当成变量名解析时报「未声明变量 if」。原因是TOKEN_SPEC里ID的正则排在IF前面正则引擎先匹配了ID。解决把关键字规则放在ID之前或者匹配到ID后查关键字表。我一般用后者因为关键字多了以后正则顺序容易乱。5.2 递归下降解析器死循环现象解析到某个 token 时pos不前进程序卡死。原因通常是parse_primary遇到不认识的 token 没有报错也没有消费外层循环一直调用同一个函数。解决在parse_primary的 else 分支里直接raise SyntaxError并且确保每个分支都调用next()或expect()。我还会在parse_expr循环里加一个断言如果pos没变就抛异常。5.3 代码生成时栈不平衡现象虚拟机执行到某条指令时栈为空报 IndexError。原因是表达式生成时多压或少弹了值。解决在gen里对每个节点保证「生成完指令后栈净增 1」。比如BinOp先 gen 左再 gen 右栈增 2然后 ADD 弹 2 压 1净增 1。你可以在每步后打印栈深度来排查。5.4 跳转地址回填错误现象if 语句执行时跳到了错误位置或者无限循环。原因是JZ的目标地址在回填时算错了。解决回填时用len(code)而不是len(code) - 1因为 pc 在执行完当前指令后已经加 1。我一般会在回填后打印整个指令序列人工核对跳转目标。5.5 变量作用域没隔离导致值被覆盖现象内层块修改同名变量外层变量也跟着变。原因是符号表只有一个字典没有按作用域分层。解决用栈式符号表进入块时enter_scope退出时exit_scope。代码生成时变量名要加上作用域前缀或者虚拟机里用环境链。小型语言我直接用字典嵌套简单可靠。6. 进阶技巧用快照测试锁住编译器行为当你把基本流程跑通后最值得投入的一件事是给编译器加一套快照测试。做法很简单准备一组源文件每个文件对应一个期望的字节码序列或运行结果每次改动后自动比对。这样你重构解析器或优化代码生成时能立刻知道有没有破坏已有行为。我一般用 Python 的pytest加syrupy或者自己写一个assert_code(source, expected)。下面是一个最小实现。import json def compile_to_json(source): tokens tokenize(source) parser Parser(tokens) ast parser.parse_program() symtab SymbolTable() check(ast, symtab) code gen(ast, []) return json.dumps(code, indent2) def test_snapshot(): source x 1 2 * 3; expected [ [PUSH, 1], [PUSH, 2], [PUSH, 3], [MUL], [ADD], [STORE, x] ] assert json.loads(compile_to_json(source)) expected这个测试的价值在于它把「编译器行为」变成了可版本控制的文本。你每次改代码生成规则跑一遍测试就知道有没有回归。我还会加一个test_run验证运行结果比如x 1 2 * 3跑完env[x]应该是 7。这两个测试加起来不到 50 行但能帮你省下大量调试时间。另一个技巧是给虚拟机加一个trace模式每执行一条指令就打印 pc、指令和栈内容。排查复杂控制流时这个 trace 比任何断点都直观。我一般用环境变量TRACE1控制默认关闭需要时打开。最后说个我自己的习惯每实现一个新语法特性先写一个最小源文件手动推导它应该生成什么指令再和编译器输出比对。如果对不上先怀疑自己的推导再怀疑编译器。这个习惯让我在写小型编译程序时少走了很多弯路。希望帮到你。本文还有配套的精品资源点击获取
