用Python写C语言编译器：从词法分析到三地址码的完整实践

简介这是一个使用Python语言实现的C语言编译器项目面向计算机专业学生、编译原理学习者及对解释器/编译器实现感兴趣的开发者。项目基于LL(1)文法的自顶向下语法分析完整覆盖词法分析、语法分析、语义检查与代码生成等核心环节并借助C语言空语句巧妙解决了左递归问题适合作为编译原理课程的实践参考。压缩包共21个文件大小42KB核心部分为8个Python源码文件分别实现词法、语法、语义及汇编代码生成等模块另含5个文本文件文法规则、测试字符串、中间代码等、5个编译后的pyc文件、1个C示例程序、1个汇编输出文件及1份docx格式文档便于对照学习。资源已有275人学习下载通过阅读源码、文法定义与输出示例可直观理解LL(1)分析表构造、递归下降解析及中间代码生成流程同时提升Python编程与编译技术综合能力。1. 用Python写C语言编译器先想清楚你是在做翻译器还是解释器第一次听说“用Python写C语言编译器”大部分人第一反应是“Python这么慢能编译C吗”。真上手之后你会发现这个方向的价值不在性能在过程——当你想搞懂编译器到底怎么把代码变成机器能理解的东西用Python把词法分析、语法分析、语义分析一路写下来比读十遍龙书都有用。我自己是在做代码结构分析工具时入的坑需要一个能解析C语法、输出AST的轻量级组件GCC太重、Clang的API太复杂干脆用Python写一个够用的C子集编译器。它适合三类人有C语言基础的编译原理初学者、要做C代码静态分析的工程师、想给C加自定义方言的人。前提是你能接受它不追求编译速度、只求正确性和可读性。这个方向做出来的东西本质上是一个“看得见每一步的编译器”而不是又一个GCC。2. 选型与词法分析为什么用Python写编译器以及第一个能跑的tokenizer2.1 用Python当编译器宿主图的是哪三样东西先泼一盆冷水用Python写的C编译器在编译速度上永远追不上GCC和Clang。如果你要的是把大型C工程在几秒内编出可执行文件这个方向可以直接关掉。但编译器开发并不是只有“源码进、机器码出”这一种形态。代码格式化、静态检查、指标统计、教学演示、AST驱动的代码生成这些场景需要的是一个能解析C语法、输出结构化信息的工具链而不是一个把整个Linux内核编出来的重型编译器。这种情况下Python的三个特性正好打在要害上。第一没有指针和手动内存管理AST节点直接用嵌套的元组或字典表示天然适配树形结构代码里不会有malloc和free的噪音。第二标准库里的re、pprint、json让token流、AST、中间代码的调试非常直观你随时可以把一整棵语法树原样打印出来看。第三写测试的成本极低一个测试文件里放几十个C代码片段跑一遍pytest就能覆盖大部分语法路径同样的事用C写测试光是构造合法输入就得先写个parser。另外还有一个很实际的理由你要解析的C代码往往不是完整的编译单元可能是从某个大工程里抽出来的一个函数、一段宏展开后的片段甚至是语法不完整的实验代码。这种场景下GCC会直接报一堆错退出而你自己写的parser可以做成容错的——解析失败时返回局部AST和错误位置后续处理仍然可以继续。这是轻量级编译器方案最值钱的地方。2.2 词法分析器的最小实现从源码到token流词法分析是整个编译器里最不玄学、也最容易被低估的环节。它的任务很简单把源码字符串切成一串token每个token带类型、值、行号、列号。行号和列号一定要从第一天就带上否则后面语法报错只能告诉人家“第几行的第几个字符出错了”没有定位信息你会在调试时后悔死。我用标准库的正则来做最朴素的切分不引入第三方依赖。关键点是token类型要分清楚KEYWORD、IDENT、INT、FLOAT、CHAR、STRING、OP、PUNCT、EOF。其中CHAR和STRING必须分开这一点后面避坑章节会细说。下面的tokenizer实现覆盖了C语言的常见运算符和整数字面量KEYWORDS {int, char, void, return, if, else, while, for, break, struct} class Token: __slots__ (type, value, line, col) def __init__(self, type_, value, line, col): self.type type_ self.value value self.line line self.col col def __repr__(self): return fToken({self.type}, {self.value!r}, {self.line}:{self.col}) def tokenize(src): tokens [] i, n 0, len(src) line col 1 while i n: c src[i] if c in \t\r\n: if c \n: line 1; col 1 else: col 1 i 1 continue if c.isalpha() or c _: start i while i n and (src[i].isalnum() or src[i] _): i 1 word src[start:i] ttype KEYWORD if word in KEYWORDS else IDENT tokens.append(Token(ttype, word, line, col)) col i - start continue if c.isdigit(): start i if src[i] 0 and i1 n and src[i1] in xX: i 2 while i n and (src[i].isdigit() or src[i].lower() in abcdef): i 1 tokens.append(Token(INT, int(src[start:i], 16), line, col)) else: while i n and (src[i].isdigit() or src[i] .): i 1 if . in src[start:i]: tokens.append(Token(FLOAT, float(src[start:i]), line, col)) else: tokens.append(Token(INT, int(src[start:i]), line, col)) col i - start continue if c in -*/%!|^~: two src[i:i2] if two in (, !, , , , ||, , -): tokens.append(Token(OP, two, line, col)) i 2; col 2 else: tokens.append(Token(OP, c, line, col)) i 1; col 1 continue if c in (){}[];,.: tokens.append(Token(PUNCT, c, line, col)) i 1; col 1 continue raise SyntaxError(fline {line}, col {col}: 非法字符 {c!r}) tokens.append(Token(EOF, eof, line, col)) return tokens这段代码的逻辑是逐个字符扫描空白直接跳过并维护行列号字母和下划线开头的一律进标识符分支如果在关键字集合里就标记为KEYWORD数字分支里先判断十六进制前缀再判断小数点运算符分支先看双字符运算符再看单字符。字符串和字符字面量建议单独写函数处理避免主循环被拉得太长。参数说明KEYWORDS集合决定哪些字是关键字目前只覆盖了最常用的一批后续加类型比如unsigned、short、long时往里补就行。Token类型用的是字符串而不是整数枚举图的是调试时打印清楚性能不是第一诉求。如果以后要处理超大文件可以改成整数常量加映射表但当前这个体量完全没必要。2.3 跑通tokenizer一个可以直接执行的示例写完tokenizer先别急着写语法分析。你至少要用三个测试片段把词法层捶一遍一个正常函数、一个包含各种运算符的表达式、一个故意写成非法字符的文件。直接跑下面的脚本看输出if __name__ __main__: sample int main() { int a 0x1F; a a 1; return a; } for tok in tokenize(sample): print(tok)预期的输出应该能看到一行一行的Token先是Token(KEYWORD, int, 1:1)然后是Token(IDENT, main, 1:5)再是左右括号的PUNCT等。看到0x1F被识别成Token(INT, 31, 1:24)就说明十六进制分支工作正常。这一步跑通了后面parser出问题时你才能确定锅在语法层不在词法层。第一次写的同学很容易在这里踩坑正则写得太贪婪把a1的吞进标识符或者数字识别没判断小数点把3.14切成3和.两个token。这些小问题在词法层暴露比在语法层暴露好修一百倍。一个实用的建议文件很大时不要一次性读进来按块读并记录跨块边界的行列号设计上和C标准库的文件缓冲区思路类似。3. 递归下降语法分析把token流组装成AST的优先级游戏3.1 文法怎么定边界先支持表达式还是先支持语句写parser之前先把你要支持的C子集画出一条边界。我的建议是第一版只支持int类型变量声明、算术表达式、赋值、if/else、while、return、函数定义与调用。其他像for、struct、指针运算、多维数组、枚举全部留到第二版。为什么这么定因为一个递归下降parser的复杂度和文法规模是指数关系的每多一个语法特性意味着parse函数里多几层嵌套、多几处前瞻分支调试成本翻倍。我见过太多人第一天想支持全部C11结果写了一个星期连声明和表达式都分不清。先跑通最小集再逐步往里面加特性这个节奏是编译器开发里最经典的增量路线GCC本身也是从支持KR C的极小子集起步的。3.2 表达式优先级解析函数嵌套就是最好的优先级表表达式解析是递归下降里最容易翻车的地方。反过来只要理解了“优先级越高parse函数调用越深”这个原则整张优先级表就不需要记。乘除一级、加减一级、关系比较一级、相等比较一级、逻辑与、逻辑或每一层套一层函数就行。def parse_multiplicative(self): left self.parse_unary() while self.peek().value in (*, /, %): op self.next().value right self.parse_unary() left (op, left, right) return left这段代码处理优先级最高的乘除取余。逻辑很直白先解析一个一元表达式作为左操作数然后只要遇到*、/、%就继续吞掉一个操作数并合成新的二元节点。因为parse_multiplicative内部调的是parse_unary而parse_unary不会递归调回parse_multiplicative所以乘除天然优先于加减——你只要让加减的parse函数调乘除的parse函数就行。def parse_additive(self): left self.parse_multiplicative() while self.peek().value in (, -): op self.next().value right self.parse_multiplicative() left (op, left, right) return left这里的关键是while循环而不是递归。很多人第一反应是把优先级写成expr :: expr OP term的递归这在递归下降里是死路——左递归会无限调用parse_expr自身直到栈爆。改成循环后所有同一优先级的运算符都在一个循环里消化掉既不会栈溢出又天然实现了左结合。这也就是“递归下降parse表达式用循环代替左递归”这句口诀的来源。3.3 语句与控制流if、while、return的解析骨架语句层和表达式层的分界在于语句里可以有声明可以改变控制流可以没有值。以if/else为例解析骨架是def parse_stmt(self): tok self.peek() if tok.value if: self.next() self.expect(() cond self.parse_expr() self.expect()) then_branch self.parse_stmt() else_branch None if self.peek().value else: self.next() else_branch self.parse_stmt() return (if, cond, then_branch, else_branch) if tok.value while: self.next() self.expect(() cond self.parse_expr() self.expect()) body self.parse_stmt() return (while, cond, body) if tok.value return: self.next() expr self.parse_expr() self.expect(;) return (return, expr) if tok.value {: self.next() stmts [] while self.peek().value ! }: stmts.append(self.parse_stmt()) self.expect(}) return (block, stmts) # 声明和表达式语句的区分 if self.peek().type KEYWORD and \ self.peek().value in (int, char, void): type_name self.next().value name self.next() self.expect(;) return (decl, type_name, name.value) expr self.parse_expr() self.expect(;) return (expr_stmt, expr)要注意两个细节。第一个是else的悬挂问题if (a) if (b) c; else d;这个else到底属于哪个if递归下降里else默认绑定最近的if因为parse_stmt处理内层if时已经看到了else并消费掉了。这是C语言的标准行为不用额外处理。第二个是声明和表达式的区分靠的是当前位置token是不是int/char关键字。这里做的简化是只支持int name;不带初始化的形式带初始化int a 42;需要继续向后看有没有有的话再parse_expr。3.4 函数定义与调用把parse_stmt包进去的最后一层函数定义的解析是整个parser的收口。parse_program不断调用parse_function遇到EOF才停def parse_function(self): type_tok self.next() # int / char / void name_tok self.next() # 函数名 self.expect(() params [] while self.peek().value ! ): p_type self.next().value p_name self.next().value params.append((p_type, p_name)) if self.peek().value ,: self.next() self.expect()) self.expect({) body [] while self.peek().value ! }: body.append(self.parse_stmt()) self.expect(}) return (func, type_tok.value, name_tok.value, params, body)函数调用在表达式层已经被parse_primary处理了那一边的逻辑是解析到标识符后下一个token是(就进入函数调用节点继续解析参数列表。函数定义和函数调用是两条独立的路径前者属于语句层后者属于表达式层不要混在一起。最难定位的bug往往是这两个词法上长得像的结构在AST里放错了层。4. 语义分析与代码生成从AST到三地址码的落地4.1 符号表与作用域变量类型从哪里查parse阶段只负责“这句话语法对不对”不负责“这个变量有没有声明、类型是不是一致”。后者是语义分析的事。语义分析的第一块地基是符号表——一张维护“变量名到类型”映射的表格并且要处理作用域嵌套。C语言里内层作用域可以遮蔽外层同名变量这个用一棵作用域链来实现class Scope: def __init__(self, parentNone): self.types {} self.parent parent def declare(self, name, type_): if name in self.types: raise NameError(f{name} 重复声明) self.types[name] type_ def lookup(self, name): if name in self.types: return self.types[name] if self.parent: return self.parent.lookup(name) return None这段代码的逻辑很朴素每个Scope只记录自己这一层的变量查找时先看自己再看父作用域一直找到顶层。进入一个{代码块时new一个子Scope退出时整个丢弃这就天然实现了变量的作用域生命周期。符号表的实现要诀是“声明时检查重复使用时检查存在”两个检查一个都不能少。注意declare里抛出的NameError不是C编译器该有的行为——真正合理的做法是把重复声明的错误信息收集起来一次性报告给用户而不是遇到第一个错误就停。常见做法是在Scope类外面维护一个error列表语义分析器不断往里追加错误最后统一输出。4.2 类型检查int、char、指针混用的判定规则类型检查要回答的核心问题是这个表达式的类型是什么赋值两侧的类型兼容不兼容。C的类型系统本身很庞杂但对一个C子集来说规则可以收敛成几条算术运算的两个操作数必须是int或charchar隐式提升为int赋值时左侧类型和右侧类型必须一致或者右侧是char而左侧是int隐式提升return的类型必须和函数声明的返回类型一致比较运算的操作数类型没有要求但两侧应该都是同一种基本类型。def infer_type(node, scope): op node[0] if op num: return int if op char: return char if op var: t scope.lookup(node[1]) if t is None: raise NameError(f未声明变量 {node[1]}) return t if op : left infer_type(node[1], scope) right infer_type(node[2], scope) if left ! int or right ! int: raise TypeError(算术运算需要int类型操作数) return int if op : left_t infer_type(node[1], scope) right_t infer_type(node[2], scope) if left_t int and right_t char: return int if left_t ! right_t: raise TypeError(f类型不匹配: {left_t} vs {right_t}) return left_t return void这个infer_type函数的骨架最容易扩展。你之后加了指针类型只需在var分支里判断名字是否以*开头或者干脆在符号表里记录(ptr, int)这样的复合类型。我一般建议类型用元组而不是字符串因为元组能表达复合结构——(ptr, int)解引用一次就是int这比硬编码一个ptr_int字符串靠谱得多。4.3 三地址码生成把AST变成线性指令序列语义分析通过后就到了输出环节。如果你做的是教学或者分析工具生成三地址码是性价比最高的选择它是线性的、接近汇编但比汇编可读、可以直接在Python环境里解释执行。常见的做法是遍历AST为每个子表达式分配一个临时变量把运算摊平成一条条指令。class CodeGen: def __init__(self): self.instrs [] self.temp_count 0 def new_temp(self): name ft{self.temp_count} self.temp_count 1 return name def gen(self, node, scope): op node[0] if op num: return str(node[1]) if op var: return node[1] if op in (, -, *, /): left self.gen(node[1], scope) right self.gen(node[2], scope) t self.new_temp() self.instrs.append(f{t} {left} {op} {right}) return t if op if: cond self.gen(node[1], scope) label_else fL_else_{self.temp_count} label_end fL_end_{self.temp_count} self.instrs.append(fif {cond} 0 goto {label_else}) child_scope Scope(scope) self.gen(node[2], child_scope) self.instrs.append(fgoto {label_end}) self.instrs.append(f{label_else}:) if node[3]: child_scope Scope(scope) self.gen(node[3], child_scope) self.instrs.append(f{label_end}:) return None return None三地址码的设计要点是每个二元运算产生一个新临时变量控制流用label和goto表达作用域用Scope链挂着。这段代码和上文的infer_type实际上可以合并到一次遍历里完成一边推断类型一边生成指令——但第一次写建议分开先跑通类型检查再跑通代码生成两个阶段混在一起出了bug你分不清是哪一边的。编译器优化这个阶段先不要碰。把正确的三地址码跑通再去想常量折叠、公共子表达式消除这些事。一上来就在AST上做优化等于地基没打牢先装修翻车是迟早的事。5. 自写C编译器最常见的五个坑现象、原因、修法5.1 现象parse表达式时直接RecursionErrorPython栈爆了原因文法写成了左递归。比如expr :: expr term这种教科书式文法直接照搬进递归下降parse_expr第一行就调parse_expr循环调用直到RecursionError。递归下降parser只能处理右递归处理不了左递归。解决把同一优先级的运算改成while循环左操作数先解析然后循环吞运算符和右操作数。这就是前面代码里parse_additive和parse_multiplicative写成while的原因。遇到栈溢出时先查根因是不是左递归不要盲目去调sys.setrecursionlimit——那是止疼药不是治病。5.2 现象语法分析结果整体错位所有token往后偏了一位原因超前读了一个token没有放回。peek方法只能看不取next方法取走并前进。很多人在写参数列表或者判断声明/表达式时为了看一眼再决定走哪个分支调了next但没有在分支处理中消费这个token导致后续解析整体错位。解决定一个铁规矩peek只用于判断分支next拿到的东西必须被处理如果确实需要放下一个token在设计时用变量缓存而不是把pos往回退。回退pos做前瞻在大语法里有它合理的地方但Python写的递归下降里回退的位置管理一旦出错报错信息会指向完全错误的行号排查成本极高。我习惯把所有需要前瞻超过两个token的场景都拆成子函数处理。5.3 现象C的int溢出行为在Python里消失了原因Python的整数没有溢出概念2147483647 1直接算出2147483648而C语言里int溢出是未定义行为——至少在常见的x86平台上结果是-2147483648。用Python写的编译器如果在语义检查时不拦这个生成的三地址码在Python里解释执行时会给出和你期望完全不同的数学结果。解决在infer_type检查到整型字面量时主动检查是否超出[-2^31, 2^31-1]范围。做两个方案要么报warning把字面量截断成int32要么按C标准把它升级成long long处理。最省事的是前者——直接按32位截断同时打印警告。这算是在一个“用Python模拟C语义”的项目里绕不开的取舍。5.4 现象字符字面量a和字符串字面量a在后续代码里被混用原因词法分析器偷懒把CHAR和STRING都处理成字符串类型只存了值没存类型。到了类型检查阶段传给需要int参数的函数时都过关了但C语言里a是int而a是char数组——语义完全不同。更隐蔽的坑是转义\n是单个字符\n是包含换行符和结尾\0的两个字符数组。解决词法层就分开Token类型用CHAR和STRING两个枚举值。类型推断时CHAR可以直接隐式提升为int参与算术STRING只有遇到数组参数或者赋值给指针才能接受。这个坑埋得越深越难挖第一天在tokenizer里多写两行后面省十个小时。5.5 现象合法C代码测试全绿一给非法输入整个编译器崩得四散原因测试集只写了合法输入。parser报错逻辑不完整遇到非法token时直接IndexError连“这里语法错误”这种提示都出不来。解决在parse的入口统一包一层异常处理捕获SyntaxError并打印精确位置测试文件里强行放十几个非法片段——缺分号、括号不匹配、多一个逗号、声明没有类型——保证每个都能给出友好的报错而不是栈回溯。这算是我做编译器开发以来最大的一个习惯非法输入的测试和合法输入的测试一样重要它决定了你的工具是被别人信赖还是被扔在角落。6. 用断言测试和可视化AST给编译器上保险写编译器最怕的不是功能少是改了A坏了B还没有感知。我自己的习惯是每加一个语法特性先把对应的合法/非法测试用例写好跑一遍确认当前是绿的再动手改代码。import pprint from tokenizer import tokenize from parser import Parser def parse_c_source(src): parser Parser(tokenize(src)) return parser.parse_function() def test_simple_add(): ast parse_c_source(int add(int a, int b) { return a b; }) assert ast[0] func assert ast[1] int assert ast[2] add pprint.pprint(ast) # 肉眼检查AST结构 def test_invalid_missing_semicolon(): try: parse_c_source(int a 3 return a;) assert False, 应该报语法错误 except SyntaxError as e: assert 行 in str(e) or line in str(e).lower() if __name__ __main__: test_simple_add() test_invalid_missing_semicolon() print(全部测试通过)测试骨架逻辑很简单合法代码测结构非法代码测报错。加上pprint把AST打出来你第一次看到嵌套元组展开在终端里的时候整个编译器的心跳就摸到了。如果测试驱动开发不适合你至少做到“改一行代码就重跑一遍全部用例”。我自己早期在这上面翻过车改了符号表查找策略结果函数参数全部变成未声明变量整个测试红了一屏原因只是作用域链的parent指针传错了。还有一次为了支持for循环改了语句分发逻辑结果所有while循环被解析成函数调用——当时是半夜两点看一眼AST输出才发现问题出在peek判断条件写反了。GCC和Clang能用几十年不出幺蛾子靠的是海量测试和严格的回归机制你写的这个迷你编译器至少要把“每个新增用例必须过、每个旧用例不许倒”这层底线守住。玩了一轮下来你会发现真正值钱的不一定是那个能跑通的C子集编译器而是你脑子里建立的这条链路源码到token、token到AST、AST到语义、语义到指令。以后再遇到任何语言工具链的怪问题你都能顺着这条链路定位到具体环节了。希望帮到你。本文还有配套的精品资源点击获取