简介这是一份用Python语言实现的C语言编译器项目面向学习编译原理、希望动手实践编译器开发的学生与开发者。它采用LL1文法完成语法分析并借助C语言空语句巧妙化解左递归问题完整覆盖词法分析、语法分析、语义分析与代码生成等核心阶段是理解编译器工作流程的优质实例。压缩包共21个文件约42KB以8个py源码文件为主辅以5个txt文法与字符串说明、5个pyc缓存、1个asm汇编输出、1个c源文件及1份docx文档结构紧凑、模块划分清晰。目前已有277人学习下载。读者可从中获得完整的文法规则、各组件实现脚本与汇编生成结果对照源码理解LL1解析表的构建与使用掌握左递归消除思路并借助测试字符串与文法文档进行验证调试从而在提升Python编程能力的同时建立对编译技术的系统认知。1. 用 Python 写一个 C 语言编译器从词法到 LL(1) 语法分析的最小闭环很多人第一次听到「用 Python 写 C 语言编译器」第一反应是「这不是自虐吗」。但如果你把目标从「替代 GCC」降到「跑通一个 C 语言子集的编译流程」事情就完全不一样了词法分析、LL(1) 语法分析、语义检查、三地址码生成每一步都能用 Python 在几百行内讲清楚。它解决的不是工程效率问题而是让你真正看懂编译器内部那套「黑匣子」——为什么a b和a b结果不同为什么int main缺失时链接器才报错为什么语法分析器能在一堆 token 里精准定位到缺失的分号。这篇文章面向的是想动手写编译器、准备编译原理课设、或者想用 Python 快速验证语法规则的人。下面按「先立理论、再动手、最后避坑」的顺序把这条链路完整走一遍。2. 词法分析器把 C 源码切成 token 流2.1 为什么先做词法而不是直接上语法编译器前端的第一步永远是词法分析Lexer。它的任务很单纯把一串字符流变成有类型的 token 流比如int变成关键字、main变成标识符、(变成界符。很多人急着写语法分析结果在语法阶段还要处理「这个字符是不是数字的一部分」逻辑全糊在一起。先把词法独立出来后面 LL(1) 分析器拿到的就是干净的 token 序列调试成本会低一个量级。C 语言子集的 token 类型一般分五类关键字int、if、while、return等、标识符、常量整数、字符、字符串、运算符、、、-等、界符(、)、{、}、;、,。这里有个容易翻车的点和必须用最长匹配原则否则a会被切成两个后面语法分析直接崩。2.2 用 Python 正则做最长匹配的 tokenizer下面是一个可运行的最小词法分析器核心思路是按优先级依次尝试匹配关键字和标识符用同一套正则但查表区分。import re # token 规格顺序即优先级最长匹配靠正则的贪婪特性 TOKEN_SPEC [ (KEYWORD, r\b(int|char|void|if|else|while|for|return|break|continue)\b), (IDENT, r\b[a-zA-Z_]\w*\b), (NUMBER, r\b\d\b), (STRING, r(?:[^\\]|\\.)*), (CHAR, r(?:[^\\]|\\.)), (OP, r\\|--||!||||\|\||[-*/%!|^~]), (DELIM, r[(){}\[\];,]), (SKIP, r[ \t\n\r]), (MISMATCH, r.), ] # 把规格编译成一个大正则命名组方便取类型 MASTER_RE re.compile(|.join(f(?P{name}{pat}) for name, pat in TOKEN_SPEC)) def tokenize(code): tokens [] line 1 for mo in MASTER_RE.finditer(code): kind mo.lastgroup value mo.group() if kind SKIP: line value.count(\n) continue if kind MISMATCH: raise SyntaxError(f第 {line} 行出现非法字符: {value!r}) tokens.append((kind, value, line)) return tokens if __name__ __main__: src int main() { int a 1; a; return a; } for t in tokenize(src): print(t)这段代码的逻辑说明TOKEN_SPEC的顺序就是匹配优先级KEYWORD放在IDENT前面保证int不会被当成普通标识符。MASTER_RE用命名组把每个 token 类型绑上名字finditer从左到右扫描天然实现最长匹配。SKIP负责吃掉空白和换行同时维护行号方便后面报错定位。MISMATCH是兜底遇到无法识别的字符直接抛异常而不是静默跳过——这是血泪经验静默跳过会让后面的语法错误变得极难排查。参数方面line的维护只在SKIP分支做因为只有空白里才可能包含换行如果你把注释也加进来记得在注释分支同样累加行号。NUMBER这里只支持十进制整数要支持十六进制就改成r\b(0[xX][0-9a-fA-F]|\d)\b。CHAR和STRING的正则用了非捕获组和转义处理能覆盖\n、a\b这类情况。2.3 词法阶段的三个必查项写完 tokenizer 后别急着往下走先做三件事验证。第一用ab测试正确结果应该是a、、、b如果切成a、、、b说明最长匹配没生效。第二用int _x1 0x1F;测试确认标识符能带数字、十六进制常量能被识别。第三故意写一个字符确认报错信息里带行号。这三项过了词法层基本就稳了。3. LL(1) 语法分析从文法到预测分析表3.1 为什么选 LL(1) 而不是 LR编译器开发里语法分析有两大流派自顶向下的 LL 和自底向上的 LR。LR 能处理的文法更多工业级编译器比如 GCC、Clang基本都用 LR 系。但 LL(1) 的优势在于直观你只需要看一个 token 就能决定用哪条产生式预测分析表的构造过程完全透明非常适合教学和快速原型。代价是文法必须消除左递归、提取左公因子C 语言的表达式文法天然左递归需要手动改写。常见做法是先把 C 子集文法写成 BNF然后做两步变换。以表达式为例原始文法E - E T | T是左递归的改写成E - T E、E - T E | ε。这一步不做LL(1) 分析器会直接死循环。3.2 计算 FIRST 集和 FOLLOW 集预测分析表的每一行是一个非终结符每一列是一个终结符token 类型单元格里放产生式。填表依据就是 FIRST 和 FOLLOW 集。FIRST(A) 是 A 能推导出的所有串的首终结符集合FOLLOW(A) 是 A 后面可能紧跟的终结符集合。规则不复杂但手工算容易漏建议直接写代码算。# 文法用字典表示key 是非终结符value 是产生式列表每条是符号列表 grammar { E: [[T, E]], E: [[, T, E], [ε]], T: [[F, T]], T: [[*, F, T], [ε]], F: [[(, E, )], [id]], } start_symbol E def first_of_sequence(seq, first_sets): 计算一个符号序列的 FIRST 集 result set() for sym in seq: if sym not in grammar: # 终结符 result.add(sym) return result result | (first_sets[sym] - {ε}) if ε not in first_sets[sym]: return result result.add(ε) return result def compute_first(grammar): first {nt: set() for nt in grammar} changed True while changed: changed False for nt, prods in grammar.items(): for prod in prods: before len(first[nt]) first[nt] | first_of_sequence(prod, first) if len(first[nt]) ! before: changed True return first def compute_follow(grammar, first, start): follow {nt: set() for nt in grammar} follow[start].add($) # $ 表示输入结束 changed True while changed: changed False for nt, prods in grammar.items(): for prod in prods: for i, sym in enumerate(prod): if sym not in grammar: continue rest prod[i1:] first_rest first_of_sequence(rest, first) before len(follow[sym]) follow[sym] | (first_rest - {ε}) if ε in first_rest or not rest: follow[sym] | follow[nt] if len(follow[sym]) ! before: changed True return follow first_sets compute_first(grammar) follow_sets compute_follow(grammar, first_sets, start_symbol) print(FIRST:, first_sets) print(FOLLOW:, follow_sets)逻辑说明first_of_sequence处理的是「一个符号序列的 FIRST」遇到终结符直接加入并返回遇到非终结符先并入它的 FIRST 去掉 ε如果该非终结符不能推出 ε 就停止否则继续看下一个符号。compute_first用不动点迭代直到所有集合不再变化。compute_follow对每条产生式的每个非终结符看它后面的符号串的 FIRST如果后面能推出 ε 或者是末尾就把左部的 FOLLOW 并进来。参数说明grammar里用ε表示空产生式用字符串表示终结符非终结符就是字典的 key。start_symbol是文法开始符号它的 FOLLOW 里要手动加$。这套代码对任何 LL(1) 文法都通用换成 C 子集的完整文法也能直接跑。3.3 构造预测分析表并驱动分析有了 FIRST 和 FOLLOW填表规则是对每条产生式A - α对 FIRST(α) 里每个终结符 a把A - α填进M[A][a]如果 ε 在 FIRST(α) 里对 FOLLOW(A) 里每个 b把A - α填进M[A][b]。填完如果某个格子有冲突说明文法不是 LL(1)需要继续改写。分析驱动用一个栈初始压入$和开始符号然后循环读 token。栈顶是非终结符就查表展开是终结符就和当前 token 匹配匹配成功就弹栈并前进。遇到$和栈顶$同时出现就接受。这套流程是所有 LL(1) 分析器的标准骨架Python 实现不超过 60 行。提示预测分析表里如果出现同一个格子被填了两次不要试图用「优先级」硬压那说明文法本身有左公因子没提取干净回到文法层面改。4. 语义检查与三地址码生成让编译器真正「懂」程序4.1 符号表变量作用域和类型检查的底座语法分析只保证结构合法int a; a hello;在语法上完全正确但语义上必须报错。符号表就是干这个的。C 语言的作用域是块级的{ }一进一出就要压栈和弹栈。常见做法是用一个栈式符号表每进入一个块压入一个新作用域离开时弹出查找变量时从栈顶往下找。符号表里每个条目至少存名字、类型、是否是数组、作用域层级。类型检查的核心是赋值兼容性——int可以赋给intchar可以隐式转int但int*不能赋给int。这些规则写成一个compatible(lhs_type, rhs_type)函数在遍历 AST 时调用。4.2 三地址码从 AST 到中间表示三地址码TAC是编译器后端最常见的中间表示每条指令最多一个运算符形式像t1 a b。从 AST 生成 TAC 用后序遍历先递归处理左右子树拿到操作数再生成一条新指令返回临时变量名。下面是一个针对表达式和赋值语句的 TAC 生成器片段。class TACGen: def __init__(self): self.temp_count 0 self.code [] def new_temp(self): self.temp_count 1 return ft{self.temp_count} def gen_expr(self, node): node 是 (binop, op, left, right) 或 (num, v) 或 (id, name) if node[0] num: return str(node[1]) if node[0] id: return node[1] if node[0] binop: left self.gen_expr(node[2]) right self.gen_expr(node[3]) tmp self.new_temp() self.code.append(f{tmp} {left} {node[1]} {right}) return tmp raise ValueError(f未知节点: {node}) def gen_assign(self, name, expr_node): val self.gen_expr(expr_node) self.code.append(f{name} {val}) # 示例a b c * d gen TACGen() gen.gen_assign(a, (binop, , (id, b), (binop, *, (id, c), (id, d)))) print(\n.join(gen.code))逻辑说明gen_expr对二元运算先递归求左右操作数再申请临时变量生成一条三地址指令返回临时变量名供上层使用。gen_assign先算表达式值再生成赋值指令。对a b c * d输出会是t1 c * d、t2 b t1、a t2顺序天然满足运算优先级。参数说明temp_count是临时变量计数器保证名字唯一code列表按生成顺序存指令后面可以直接遍历输出或做优化。如果要支持和--需要在gen_expr里加分支注意前置和后置的求值时机不同——前置先自增再取值后置先取值再自增这正是a b和a b结果不同的根源。4.3 控制流的 TAC 生成if 和 while 的回填表达式和赋值只是热身真正让编译器「活」起来的是控制流。if和while的 TAC 需要用到回填backpatching生成跳转指令时目标地址还不知道先留空等目标确定再填回去。常见做法是维护一个「待回填列表」每个元素记录指令索引和目标标签。以while (a b) { s }为例生成顺序是先放循环开始标签 L1生成条件a b的 TAC生成if t1 0 goto L2生成循环体 s 的 TAC生成goto L1最后放 L2 标签。if语句类似只是没有回跳。这块逻辑不复杂但标签管理容易乱建议用一个new_label()统一发号。5. 避坑与排查编译器开发中最容易翻车的 5 个点5.1 现象ab被切成a、、、b原因词法分析器没有严格按最长匹配原则正则顺序或匹配策略有问题。解决确保在之前尝试匹配用finditer配合优先级有序的正则列表不要用多个独立re.match逐个试。5.2 现象LL(1) 分析器遇到if语句就死循环原因文法里存在左递归或左公因子没提取。C 语言的if-else有经典的悬挂 else 问题stmt - if (expr) stmt | if (expr) stmt else stmt不是 LL(1) 文法。解决改写文法用stmt - if (expr) stmt else_part、else_part - else stmt | ε把选择推迟到看到else再决定。5.3 现象符号表查不到变量但代码里明明定义了原因作用域压栈和弹栈不匹配常见于for循环的初始化变量在循环外被引用或者块作用域退出时弹多了。解决在每个{和}的处理分支里严格配对压栈弹栈调试时打印符号表栈的深度和内容一眼就能看出哪层丢了。5.4 现象三地址码里临时变量名冲突原因多个TACGen实例各自从t1开始编号合并代码时撞名。解决把临时变量计数器做成全局的或者加前缀区分函数/作用域。更稳妥的做法是用一个TempFactory单例统一发号。5.5 现象报错信息只有「语法错误」不知道哪一行原因token 里没带行号或者语法分析器捕获异常时把位置信息丢了。解决词法阶段每个 token 都带行号语法分析器在匹配失败时把当前 token 的行号和值一起抛出来。这是后悔药早加早省心。6. 进阶技巧用 Python 的ast模块反向验证你的编译器写到这一步你已经有了一个能跑通 C 子集的编译器前端。但怎么确认它真的对一个很实用的技巧是「交叉验证」把同一段 C 代码用你的编译器生成 TAC再用 Python 的ast模块解析等价的 Python 表达式对比运算顺序和结果。比如a b c * d你的 TAC 应该先算c * dPython 的ast.dump也会显示Mult节点在Add下面结构一致就说明优先级处理对了。另一个进阶方向是加一个简单的常量折叠优化在 TAC 生成阶段如果左右操作数都是常量直接算出结果不生成指令。这能让你直观看到「编译器优化」到底在做什么。实现上就是在gen_expr的binop分支里加一个判断两边都是num节点就直接返回计算结果字符串。def gen_expr(self, node): if node[0] num: return str(node[1]) if node[0] binop: left self.gen_expr(node[2]) right self.gen_expr(node[3]) # 常量折叠两边都是数字就直接算 if left.lstrip(-).isdigit() and right.lstrip(-).isdigit(): return str(eval(f{left} {node[1]} {right})) tmp self.new_temp() self.code.append(f{tmp} {left} {node[1]} {right}) return tmp这段改动很小但效果立竿见影a 2 3 * 4会直接生成a 14而不是三条指令。参数上注意eval只用于演示生产环境要自己写运算函数避免注入风险。常量折叠是编译器优化的入门砖做完这个再去看死代码消除、公共子表达式消除思路会顺很多。我自己写第一个编译器时最大的教训是「别急着写代码先把文法在纸上推三遍」。当时跳过 FIRST/FOLLOW 手工验算直接写分析器结果预测表冲突查了两天才发现是左递归没消干净。后来养成的习惯是任何文法改动先用小脚本算一遍 FIRST 和 FOLLOW确认无冲突再写分析逻辑。这个习惯帮我省下了大量调试时间。希望帮到你。本文还有配套的精品资源点击获取