简介这是一份面向编译原理初学者与Python开发者的实践型资源用Python语言实现了一个C语言编译器采用LL1文法完成语法分析并借助C语言空语句巧妙化解左递归难题适合想动手理解词法分析、语法分析、语义分析与代码生成全流程的读者。压缩包共21个文件约42KB以8个py源码文件为核心辅以5个txt文法与字符串说明、5个pyc缓存、1个asm汇编输出、1个c示例及1份docx文档结构紧凑便于按模块研读。目前已有277人学习下载。读者可从中获得完整的文法规则、LL1解析表构建思路、抽象语法树生成逻辑以及各阶段组件的Python实现代码既能对照源码理解编译器工作原理也能作为课程设计或自学编译技术的参考范例对提升Python工程能力与编译技术认知均有帮助。1. 用 Python 写一个 C 语言编译器从词法到 LL(1) 语法分析的最小闭环很多人第一次听到「用 Python 写 C 语言编译器」第一反应是「Python 这么慢能扛得住编译器的活吗」。我当初也这么想直到自己动手把词法分析、LL(1) 语法分析、四则运算求值这条链路跑通才发现真正卡住新手的从来不是性能而是不知道从哪一行代码开始。这个方向解决的核心问题是把「编译器开发」这个听起来高不可攀的黑匣子拆成你能在一台装了 Python 的笔记本上、一个下午就能看到中间结果的可复现流程。它适合三类人正在学编译原理但被龙书劝退的学生、想给 C 语言子集做静态检查工具的后端工程师、以及想搞懂「编译器和编辑器的区别」到底在哪的从业者。下面这套方案不追求完整支持 C99而是先做一个能解析声明、赋值、表达式和 if/while 的 C 子集编译器前端把 LL(1) 文法这条主线走通后面再往上加特性就有据可依。2. 词法分析器把 C 源码切成 token 流2.1 为什么词法分析要单独抽一层编译器前端第一步永远是词法分析lexer它的职责非常单一把一串字符流变成一串有类型的 token 流。很多人图省事直接在语法分析里用正则去匹配字符写着写着就发现代码里到处是pos、peek()、advance()的散落调用改一个关键字要动五个地方。把 lexer 独立出来好处是语法分析器只需要面对Token(type, value, line, col)这种结构完全不用关心空白、注释、换行怎么处理。C 语言的词法规则里真正需要小心的是这几类关键字int、if、while、return、标识符、整数字面量、字符串字面量、运算符含、!、、、、||这类双字符、分隔符;、,、(、)、{、}。注释//和/* */要在这一层直接丢掉不要留给语法分析。2.2 用 Python 实现一个可跑的 lexer下面这份代码是我常用的最小骨架直接复制就能跑。它用re做模式匹配但匹配顺序严格按「长运算符优先」排列避免把吃掉。import re from dataclasses import dataclass dataclass class Token: type: str # 如 KEYWORD / IDENT / INT / OP / PUNC / EOF value: str line: int col: int # 顺序很重要双字符运算符必须排在单字符前面 TOKEN_SPEC [ (COMMENT, r//[^\n]*|/\*[\s\S]*?\*/), (STRING, r(?:\\.|[^\\])*), (FLOAT, r\d\.\d), (INT, r\d), (KEYWORD, r\b(?:int|char|void|if|else|while|for|return|break|continue)\b), (IDENT, r[A-Za-z_]\w*), (OP, r|!||||\|\||[-*/%!]), (PUNC, r[;,.()\[\]{}]), (SKIP, r[ \t\r\n]), (MISMATCH, r.), ] MASTER_RE re.compile(|.join(f(?P{n}{p}) for n, p in TOKEN_SPEC)) def tokenize(src: str): line, line_start 1, 0 tokens [] for m in MASTER_RE.finditer(src): kind m.lastgroup text m.group() col m.start() - line_start 1 if kind SKIP: pass elif kind COMMENT: pass elif kind MISMATCH: raise SyntaxError(f非法字符 {text!r} 在第 {line} 行第 {col} 列) else: tokens.append(Token(kind, text, line, col)) # 更新行号按换行符数量推进 nl text.count(\n) if nl: line nl line_start m.end() - text.rfind(\n) - 1 tokens.append(Token(EOF, , line, 1)) return tokens逻辑说明MASTER_RE把所有模式合成一个正则finditer从左到右扫描谁先匹配上就用谁所以TOKEN_SPEC里的顺序就是优先级。COMMENT和SKIP匹配到后直接丢弃不产生 token。行号列号在循环里维护遇到换行就更新line_start这样报错时能精确指到位置。参数说明FLOAT放在INT前面否则3.14会被切成3、.、14三个 token。KEYWORD用\b边界保证integer不会被误判成int。MISMATCH兜底任何没被前面规则吃掉的字符直接抛错比默默跳过安全得多。跑一下tokenize(int a 10; // 注释\nif (a 10) return a;)你会看到KEYWORD int、IDENT a、OP 、INT 10、PUNC ;这样一条干净的流。这一步跑通后面语法分析才有稳定的输入。3. LL(1) 语法分析用递归下降把 token 流变成语法树3.1 为什么选 LL(1) 而不是 LR编译器开发里语法分析有两大流派自顶向下的 LL 和自底向上的 LR。LR 能处理的文法更强但手写 LR 分析器对新手极不友好状态机、冲突消解、移进归约表这些东西光调试就能耗掉一周。LL(1) 的核心优势是「一个非终结符 一个向前看 token 就能唯一决定用哪条产生式」这意味着你可以直接写递归下降函数每个非终结符对应一个 Python 函数代码结构和文法几乎一一对应改文法就是改函数调试成本极低。代价是 LL(1) 对文法有要求不能有左递归不能有公共左因子。C 语言的表达式文法天然左递归expr - expr term所以要先做消除左递归的改写。这一步是 LL(1) 路线里最容易翻车的地方后面避坑章节会专门讲。3.2 把 C 子集文法改写成 LL(1) 形式先定义我们要支持的文法子集用 EBNF 写program - stmt_list EOF stmt_list - stmt stmt_list | ε stmt - decl_stmt | assign_stmt | if_stmt | while_stmt | return_stmt | block decl_stmt - int IDENT expr ; assign_stmt- IDENT expr ; if_stmt - if ( expr ) stmt (else stmt)? while_stmt - while ( expr ) stmt return_stmt- return expr? ; block - { stmt_list } expr - term expr_tail expr_tail - ( | -) term expr_tail | ε term - factor term_tail term_tail - (* | /) factor term_tail | ε factor - INT | IDENT | ( expr )关键改动是把expr - expr term这种左递归改成了expr - term expr_tailexpr_tail负责处理后续的加减。这样每个非终结符的 FIRST 集互不冲突向前看一个 token 就能决定分支。3.3 递归下降分析器的 Python 实现class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): return self.tokens[self.pos] def eat(self, ttypeNone, valueNone): tok self.tokens[self.pos] if ttype and tok.type ! ttype: raise SyntaxError(f第 {tok.line} 行期望 {ttype}实际 {tok.type}({tok.value})) if value and tok.value ! value: raise SyntaxError(f第 {tok.line} 行期望 {value!r}实际 {tok.value!r}) self.pos 1 return tok def parse_program(self): stmts [] while self.peek().type ! EOF: stmts.append(self.parse_stmt()) return (program, stmts) def parse_stmt(self): tok self.peek() if tok.type KEYWORD and tok.value int: return self.parse_decl() if tok.type KEYWORD and tok.value if: return self.parse_if() if tok.type KEYWORD and tok.value while: return self.parse_while() if tok.type KEYWORD and tok.value return: return self.parse_return() if tok.type PUNC and tok.value {: return self.parse_block() if tok.type IDENT: return self.parse_assign() raise SyntaxError(f第 {tok.line} 行无法识别的语句起始 {tok.value!r}) def parse_decl(self): self.eat(KEYWORD, int) name self.eat(IDENT).value self.eat(OP, ) val self.parse_expr() self.eat(PUNC, ;) return (decl, name, val) def parse_assign(self): name self.eat(IDENT).value self.eat(OP, ) val self.parse_expr() self.eat(PUNC, ;) return (assign, name, val) def parse_if(self): self.eat(KEYWORD, if) self.eat(PUNC, () cond self.parse_expr() self.eat(PUNC, )) then self.parse_stmt() els None if self.peek().type KEYWORD and self.peek().value else: self.eat(KEYWORD, else) els self.parse_stmt() return (if, cond, then, els) def parse_while(self): self.eat(KEYWORD, while) self.eat(PUNC, () cond self.parse_expr() self.eat(PUNC, )) body self.parse_stmt() return (while, cond, body) def parse_return(self): self.eat(KEYWORD, return) val None if self.peek().type ! PUNC or self.peek().value ! ;: val self.parse_expr() self.eat(PUNC, ;) return (return, val) def parse_block(self): self.eat(PUNC, {) stmts [] while not (self.peek().type PUNC and self.peek().value }): stmts.append(self.parse_stmt()) self.eat(PUNC, }) return (block, stmts) def parse_expr(self): node self.parse_term() while self.peek().type OP and self.peek().value in (, -): op self.eat(OP).value rhs self.parse_term() node (binop, op, node, rhs) return node def parse_term(self): node self.parse_factor() while self.peek().type OP and self.peek().value in (*, /): op self.eat(OP).value rhs self.parse_factor() node (binop, op, node, rhs) return node def parse_factor(self): tok self.peek() if tok.type INT: self.eat(INT) return (int, int(tok.value)) if tok.type IDENT: self.eat(IDENT) return (var, tok.value) if tok.type PUNC and tok.value (: self.eat(PUNC, () node self.parse_expr() self.eat(PUNC, )) return node raise SyntaxError(f第 {tok.line} 行表达式里出现非法 token {tok.value!r})逻辑说明每个parse_xxx方法对应文法里一个非终结符peek()看当前 token 决定走哪条分支eat()消费并校验。parse_expr和parse_term用 while 循环处理expr_tail和term_tail把左递归改写成迭代这是递归下降处理二元运算符的标准写法。返回的元组就是语法树节点(binop, , left, right)这种结构后面做求值或代码生成时直接递归遍历即可。参数说明eat同时支持按类型和按值校验eat(KEYWORD, int)比只校验类型更严格能防止把char误当int处理。parse_return里判断return;这种无返回值的情况避免把分号当表达式解析。parse_factor里(分支递归调用parse_expr天然支持括号嵌套。把 lexer 和 parser 串起来Parser(tokenize(src)).parse_program()输入int a 1 2 * 3; if (a 7) return a;你会得到一棵嵌套元组表示的语法树。到这一步一个 C 子集编译器的前端骨架就立住了。4. 语义检查与求值让语法树真正跑起来4.1 符号表要解决什么问题语法分析只保证结构合法但int a b 1;里b没声明过语法上是合法的语义上是错的。符号表symbol table就是干这个的记录每个变量的类型、作用域、是否已初始化。C 语言的作用域是块级的{}里声明的变量出了块就失效所以符号表要用栈式结构进块压一层出块弹一层。常见做法是用一个list[dict]每层是一个 dict查找时从栈顶往下找。变量重复声明、使用未声明变量、类型不匹配这三类错误在这一层报出来比拖到代码生成阶段再发现要省事得多。4.2 用访问者模式做求值语法树是元组嵌套直接写递归函数遍历就行不需要引入复杂的 visitor 类。下面这个求值器支持整数运算和变量读写class Evaluator: def __init__(self): self.scopes [{}] # 栈式作用域scopes[-1] 是当前块 def declare(self, name, value): if name in self.scopes[-1]: raise NameError(f变量 {name} 重复声明) self.scopes[-1][name] value def lookup(self, name): for scope in reversed(self.scopes): if name in scope: return scope[name] raise NameError(f使用了未声明的变量 {name}) def assign(self, name, value): for scope in reversed(self.scopes): if name in scope: scope[name] value return raise NameError(f赋值给未声明的变量 {name}) def eval(self, node): kind node[0] if kind int: return node[1] if kind var: return self.lookup(node[1]) if kind binop: op, l, r node[1], self.eval(node[2]), self.eval(node[3]) if op : return l r if op -: return l - r if op *: return l * r if op /: if r 0: raise ZeroDivisionError(除零) return l // r raise ValueError(f未知节点 {kind}) def exec_stmt(self, node): kind node[0] if kind decl: self.declare(node[1], self.eval(node[2])) elif kind assign: self.assign(node[1], self.eval(node[2])) elif kind block: self.scopes.append({}) for s in node[1]: self.exec_stmt(s) self.scopes.pop() elif kind if: if self.eval(node[1]): self.exec_stmt(node[2]) elif node[3] is not None: self.exec_stmt(node[3]) elif kind while: guard 0 while self.eval(node[1]): self.exec_stmt(node[2]) guard 1 if guard 1_000_000: raise RuntimeError(疑似死循环已中断) elif kind return: raise _Return(self.eval(node[2]) if node[2] else None) class _Return(Exception): def __init__(self, value): self.value value逻辑说明scopes是列表套字典declare只往当前层写lookup和assign从栈顶往下找这样内层块能遮蔽外层同名变量符合 C 的作用域规则。exec_stmt处理语句eval处理表达式block分支压栈弹栈while加了 100 万次迭代的保险丝防止写错条件导致进程卡死。return用异常实现因为 Python 没有 goto异常是跳出多层嵌套最干净的方式。参数说明/用整除//因为我们只支持整数类型要支持浮点得在 lexer 里保留FLOAT并在这里分支。guard上限可以按需调调试阶段设小一点比如 1 万能更快暴露死循环。_Return继承Exception而不是BaseException避免和KeyboardInterrupt混淆。把Evaluator和前面的Parser接起来跑int a 1 2 * 3; if (a 7) return a;最终能拿到返回值 7。这条链路走通说明你的编译器前端已经能正确理解并执行一个 C 子集了。5. 避坑与排查LL(1) 编译器最容易翻车的 5 个地方5.1 现象表达式1 - 2 - 3算出来是 2 而不是 -4原因消除左递归时把结合性搞反了。原始文法expr - expr - term是左结合改写成expr - term expr_tail、expr_tail - - term expr_tail后如果求值时写成node (binop, op, rhs, node)就变成了右结合1 - (2 - 3) 2。解决在parse_expr的 while 循环里始终把已解析的左节点放在左边node (binop, op, node, rhs)。判断结合性对不对用10 - 3 - 2测正确答案是 5如果得到 9 就是结合性反了。5.2 现象if (a 0) if (b 0) x 1; else x 2;里 else 挂错了 if原因悬空 elsedangling else问题。LL(1) 文法里if_stmt - if ( expr ) stmt (else stmt)?当stmt本身又是一个 if 时向前看一个 token 无法区分 else 属于哪层。解决约定 else 就近匹配在parse_if里解析完 then 分支后立刻检查 else这样 else 自然绑定到最近的未匹配 if。这是 C 语言的实际行为也是大多数手写递归下降的默认选择。要验证把上面的代码跑一遍看x最终是 1 还是 2正确结果是 1外层条件为真时内层 else 不执行。5.3 现象lexer 把ab切成a、、、b而不是a、、、b原因正则的贪婪匹配和模式顺序。OP模式里[-*/%!]是单字符如果没单独列出来会被切成、或、取决于顺序。解决把所有多字符运算符显式列在单字符前面|!||||\|\||\\|--|[-*/%!]。C 语言里和--是独立 token必须优先匹配。测试用例用ab和a---b看切分结果是否符合 C 的「最长匹配」规则。5.4 现象解析int a 10;时报「期望 IDENT实际 KEYWORD」原因parse_stmt里判断声明语句时只检查了tok.value int但没检查tok.type KEYWORD或者关键字表里漏了int。另一种可能是 lexer 的KEYWORD正则里\b边界写错导致int被IDENT先匹配走。解决在parse_stmt里同时校验类型和值if tok.type KEYWORD and tok.value int。lexer 里确认KEYWORD排在IDENT前面且用了\b边界。调试时先单独跑tokenize(int a;)看第一个 token 是不是KEYWORD int是的话问题在 parser不是的话问题在 lexer。5.5 现象嵌套块里修改外层变量出了块发现没改到原因declare和assign混用了。如果内层块里写int a 5;declare只写当前层这是对的但如果写a 5;不带 int应该走assign去外层找结果代码里错误地调了declare就在内层新建了一个同名变量外层没动。解决严格区分声明和赋值。decl节点走declareassign节点走assign。测试用例外层int a 1;内层块{ a 2; }出块后打印a应该是 2如果内层写{ int a 2; }出块后a应该还是 1。这两个用例能一次性验证作用域逻辑对不对。6. 从解释执行到字节码给编译器加一个后端前端跑通之后下一步自然是让它真的「编译」出东西而不是边解析边求值。最省事的后端是生成 Python 字节码或者自定义栈式指令我这里选后者因为指令集简单、可读、方便调试。核心思路是把语法树翻译成一串LOAD_INT、LOAD_VAR、ADD、STORE、JUMP_IF_FALSE这样的指令再用一个栈式虚拟机执行。先定义指令格式用元组(op, arg)表示arg可选def compile_expr(node, out): kind node[0] if kind int: out.append((LOAD_INT, node[1])) elif kind var: out.append((LOAD_VAR, node[1])) elif kind binop: compile_expr(node[2], out) compile_expr(node[3], out) out.append({: ADD, -: SUB, *: MUL, /: DIV}[node[1]]) def compile_stmt(node, out): kind node[0] if kind decl or kind assign: compile_expr(node[2], out) out.append((STORE, node[1])) elif kind block: for s in node[1]: compile_stmt(s, out) elif kind if: compile_expr(node[1], out) jf len(out); out.append((JUMP_IF_FALSE, None)) compile_stmt(node[2], out) if node[3] is not None: jmp len(out); out.append((JUMP, None)) out[jf] (JUMP_IF_FALSE, len(out)) compile_stmt(node[3], out) out[jmp] (JUMP, len(out)) else: out[jf] (JUMP_IF_FALSE, len(out)) elif kind while: start len(out) compile_expr(node[1], out) jf len(out); out.append((JUMP_IF_FALSE, None)) compile_stmt(node[2], out) out.append((JUMP, start)) out[jf] (JUMP_IF_FALSE, len(out))逻辑说明表达式编译用后序遍历先压左再压右最后发运算符指令这是栈式虚拟机的标准做法。if和while用回填backpatch技术先发一条占位跳转指令等目标位置确定后再把地址填回去。while的JUMP start形成循环JUMP_IF_FALSE在条件为假时跳出。参数说明JUMP_IF_FALSE的arg是目标指令索引回填时用len(out)取当前指令数作为跳转目标。STORE同时用于声明和赋值因为在这个简化模型里变量不需要预先声明类型符号表在虚拟机运行时维护。虚拟机执行循环大概长这样def run(bytecode): stack, env, pc [], {}, 0 while pc len(bytecode): op, arg bytecode[pc]; pc 1 if op LOAD_INT: stack.append(arg) elif op LOAD_VAR: stack.append(env[arg]) elif op STORE: env[arg] 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 JUMP: pc arg elif op JUMP_IF_FALSE: if stack.pop() 0: pc arg return env验证方法很直接同一段源码分别走Evaluator和「编译 虚拟机」两条路比较最终env里的变量值是否一致。不一致就说明后端翻译有 bug用print(bytecode)把指令序列打出来逐条对照语法树找差异。这个对拍differential testing习惯是我调试编译器时最依赖的手段比单步跟踪快得多。最后说个我自己的习惯每加一个语言特性先写三个测试用例——一个正常路径、一个边界空块、零次循环、一个错误路径未声明变量、除零跑通了再往下走。编译器这东西后悔药就是测试用例写的时候嫌烦出 bug 的时候真香。希望帮到你。本文还有配套的精品资源点击获取