简介这份资源是北京交通大学编译原理课程实验项目的完整源码集合面向计算机科学与技术专业学生及需要系统练习编译器前端开发的开发者。内容覆盖词法分析、递归下降语法分析、LL(1)文法分析、算符优先文法分析、基于SLR(1)分析法的语法制导翻译以及中间代码生成六个核心实验模块从字符序列到记号流、抽象语法树、语法检查直至语义动作触发与中间代码输出构成一条完整的编译前端技术链路。压缩包共94个文件以33个cpp源文件与29个头文件为主体辅以21个txt测试用例与文法文件、6个makefile构建脚本及少量c文件整体约66KB按Lab01至Lab06分目录组织结构清晰便于逐模块对照学习。目前已有92人学习。读者可借助现成源码与测试数据快速搭建实验环境理解各分析方法的实现细节与衔接关系适合作为课程实验参考、期末复习或编译器入门练手材料。1. 编译原理课程实验六个模块从词法分析到中间代码生成的完整落地路径很多同学学完编译原理的理论课考试能拿高分但一上手写词法分析器就卡在正则表达式到 NFA 的转换上更别提后面还有递归下降、LL(1)、算符优先、SLR(1) 和语法制导翻译五座大山。北京交通大学这套编译原理课程实验项目把六个核心模块串成了一条完整的编译器前端实现链路从字符流输入一路走到中间代码输出。它解决的不是“考试怎么考”的问题而是“给你一段类 C 语言的源代码你怎么让机器真正理解它并生成可执行的中间表示”。适合正在做编译原理课程设计的学生、想系统补齐编译器前端实现能力的后端工程师以及需要快速搭建 DSL 解析器的开发者。六个模块分别是词法分析、递归下降语法分析、LL(1) 文法分析、算符优先文法分析、基于 SLR(1) 分析法的语法制导翻译、中间代码生成。每个模块独立可运行又层层递进构成完整前端。2. 词法分析器从正则表达式到 DFA 的最小实现路径词法分析是整个编译器的入口任务是把源代码字符流切分成有意义的 Token 序列。很多教程一上来就讲自动机理论但真正动手写的时候你需要的是一条从正则表达式到确定有限自动机DFA的工程化路径。常见做法是先用正则表达式描述每种 Token 的模式再手工构造或程序生成 DFA最后用状态转移表驱动扫描器。2.1 正则表达式到 NFA 再到 DFA 的转换逻辑词法分析的核心是识别标识符、关键字、数字常量、运算符和界符。以标识符为例正则表达式是[a-zA-Z_][a-zA-Z0-9_]*对应的 NFA 有两个状态起始状态接受字母或下划线后进入接受状态接受状态可以循环接受字母、数字或下划线。关键字是标识符的特例通常在识别出标识符后查关键字表来区分。从 NFA 到 DFA 用子集构造法每个 DFA 状态是 NFA 状态的集合初始状态是 NFA 起始状态的 ε-闭包对每个输入符号计算转移后的 ε-闭包直到没有新状态产生。DFA 最小化用 Hopcroft 算法或简单的分割法把等价状态合并。实际工程中如果 Token 种类不多二三十种手工构造 DFA 状态转移表反而比程序生成更可控。下面是一个用 Python 实现的简化词法分析器核心代码采用状态转移表驱动# 词法分析器核心状态转移表驱动 # 状态定义0起始, 1标识符/关键字, 2数字, 3运算符, 4界符, 5接受 TRANSITION { (0, letter): 1, (0, digit): 2, (0, op): 3, (0, delim): 4, (1, letter): 1, (1, digit): 1, (1, other): 5, (2, digit): 2, (2, dot): 2, (2, other): 5, (3, op): 5, (4, delim): 5, } KEYWORDS {if, else, while, for, int, float, return} def classify(ch): if ch.isalpha() or ch _: return letter if ch.isdigit(): return digit if ch in -*/!|: return op if ch in (){}[];,: return delim return other def tokenize(source): tokens, i, state [], 0, 0 buf while i len(source): ch source[i] cls classify(ch) key (state, cls) if key in TRANSITION: state TRANSITION[key] buf ch i 1 else: if buf: tokens.append((ID if buf not in KEYWORDS else KW, buf)) buf state 0 if ch.isspace(): i 1 else: # 无法识别的字符报错 raise SyntaxError(f非法字符 {ch} 在位置 {i}) if buf: tokens.append((ID if buf not in KEYWORDS else KW, buf)) return tokens这段代码的逻辑说明TRANSITION字典定义了状态转移规则键是(当前状态, 字符类别)值是目标状态。classify函数把字符映射到类别。主循环中如果当前状态和字符类别有转移规则就更新状态并累积字符否则说明当前 Token 结束把缓冲区内容作为 Token 输出然后重置状态。参数方面KEYWORDS集合需要根据目标语言的关键字表调整TRANSITION表在 Token 种类增加时需要同步扩展。注意数字识别中dot的处理是为了支持浮点数但需要额外状态来区分1.和1.5以及.5的合法性。2.2 词法分析器的参数配置与测试方法词法分析器的关键参数有三个最大标识符长度、数字常量的进制支持、注释处理策略。最大标识符长度影响缓冲区大小一般设为 256 足够数字常量要决定是否支持十六进制0x前缀和科学计数法e指数注释处理有两种策略——在词法阶段直接跳过或者作为特殊 Token 返回给语法分析器。常见做法是词法阶段跳过单行注释//和块注释/* */但块注释的嵌套处理容易翻车建议不支持嵌套。测试词法分析器时构造覆盖所有 Token 类型的输入文件逐行检查输出 Token 序列。重点验证边界情况标识符后紧跟运算符ab应输出ID(a), OP(), ID(b)、数字后紧跟字母123abc应报错或拆分为NUM(123), ID(abc)、字符串中的转义字符处理。我一般会写一个test_lexer.py用assert断言预期 Token 序列跑一遍就能发现大部分问题。3. 递归下降与 LL(1)两种自顶向下语法分析的工程取舍语法分析是编译器的核心任务是根据文法规则把 Token 序列组织成语法树。递归下降和 LL(1) 都是自顶向下方法但工程实现差异很大。递归下降用手写递归函数模拟推导过程灵活但代码量大LL(1) 用预测分析表驱动自动化程度高但对文法要求苛刻。这一章把两种方法放在一起讲是因为它们共享 FIRST 集和 FOLLOW 集的计算逻辑而且实际项目中经常先用 LL(1) 验证文法再用递归下降处理需要语义动作的场景。3.1 递归下降分析器的函数骨架与回溯处理递归下降的核心思想是为每个非终结符写一个函数函数内部根据当前 Token 决定展开哪个产生式。如果产生式有多个候选需要计算 FIRST 集来决定选择当 FIRST 集有交集时需要提取左公因子或做回溯。回溯的实现方式是记录当前 Token 位置尝试一个产生式失败后恢复到该位置再试下一个。下面是一个递归下降分析器的骨架代码处理简单的表达式文法# 递归下降分析器骨架 # 文法E - T E, E - T E | ε, T - F T, T - *F T | ε, F - (E) | id 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 match(self, expected_type): tok self.peek() if tok[0] expected_type: self.pos 1 return tok raise SyntaxError(f期望 {expected_type}实际 {tok}) def parse_E(self): self.parse_T() self.parse_E_prime() def parse_E_prime(self): if self.peek()[0] OP and self.peek()[1] : self.match(OP) self.parse_T() self.parse_E_prime() # ε 产生式什么都不做 def parse_T(self): self.parse_F() self.parse_T_prime() def parse_T_prime(self): if self.peek()[0] OP and self.peek()[1] *: self.match(OP) self.parse_F() self.parse_T_prime() def parse_F(self): tok self.peek() if tok[0] ID: self.match(ID) elif tok[0] DELIM and tok[1] (: self.match(DELIM) self.parse_E() self.match(DELIM) # 期望 ) else: raise SyntaxError(fF 无法匹配 {tok})逻辑说明每个非终结符对应一个parse_X方法。peek返回当前 Token 但不移动位置match检查并消费 Token。E和T的处理体现了消除左递归后的文法结构——当遇到或*时进入递归否则走 ε 产生式直接返回。参数方面tokens是词法分析器的输出列表每个元素是(类型, 值)元组。注意match中的expected_type只检查类型如果需要精确匹配运算符值要额外判断tok[1]。3.2 LL(1) 预测分析表的构造与驱动LL(1) 分析器用一张二维表M[非终结符][终结符] 产生式来驱动。构造这张表需要先计算 FIRST 集和 FOLLOW 集。FIRST(A) 是 A 能推导出的所有串的首终结符集合FOLLOW(A) 是 A 后面可能紧跟的终结符集合。对于产生式A - α如果a在 FIRST(α) 中则M[A][a] A - α如果 α 能推导出 ε 且a在 FOLLOW(A) 中则M[A][a] A - α。构造 FIRST 集的算法对于终结符FIRST(a) {a}对于非终结符 A扫描所有产生式A - X1X2...Xn把 FIRST(X1) 中非 ε 的符号加入 FIRST(A)如果 X1 能推导 ε 则继续看 X2以此类推。FOLLOW 集的计算起始符号的 FOLLOW 包含$对于产生式A - αBβ把 FIRST(β) 中非 ε 的符号加入 FOLLOW(B)如果 β 能推导 ε 或 β 为空把 FOLLOW(A) 加入 FOLLOW(B)。LL(1) 分析表驱动的核心代码# LL(1) 分析表驱动 def ll1_parse(table, start_symbol, tokens): stack [$, start_symbol] tokens tokens [(EOF, $)] pos 0 while stack: top stack.pop() cur tokens[pos] if top cur[0] or top cur[1]: pos 1 elif top in table and cur[0] in table[top]: production table[top][cur[0]] # production 是产生式右部列表逆序入栈 for sym in reversed(production): if sym ! ε: stack.append(sym) else: raise SyntaxError(fLL(1) 分析失败栈顶 {top}当前 {cur}) return True逻辑说明栈初始化为[$, 起始符号]每次取栈顶和当前 Token。如果栈顶是终结符且匹配当前 Token消费 Token如果栈顶是非终结符且表中有对应产生式把产生式右部逆序入栈。参数方面table是嵌套字典{非终结符: {终结符: 产生式右部列表}}start_symbol是文法起始符号。注意产生式右部中的 ε 不入栈因为 ε 表示空串。3.3 递归下降与 LL(1) 的选型对比对比维度递归下降LL(1)实现方式手写递归函数预测分析表驱动文法限制可处理部分非 LL(1) 文法回溯严格 LL(1) 文法语义动作灵活嵌入需额外机制调试难度低可断点高表驱动黑匣子代码量大小性能函数调用开销栈操作开销选型建议如果文法简单且需要嵌入复杂语义动作如类型检查选递归下降如果文法规范且需要快速验证选 LL(1)。实际项目中我一般先用 LL(1) 验证文法是否满足条件再用递归下降实现最终版本。4. 算符优先与 SLR(1)自底向上分析的两条实现路线自底向上分析从 Token 序列出发通过移进和归约逐步构造语法树。算符优先分析法利用运算符之间的优先级关系决定移进还是归约适合表达式分析SLR(1) 分析法构造 LR(0) 项目集规范族用 FOLLOW 集解决冲突能处理更广泛的文法。这一章把两种方法放在一起是因为它们共享移进-归约的框架但冲突解决策略不同。4.1 算符优先关系表的构造与使用算符优先分析的核心是构造优先关系表定义终结符之间的三种关系a b表示 a 的优先级低于 b移进a b表示 a 的优先级高于 b归约a b表示相同优先级匹配。构造方法是对每个产生式A - ...ab...或A - ...aBb...如果 a 和 b 都是终结符则a b如果 a 是终结符且 B 是非终结符对 FIRSTVT(B) 中每个 b 有a b对 LASTVT(B) 中每个 b 有b a。算符优先分析器的驱动逻辑维护一个栈初始为[$]。读入 Token查优先关系表决定动作。如果栈顶终结符当前 Token移进如果归约栈顶的句柄如果移进并标记匹配。归约时找栈顶最左素短语用产生式左部替换。# 算符优先分析器驱动 def operator_precedence_parse(prec_table, tokens): stack [$] tokens tokens [(EOF, $)] pos 0 while stack: top_term next((s for s in reversed(stack) if s in prec_table), $) cur tokens[pos][1] relation prec_table.get(top_term, {}).get(cur, None) if relation or relation : stack.append(cur) pos 1 elif relation : # 归约找最左素短语 handle [] while stack and stack[-1] not in prec_table: handle.insert(0, stack.pop()) if stack: handle.insert(0, stack.pop()) # 用产生式左部替换 handle需查产生式表 stack.append(reduce_handle(handle)) else: raise SyntaxError(f算符优先分析失败{top_term} 与 {cur} 无关系) return True逻辑说明prec_table是嵌套字典{终结符: {终结符: 关系}}。每次循环找栈中最靠近栈顶的终结符与当前 Token 查表。或时移进时归约。归约时从栈顶向下找最左素短语直到遇到终结符。参数方面reduce_handle需要根据产生式表把句柄替换为非终结符。注意算符优先分析不处理单非终结符产生式如E - T需要额外处理。4.2 SLR(1) 项目集规范族与分析表构造SLR(1) 分析法的步骤首先构造 LR(0) 项目集规范族每个项目是产生式 点的位置。从初始项目S - .S开始计算闭包如果点后是非终结符加入该非终结符的所有产生式且点在最左然后对每个符号计算 GOTO 转移直到没有新项目集。然后构造 SLR(1) 分析表对于项目A - α.aβ如果 a 是终结符填ACTION[状态][a] 移进对于项目A - α.对 FOLLOW(A) 中每个终结符填ACTION[状态][a] 归约对于项目S - S.填ACTION[状态][$] 接受。GOTO 表填非终结符转移。SLR(1) 分析表驱动的核心代码# SLR(1) 分析表驱动 def slr1_parse(action_table, goto_table, tokens): state_stack [0] symbol_stack [$] tokens tokens [(EOF, $)] pos 0 while True: state state_stack[-1] cur tokens[pos][1] action action_table.get(state, {}).get(cur, None) if action is None: raise SyntaxError(fSLR(1) 分析失败状态 {state}输入 {cur}) if action[0] shift: state_stack.append(action[1]) symbol_stack.append(cur) pos 1 elif action[0] reduce: prod action[1] # (左部, 右部长度) for _ in range(prod[1]): state_stack.pop() symbol_stack.pop() goto_state goto_table[state_stack[-1]][prod[0]] state_stack.append(goto_state) symbol_stack.append(prod[0]) elif action[0] accept: return True逻辑说明state_stack和symbol_stack同步操作。action_table是{状态: {终结符: (shift, 新状态) 或 (reduce, (左部, 长度)) 或 (accept,)}}。移进时压入新状态和符号归约时弹出对应长度的状态和符号然后查 GOTO 表压入新状态。参数方面goto_table是{状态: {非终结符: 新状态}}。注意 SLR(1) 的冲突解决依赖 FOLLOW 集如果 FOLLOW 集有交集需要升级到 LR(1) 或 LALR(1)。4.3 算符优先与 SLR(1) 的适用场景对比对比维度算符优先SLR(1)文法范围算符优先文法SLR(1) 文法分析表大小小仅终结符大状态×符号冲突处理优先级关系FOLLOW 集实现复杂度低高错误恢复难较易典型应用表达式分析通用编程语言选型建议如果只分析表达式且运算符优先级明确算符优先足够如果需要处理完整编程语言文法含控制流、声明SLR(1) 更合适。实际项目中我一般用算符优先做快速原型用 SLR(1) 做最终实现。5. 语法制导翻译与中间代码生成从语法树到四元式的落地语法制导翻译是在语法分析过程中同步执行语义动作生成中间代码。中间代码有多种形式四元式、三元式、间接三元式、抽象语法树。四元式最常用格式为(op, arg1, arg2, result)。这一章把语法制导翻译和中间代码生成放在一起是因为前者是手段后者是目的。5.1 语法制导定义与翻译方案的设计语法制导定义SDD为每个产生式关联语义规则计算综合属性和继承属性。翻译方案SDT把语义动作嵌入产生式右部用花括号标记执行位置。对于表达式E - E1 TSDD 可以是E.code E1.code || T.code || gen(, E1.addr, T.addr, E.addr)其中||表示代码拼接gen生成四元式。设计翻译方案时关键决策是属性传递方式。自顶向下的 LL(1) 分析适合继承属性从左向右传递自底向上的 SLR(1) 分析适合综合属性从右向左归约。实际项目中我一般用 SLR(1) 框架在归约时执行语义动作因为归约顺序天然对应语法树的后序遍历。# 语法制导翻译表达式四元式生成 quadruples [] temp_count 0 def new_temp(): global temp_count temp_count 1 return ft{temp_count} def gen(op, arg1, arg2, result): quadruples.append((op, arg1, arg2, result)) return result # 语义动作示例E - E1 T def reduce_add(E1_addr, T_addr): temp new_temp() gen(, E1_addr, T_addr, temp) return temp # 语义动作示例E - T def reduce_assign(E_addr, T_addr): gen(, T_addr, _, E_addr) return E_addr逻辑说明quadruples存储所有四元式new_temp生成临时变量。gen把四元式加入列表并返回结果地址。reduce_add在归约E - E1 T时调用生成加法四元式并返回临时变量地址。参数方面E1_addr和T_addr是子表达式的地址可能是变量名或临时变量。注意临时变量编号要全局唯一避免冲突。5.2 四元式生成的完整流程与回填技术四元式生成的完整流程词法分析输出 Token 序列语法分析构造语法树或直接归约语义动作在归约时生成四元式。对于控制流语句if、while需要回填技术处理跳转指令的目标地址。回填的基本思路先生成跳转指令但目标地址留空等目标确定后再填回去。以if (E) S1 else S2为例翻译方案分析 E生成条件四元式得到 E 的地址生成(jnz, E.addr, _, _)目标待回填分析 S1生成 S1 的四元式生成(j, _, _, _)跳过 S2目标待回填回填jnz的目标为 S2 的起始位置分析 S2生成 S2 的四元式回填j的目标为 S2 结束后的位置# 回填技术示例 def backpatch(quad_list, target): for quad in quad_list: quadruples[quad] (quadruples[quad][0], quadruples[quad][1], quadruples[quad][2], target) # if 语句翻译 def translate_if(E_addr, S1_quads, S2_quads): jnz_index len(quadruples) gen(jnz, E_addr, _, _) # 目标待回填 S1_start len(quadruples) # S1 的四元式已生成 j_index len(quadruples) gen(j, _, _, _) # 目标待回填 S2_start len(quadruples) # S2 的四元式已生成 end len(quadruples) backpatch([jnz_index], S2_start) backpatch([j_index], end)逻辑说明backpatch把四元式列表中指定索引的目标地址替换为target。translate_if先生成jnz占位再生成 S1 和j占位最后回填。参数方面quad_list是待回填的四元式索引列表target是目标四元式索引。注意回填顺序不能乱否则目标地址会错。5.3 中间代码生成的验证方法与常见错误验证中间代码生成是否正确最直接的方法是解释执行四元式序列看结果是否与预期一致。写一个简单的四元式解释器维护变量表逐条执行四元式遇到就做加法遇到jnz就跳转。对于复杂程序可以对比生成的四元式序列与手写汇编的语义等价性。常见错误包括临时变量重复编号导致覆盖、跳转目标回填错误导致死循环、运算符优先级处理错误导致表达式求值顺序不对。我一般会在生成四元式后打印完整序列人工检查关键路径。另外四元式中的_表示空操作数解释器需要跳过。6. 六个模块的联调与避坑从独立实验到完整前端六个模块单独跑通只是第一步联调时才会暴露真正的工程问题。这一章记录我在整合词法分析、递归下降、LL(1)、算符优先、SLR(1) 和中间代码生成时踩过的坑以及最终的联调方案。6.1 模块间接口设计与数据流对齐六个模块的接口设计决定了联调难度。词法分析器输出 Token 列表格式为(类型, 值, 行号, 列号)。语法分析器接收 Token 列表输出语法树或直接归约。语法制导翻译在归约时生成四元式。中间代码生成接收四元式列表输出优化后的四元式。接口对齐的关键是 Token 类型定义要统一。词法分析器定义的ID、NUM、OP、KW、DELIM必须与语法分析器的预期一致。我一般会写一个token_types.py集中定义所有 Token 类型常量所有模块导入同一份定义。行号和列号用于错误报告语法分析器报错时能定位到具体位置。数据流对齐的另一个问题是 ε 产生式的处理。递归下降中 ε 产生式直接返回LL(1) 中 ε 不入栈SLR(1) 中 ε 归约不弹栈。联调时要确保各模块对 ε 的处理一致否则会出现 Token 消费错位。6.2 避坑六个模块联调中的五条血泪经验现象一词法分析器把关键字识别为标识符。原因关键字表在识别标识符后查询但查询逻辑写在了 Token 输出之后。解决在输出 Token 前查关键字表如果在表中则类型改为KW。现象二递归下降分析器遇到左递归文法死循环。原因文法E - E T是左递归递归下降会无限展开。解决消除左递归改为E - T EE - T E | ε。现象三LL(1) 分析表出现多重入口。原因FIRST 集有交集文法不满足 LL(1) 条件。解决提取左公因子或改写文法如果无法消除则改用 SLR(1)。现象四SLR(1) 分析表出现移进-归约冲突。原因FOLLOW 集包含当前 Token导致既可移进又可归约。解决检查文法是否有二义性或升级到 LR(1) 用更精确的展望符。现象五四元式回填后跳转目标错误。原因回填时四元式索引计算错误或者回填顺序颠倒。解决在回填前打印四元式列表和索引确认目标地址正确。我一般会在backpatch中加断言检查目标索引在合法范围内。6.3 联调测试用例设计与自动化验证联调测试用例要覆盖六个模块的交互点。我一般设计三组用例第一组是简单表达式a b * c验证词法、语法和四元式生成第二组是控制流if (a b) x 1; else x 2;验证回填和跳转第三组是嵌套结构while (a 10) { a a 1; }验证循环和临时变量管理。自动化验证用 Python 的unittest框架每个用例断言四元式序列与预期一致。对于复杂用例可以只断言关键四元式如跳转指令的目标地址而不比对完整序列。我一般会写一个test_integration.py跑一遍就能发现模块间的接口问题。测试用例输入预期四元式关键点简单表达式a b * c先乘后加临时变量顺序正确条件语句if (a b) x 1;jnz 目标正确赋值四元式存在循环语句while (a 10) a a 1;跳转回循环开始条件判断正确6.4 性能优化与代码生成质量提升六个模块跑通后性能优化是下一步。词法分析器的瓶颈在字符分类可以用查表法替代isalpha和isdigit调用。语法分析器的瓶颈在递归调用可以把递归下降改为迭代或使用预测分析表。四元式生成的瓶颈在临时变量分配可以用寄存器分配算法减少临时变量数量。代码生成质量提升的方向常量折叠编译期计算2 3为5、公共子表达式消除重复计算a b只算一次、死代码消除删除不可达的四元式。这些优化可以在四元式生成后单独做一遍不影响前端模块。我一般会先保证正确性再逐步加优化。每加一个优化跑一遍回归测试确保没有引入新错误。编译原理实验的最终目标不是写出工业级编译器而是理解从字符流到中间代码的完整链路。这套六个模块的源码集合提供了可运行的参考实现照着改一遍比看十遍理论书都管用。希望帮到你。本文还有配套的精品资源点击获取 编译原理课程实验六模块：从词法分析到中间代码生成的完整实现路径
简介这份资源是北京交通大学编译原理课程实验项目的完整源码集合面向计算机科学与技术专业学生及需要系统练习编译器前端开发的开发者。内容覆盖词法分析、递归下降语法分析、LL(1)文法分析、算符优先文法分析、基于SLR(1)分析法的语法制导翻译以及中间代码生成六个核心实验模块从字符序列到记号流、抽象语法树、语法检查直至语义动作触发与中间代码输出构成一条完整的编译前端技术链路。压缩包共94个文件以33个cpp源文件与29个头文件为主体辅以21个txt测试用例与文法文件、6个makefile构建脚本及少量c文件整体约66KB按Lab01至Lab06分目录组织结构清晰便于逐模块对照学习。目前已有92人学习。读者可借助现成源码与测试数据快速搭建实验环境理解各分析方法的实现细节与衔接关系适合作为课程实验参考、期末复习或编译器入门练手材料。1. 编译原理课程实验六个模块从词法分析到中间代码生成的完整落地路径很多同学学完编译原理的理论课考试能拿高分但一上手写词法分析器就卡在正则表达式到 NFA 的转换上更别提后面还有递归下降、LL(1)、算符优先、SLR(1) 和语法制导翻译五座大山。北京交通大学这套编译原理课程实验项目把六个核心模块串成了一条完整的编译器前端实现链路从字符流输入一路走到中间代码输出。它解决的不是“考试怎么考”的问题而是“给你一段类 C 语言的源代码你怎么让机器真正理解它并生成可执行的中间表示”。适合正在做编译原理课程设计的学生、想系统补齐编译器前端实现能力的后端工程师以及需要快速搭建 DSL 解析器的开发者。六个模块分别是词法分析、递归下降语法分析、LL(1) 文法分析、算符优先文法分析、基于 SLR(1) 分析法的语法制导翻译、中间代码生成。每个模块独立可运行又层层递进构成完整前端。2. 词法分析器从正则表达式到 DFA 的最小实现路径词法分析是整个编译器的入口任务是把源代码字符流切分成有意义的 Token 序列。很多教程一上来就讲自动机理论但真正动手写的时候你需要的是一条从正则表达式到确定有限自动机DFA的工程化路径。常见做法是先用正则表达式描述每种 Token 的模式再手工构造或程序生成 DFA最后用状态转移表驱动扫描器。2.1 正则表达式到 NFA 再到 DFA 的转换逻辑词法分析的核心是识别标识符、关键字、数字常量、运算符和界符。以标识符为例正则表达式是[a-zA-Z_][a-zA-Z0-9_]*对应的 NFA 有两个状态起始状态接受字母或下划线后进入接受状态接受状态可以循环接受字母、数字或下划线。关键字是标识符的特例通常在识别出标识符后查关键字表来区分。从 NFA 到 DFA 用子集构造法每个 DFA 状态是 NFA 状态的集合初始状态是 NFA 起始状态的 ε-闭包对每个输入符号计算转移后的 ε-闭包直到没有新状态产生。DFA 最小化用 Hopcroft 算法或简单的分割法把等价状态合并。实际工程中如果 Token 种类不多二三十种手工构造 DFA 状态转移表反而比程序生成更可控。下面是一个用 Python 实现的简化词法分析器核心代码采用状态转移表驱动# 词法分析器核心状态转移表驱动 # 状态定义0起始, 1标识符/关键字, 2数字, 3运算符, 4界符, 5接受 TRANSITION { (0, letter): 1, (0, digit): 2, (0, op): 3, (0, delim): 4, (1, letter): 1, (1, digit): 1, (1, other): 5, (2, digit): 2, (2, dot): 2, (2, other): 5, (3, op): 5, (4, delim): 5, } KEYWORDS {if, else, while, for, int, float, return} def classify(ch): if ch.isalpha() or ch _: return letter if ch.isdigit(): return digit if ch in -*/!|: return op if ch in (){}[];,: return delim return other def tokenize(source): tokens, i, state [], 0, 0 buf while i len(source): ch source[i] cls classify(ch) key (state, cls) if key in TRANSITION: state TRANSITION[key] buf ch i 1 else: if buf: tokens.append((ID if buf not in KEYWORDS else KW, buf)) buf state 0 if ch.isspace(): i 1 else: # 无法识别的字符报错 raise SyntaxError(f非法字符 {ch} 在位置 {i}) if buf: tokens.append((ID if buf not in KEYWORDS else KW, buf)) return tokens这段代码的逻辑说明TRANSITION字典定义了状态转移规则键是(当前状态, 字符类别)值是目标状态。classify函数把字符映射到类别。主循环中如果当前状态和字符类别有转移规则就更新状态并累积字符否则说明当前 Token 结束把缓冲区内容作为 Token 输出然后重置状态。参数方面KEYWORDS集合需要根据目标语言的关键字表调整TRANSITION表在 Token 种类增加时需要同步扩展。注意数字识别中dot的处理是为了支持浮点数但需要额外状态来区分1.和1.5以及.5的合法性。2.2 词法分析器的参数配置与测试方法词法分析器的关键参数有三个最大标识符长度、数字常量的进制支持、注释处理策略。最大标识符长度影响缓冲区大小一般设为 256 足够数字常量要决定是否支持十六进制0x前缀和科学计数法e指数注释处理有两种策略——在词法阶段直接跳过或者作为特殊 Token 返回给语法分析器。常见做法是词法阶段跳过单行注释//和块注释/* */但块注释的嵌套处理容易翻车建议不支持嵌套。测试词法分析器时构造覆盖所有 Token 类型的输入文件逐行检查输出 Token 序列。重点验证边界情况标识符后紧跟运算符ab应输出ID(a), OP(), ID(b)、数字后紧跟字母123abc应报错或拆分为NUM(123), ID(abc)、字符串中的转义字符处理。我一般会写一个test_lexer.py用assert断言预期 Token 序列跑一遍就能发现大部分问题。3. 递归下降与 LL(1)两种自顶向下语法分析的工程取舍语法分析是编译器的核心任务是根据文法规则把 Token 序列组织成语法树。递归下降和 LL(1) 都是自顶向下方法但工程实现差异很大。递归下降用手写递归函数模拟推导过程灵活但代码量大LL(1) 用预测分析表驱动自动化程度高但对文法要求苛刻。这一章把两种方法放在一起讲是因为它们共享 FIRST 集和 FOLLOW 集的计算逻辑而且实际项目中经常先用 LL(1) 验证文法再用递归下降处理需要语义动作的场景。3.1 递归下降分析器的函数骨架与回溯处理递归下降的核心思想是为每个非终结符写一个函数函数内部根据当前 Token 决定展开哪个产生式。如果产生式有多个候选需要计算 FIRST 集来决定选择当 FIRST 集有交集时需要提取左公因子或做回溯。回溯的实现方式是记录当前 Token 位置尝试一个产生式失败后恢复到该位置再试下一个。下面是一个递归下降分析器的骨架代码处理简单的表达式文法# 递归下降分析器骨架 # 文法E - T E, E - T E | ε, T - F T, T - *F T | ε, F - (E) | id 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 match(self, expected_type): tok self.peek() if tok[0] expected_type: self.pos 1 return tok raise SyntaxError(f期望 {expected_type}实际 {tok}) def parse_E(self): self.parse_T() self.parse_E_prime() def parse_E_prime(self): if self.peek()[0] OP and self.peek()[1] : self.match(OP) self.parse_T() self.parse_E_prime() # ε 产生式什么都不做 def parse_T(self): self.parse_F() self.parse_T_prime() def parse_T_prime(self): if self.peek()[0] OP and self.peek()[1] *: self.match(OP) self.parse_F() self.parse_T_prime() def parse_F(self): tok self.peek() if tok[0] ID: self.match(ID) elif tok[0] DELIM and tok[1] (: self.match(DELIM) self.parse_E() self.match(DELIM) # 期望 ) else: raise SyntaxError(fF 无法匹配 {tok})逻辑说明每个非终结符对应一个parse_X方法。peek返回当前 Token 但不移动位置match检查并消费 Token。E和T的处理体现了消除左递归后的文法结构——当遇到或*时进入递归否则走 ε 产生式直接返回。参数方面tokens是词法分析器的输出列表每个元素是(类型, 值)元组。注意match中的expected_type只检查类型如果需要精确匹配运算符值要额外判断tok[1]。3.2 LL(1) 预测分析表的构造与驱动LL(1) 分析器用一张二维表M[非终结符][终结符] 产生式来驱动。构造这张表需要先计算 FIRST 集和 FOLLOW 集。FIRST(A) 是 A 能推导出的所有串的首终结符集合FOLLOW(A) 是 A 后面可能紧跟的终结符集合。对于产生式A - α如果a在 FIRST(α) 中则M[A][a] A - α如果 α 能推导出 ε 且a在 FOLLOW(A) 中则M[A][a] A - α。构造 FIRST 集的算法对于终结符FIRST(a) {a}对于非终结符 A扫描所有产生式A - X1X2...Xn把 FIRST(X1) 中非 ε 的符号加入 FIRST(A)如果 X1 能推导 ε 则继续看 X2以此类推。FOLLOW 集的计算起始符号的 FOLLOW 包含$对于产生式A - αBβ把 FIRST(β) 中非 ε 的符号加入 FOLLOW(B)如果 β 能推导 ε 或 β 为空把 FOLLOW(A) 加入 FOLLOW(B)。LL(1) 分析表驱动的核心代码# LL(1) 分析表驱动 def ll1_parse(table, start_symbol, tokens): stack [$, start_symbol] tokens tokens [(EOF, $)] pos 0 while stack: top stack.pop() cur tokens[pos] if top cur[0] or top cur[1]: pos 1 elif top in table and cur[0] in table[top]: production table[top][cur[0]] # production 是产生式右部列表逆序入栈 for sym in reversed(production): if sym ! ε: stack.append(sym) else: raise SyntaxError(fLL(1) 分析失败栈顶 {top}当前 {cur}) return True逻辑说明栈初始化为[$, 起始符号]每次取栈顶和当前 Token。如果栈顶是终结符且匹配当前 Token消费 Token如果栈顶是非终结符且表中有对应产生式把产生式右部逆序入栈。参数方面table是嵌套字典{非终结符: {终结符: 产生式右部列表}}start_symbol是文法起始符号。注意产生式右部中的 ε 不入栈因为 ε 表示空串。3.3 递归下降与 LL(1) 的选型对比对比维度递归下降LL(1)实现方式手写递归函数预测分析表驱动文法限制可处理部分非 LL(1) 文法回溯严格 LL(1) 文法语义动作灵活嵌入需额外机制调试难度低可断点高表驱动黑匣子代码量大小性能函数调用开销栈操作开销选型建议如果文法简单且需要嵌入复杂语义动作如类型检查选递归下降如果文法规范且需要快速验证选 LL(1)。实际项目中我一般先用 LL(1) 验证文法是否满足条件再用递归下降实现最终版本。4. 算符优先与 SLR(1)自底向上分析的两条实现路线自底向上分析从 Token 序列出发通过移进和归约逐步构造语法树。算符优先分析法利用运算符之间的优先级关系决定移进还是归约适合表达式分析SLR(1) 分析法构造 LR(0) 项目集规范族用 FOLLOW 集解决冲突能处理更广泛的文法。这一章把两种方法放在一起是因为它们共享移进-归约的框架但冲突解决策略不同。4.1 算符优先关系表的构造与使用算符优先分析的核心是构造优先关系表定义终结符之间的三种关系a b表示 a 的优先级低于 b移进a b表示 a 的优先级高于 b归约a b表示相同优先级匹配。构造方法是对每个产生式A - ...ab...或A - ...aBb...如果 a 和 b 都是终结符则a b如果 a 是终结符且 B 是非终结符对 FIRSTVT(B) 中每个 b 有a b对 LASTVT(B) 中每个 b 有b a。算符优先分析器的驱动逻辑维护一个栈初始为[$]。读入 Token查优先关系表决定动作。如果栈顶终结符当前 Token移进如果归约栈顶的句柄如果移进并标记匹配。归约时找栈顶最左素短语用产生式左部替换。# 算符优先分析器驱动 def operator_precedence_parse(prec_table, tokens): stack [$] tokens tokens [(EOF, $)] pos 0 while stack: top_term next((s for s in reversed(stack) if s in prec_table), $) cur tokens[pos][1] relation prec_table.get(top_term, {}).get(cur, None) if relation or relation : stack.append(cur) pos 1 elif relation : # 归约找最左素短语 handle [] while stack and stack[-1] not in prec_table: handle.insert(0, stack.pop()) if stack: handle.insert(0, stack.pop()) # 用产生式左部替换 handle需查产生式表 stack.append(reduce_handle(handle)) else: raise SyntaxError(f算符优先分析失败{top_term} 与 {cur} 无关系) return True逻辑说明prec_table是嵌套字典{终结符: {终结符: 关系}}。每次循环找栈中最靠近栈顶的终结符与当前 Token 查表。或时移进时归约。归约时从栈顶向下找最左素短语直到遇到终结符。参数方面reduce_handle需要根据产生式表把句柄替换为非终结符。注意算符优先分析不处理单非终结符产生式如E - T需要额外处理。4.2 SLR(1) 项目集规范族与分析表构造SLR(1) 分析法的步骤首先构造 LR(0) 项目集规范族每个项目是产生式 点的位置。从初始项目S - .S开始计算闭包如果点后是非终结符加入该非终结符的所有产生式且点在最左然后对每个符号计算 GOTO 转移直到没有新项目集。然后构造 SLR(1) 分析表对于项目A - α.aβ如果 a 是终结符填ACTION[状态][a] 移进对于项目A - α.对 FOLLOW(A) 中每个终结符填ACTION[状态][a] 归约对于项目S - S.填ACTION[状态][$] 接受。GOTO 表填非终结符转移。SLR(1) 分析表驱动的核心代码# SLR(1) 分析表驱动 def slr1_parse(action_table, goto_table, tokens): state_stack [0] symbol_stack [$] tokens tokens [(EOF, $)] pos 0 while True: state state_stack[-1] cur tokens[pos][1] action action_table.get(state, {}).get(cur, None) if action is None: raise SyntaxError(fSLR(1) 分析失败状态 {state}输入 {cur}) if action[0] shift: state_stack.append(action[1]) symbol_stack.append(cur) pos 1 elif action[0] reduce: prod action[1] # (左部, 右部长度) for _ in range(prod[1]): state_stack.pop() symbol_stack.pop() goto_state goto_table[state_stack[-1]][prod[0]] state_stack.append(goto_state) symbol_stack.append(prod[0]) elif action[0] accept: return True逻辑说明state_stack和symbol_stack同步操作。action_table是{状态: {终结符: (shift, 新状态) 或 (reduce, (左部, 长度)) 或 (accept,)}}。移进时压入新状态和符号归约时弹出对应长度的状态和符号然后查 GOTO 表压入新状态。参数方面goto_table是{状态: {非终结符: 新状态}}。注意 SLR(1) 的冲突解决依赖 FOLLOW 集如果 FOLLOW 集有交集需要升级到 LR(1) 或 LALR(1)。4.3 算符优先与 SLR(1) 的适用场景对比对比维度算符优先SLR(1)文法范围算符优先文法SLR(1) 文法分析表大小小仅终结符大状态×符号冲突处理优先级关系FOLLOW 集实现复杂度低高错误恢复难较易典型应用表达式分析通用编程语言选型建议如果只分析表达式且运算符优先级明确算符优先足够如果需要处理完整编程语言文法含控制流、声明SLR(1) 更合适。实际项目中我一般用算符优先做快速原型用 SLR(1) 做最终实现。5. 语法制导翻译与中间代码生成从语法树到四元式的落地语法制导翻译是在语法分析过程中同步执行语义动作生成中间代码。中间代码有多种形式四元式、三元式、间接三元式、抽象语法树。四元式最常用格式为(op, arg1, arg2, result)。这一章把语法制导翻译和中间代码生成放在一起是因为前者是手段后者是目的。5.1 语法制导定义与翻译方案的设计语法制导定义SDD为每个产生式关联语义规则计算综合属性和继承属性。翻译方案SDT把语义动作嵌入产生式右部用花括号标记执行位置。对于表达式E - E1 TSDD 可以是E.code E1.code || T.code || gen(, E1.addr, T.addr, E.addr)其中||表示代码拼接gen生成四元式。设计翻译方案时关键决策是属性传递方式。自顶向下的 LL(1) 分析适合继承属性从左向右传递自底向上的 SLR(1) 分析适合综合属性从右向左归约。实际项目中我一般用 SLR(1) 框架在归约时执行语义动作因为归约顺序天然对应语法树的后序遍历。# 语法制导翻译表达式四元式生成 quadruples [] temp_count 0 def new_temp(): global temp_count temp_count 1 return ft{temp_count} def gen(op, arg1, arg2, result): quadruples.append((op, arg1, arg2, result)) return result # 语义动作示例E - E1 T def reduce_add(E1_addr, T_addr): temp new_temp() gen(, E1_addr, T_addr, temp) return temp # 语义动作示例E - T def reduce_assign(E_addr, T_addr): gen(, T_addr, _, E_addr) return E_addr逻辑说明quadruples存储所有四元式new_temp生成临时变量。gen把四元式加入列表并返回结果地址。reduce_add在归约E - E1 T时调用生成加法四元式并返回临时变量地址。参数方面E1_addr和T_addr是子表达式的地址可能是变量名或临时变量。注意临时变量编号要全局唯一避免冲突。5.2 四元式生成的完整流程与回填技术四元式生成的完整流程词法分析输出 Token 序列语法分析构造语法树或直接归约语义动作在归约时生成四元式。对于控制流语句if、while需要回填技术处理跳转指令的目标地址。回填的基本思路先生成跳转指令但目标地址留空等目标确定后再填回去。以if (E) S1 else S2为例翻译方案分析 E生成条件四元式得到 E 的地址生成(jnz, E.addr, _, _)目标待回填分析 S1生成 S1 的四元式生成(j, _, _, _)跳过 S2目标待回填回填jnz的目标为 S2 的起始位置分析 S2生成 S2 的四元式回填j的目标为 S2 结束后的位置# 回填技术示例 def backpatch(quad_list, target): for quad in quad_list: quadruples[quad] (quadruples[quad][0], quadruples[quad][1], quadruples[quad][2], target) # if 语句翻译 def translate_if(E_addr, S1_quads, S2_quads): jnz_index len(quadruples) gen(jnz, E_addr, _, _) # 目标待回填 S1_start len(quadruples) # S1 的四元式已生成 j_index len(quadruples) gen(j, _, _, _) # 目标待回填 S2_start len(quadruples) # S2 的四元式已生成 end len(quadruples) backpatch([jnz_index], S2_start) backpatch([j_index], end)逻辑说明backpatch把四元式列表中指定索引的目标地址替换为target。translate_if先生成jnz占位再生成 S1 和j占位最后回填。参数方面quad_list是待回填的四元式索引列表target是目标四元式索引。注意回填顺序不能乱否则目标地址会错。5.3 中间代码生成的验证方法与常见错误验证中间代码生成是否正确最直接的方法是解释执行四元式序列看结果是否与预期一致。写一个简单的四元式解释器维护变量表逐条执行四元式遇到就做加法遇到jnz就跳转。对于复杂程序可以对比生成的四元式序列与手写汇编的语义等价性。常见错误包括临时变量重复编号导致覆盖、跳转目标回填错误导致死循环、运算符优先级处理错误导致表达式求值顺序不对。我一般会在生成四元式后打印完整序列人工检查关键路径。另外四元式中的_表示空操作数解释器需要跳过。6. 六个模块的联调与避坑从独立实验到完整前端六个模块单独跑通只是第一步联调时才会暴露真正的工程问题。这一章记录我在整合词法分析、递归下降、LL(1)、算符优先、SLR(1) 和中间代码生成时踩过的坑以及最终的联调方案。6.1 模块间接口设计与数据流对齐六个模块的接口设计决定了联调难度。词法分析器输出 Token 列表格式为(类型, 值, 行号, 列号)。语法分析器接收 Token 列表输出语法树或直接归约。语法制导翻译在归约时生成四元式。中间代码生成接收四元式列表输出优化后的四元式。接口对齐的关键是 Token 类型定义要统一。词法分析器定义的ID、NUM、OP、KW、DELIM必须与语法分析器的预期一致。我一般会写一个token_types.py集中定义所有 Token 类型常量所有模块导入同一份定义。行号和列号用于错误报告语法分析器报错时能定位到具体位置。数据流对齐的另一个问题是 ε 产生式的处理。递归下降中 ε 产生式直接返回LL(1) 中 ε 不入栈SLR(1) 中 ε 归约不弹栈。联调时要确保各模块对 ε 的处理一致否则会出现 Token 消费错位。6.2 避坑六个模块联调中的五条血泪经验现象一词法分析器把关键字识别为标识符。原因关键字表在识别标识符后查询但查询逻辑写在了 Token 输出之后。解决在输出 Token 前查关键字表如果在表中则类型改为KW。现象二递归下降分析器遇到左递归文法死循环。原因文法E - E T是左递归递归下降会无限展开。解决消除左递归改为E - T EE - T E | ε。现象三LL(1) 分析表出现多重入口。原因FIRST 集有交集文法不满足 LL(1) 条件。解决提取左公因子或改写文法如果无法消除则改用 SLR(1)。现象四SLR(1) 分析表出现移进-归约冲突。原因FOLLOW 集包含当前 Token导致既可移进又可归约。解决检查文法是否有二义性或升级到 LR(1) 用更精确的展望符。现象五四元式回填后跳转目标错误。原因回填时四元式索引计算错误或者回填顺序颠倒。解决在回填前打印四元式列表和索引确认目标地址正确。我一般会在backpatch中加断言检查目标索引在合法范围内。6.3 联调测试用例设计与自动化验证联调测试用例要覆盖六个模块的交互点。我一般设计三组用例第一组是简单表达式a b * c验证词法、语法和四元式生成第二组是控制流if (a b) x 1; else x 2;验证回填和跳转第三组是嵌套结构while (a 10) { a a 1; }验证循环和临时变量管理。自动化验证用 Python 的unittest框架每个用例断言四元式序列与预期一致。对于复杂用例可以只断言关键四元式如跳转指令的目标地址而不比对完整序列。我一般会写一个test_integration.py跑一遍就能发现模块间的接口问题。测试用例输入预期四元式关键点简单表达式a b * c先乘后加临时变量顺序正确条件语句if (a b) x 1;jnz 目标正确赋值四元式存在循环语句while (a 10) a a 1;跳转回循环开始条件判断正确6.4 性能优化与代码生成质量提升六个模块跑通后性能优化是下一步。词法分析器的瓶颈在字符分类可以用查表法替代isalpha和isdigit调用。语法分析器的瓶颈在递归调用可以把递归下降改为迭代或使用预测分析表。四元式生成的瓶颈在临时变量分配可以用寄存器分配算法减少临时变量数量。代码生成质量提升的方向常量折叠编译期计算2 3为5、公共子表达式消除重复计算a b只算一次、死代码消除删除不可达的四元式。这些优化可以在四元式生成后单独做一遍不影响前端模块。我一般会先保证正确性再逐步加优化。每加一个优化跑一遍回归测试确保没有引入新错误。编译原理实验的最终目标不是写出工业级编译器而是理解从字符流到中间代码的完整链路。这套六个模块的源码集合提供了可运行的参考实现照着改一遍比看十遍理论书都管用。希望帮到你。本文还有配套的精品资源点击获取