广工编译原理实验通关：从词法分析到代码生成的手写编译器实战

简介这份资源面向计算机专业学习编译原理的学生围绕教学型编译程序PL/0展开词法、语法与语义分析的修改扩充实验帮助读者在动手改造中理解编译过程的基本原理与实现方法。实验要求增加ELSE、FOR、TO、DOWNTO、RETURN等保留字及、-、、--等运算符将不等号#改为并为条件语句补充ELSE子句属于编译原理课程中典型的进阶实验任务。压缩包共24个文件约644KB包含cpp与h源码、dsp与dsw工程文件、exe可执行程序、doc实验报告以及obj、pdb、ilk等编译中间产物覆盖从源码到可运行程序的完整工程结构。目前已有789人学习下载适合需要参考PL/0改造思路、对照实验报告与测试代码进行调试排错的同学可据此快速搭建实验环境并验证各扩充功能的实现效果。1. 广工编译原理实验从词法分析到代码生成的完整通关路径如果你在广工选过编译原理这门课大概率经历过这样的场景实验指导书发下来要求实现一个从词法分析到目标代码生成的完整编译器前端但课上讲的 LL(1)、LR(1) 和语法制导翻译到了动手环节全变成了玄学。编译原理实验和计算机组成原理实验、CSAPP 实验并称三大硬核课设区别在于后两者还能靠 Quartus 原理图或者单链表基本操作实验的经验硬扛而编译器实验一旦某个环节的自动机状态转移写错后面所有阶段全部翻车。这篇笔记面向正在做广工编译原理实验的同学也面向任何想从零手写一个小型编译器前端的开发者。我会按实验通常的阶段划分把词法分析、语法分析、语义分析、中间代码生成这条链路拆开每个阶段给出可复现的实现思路、关键参数设置和我在实际编码中踩过的坑。不依赖任何特定版本的实验框架核心逻辑用 Python 写清楚你换成 C 或 Java 也能直接迁移。2. 词法分析器正则到 DFA 的手工构造与代码落地2.1 为什么实验第一步总是词法分析编译器的输入是一串字符流词法分析的任务是把它切分成有意义的词素token比如关键字int、标识符count、运算符、常量10。广工实验通常要求支持的语言子集包括整型与浮点型常量、标识符、基本运算符、分隔符和若干关键字。这一步的核心理论是正则表达式到有限自动机的转换但实验里更常见的做法是直接手写一个状态机而不是用 lex 这类工具生成。原因很实际手写状态机虽然代码量大但调试直观每个字符读入后状态怎么跳转一目了然。用工具生成的话一旦正则写错生成的 DFA 状态表可读性极差排查起来就是黑匣子。我一般会先用正则把每种 token 的模式理清楚再手工画出状态转移图最后翻译成代码。2.2 手写词法分析器的完整代码与参数说明下面是一个支持整型常量、浮点常量、标识符、关键字和基本运算符的词法分析器核心实现。代码用 Python 写但逻辑是语言无关的。import re # token 类型定义 TOKEN_TYPES { INT: r\d, FLOAT: r\d\.\d, ID: r[a-zA-Z_][a-zA-Z0-9_]*, OP: r[\-*/!], SEP: r[;,.(){}], KEYWORD: r\b(if|else|while|int|float|return)\b } class Lexer: def __init__(self, source): self.source source self.pos 0 self.tokens [] # 关键字集合用于区分 ID 和 KEYWORD self.keywords {if, else, while, int, float, return} def tokenize(self): while self.pos len(self.source): # 跳过空白字符 if self.source[self.pos].isspace(): self.pos 1 continue matched False # 按优先级尝试匹配先长后短避免 FLOAT 被 INT 截断 for token_type in [FLOAT, INT, ID, KEYWORD, OP, SEP]: pattern TOKEN_TYPES[token_type] regex re.compile(pattern) match regex.match(self.source, self.pos) if match: value match.group() # 标识符需要二次判断是否为关键字 if token_type ID and value in self.keywords: token_type KEYWORD self.tokens.append((token_type, value)) self.pos match.end() matched True break if not matched: raise SyntaxError(f非法字符 {self.source[self.pos]} 在位置 {self.pos}) return self.tokens # 测试 if __name__ __main__: code int count 10; float rate 3.14; if count 0 { count count 1; } lexer Lexer(code) for token in lexer.tokenize(): print(token)这段代码的逻辑说明tokenize方法维护一个位置指针pos每次循环先跳过空白然后按FLOAT → INT → ID → KEYWORD → OP → SEP的顺序尝试匹配。参数说明匹配顺序至关重要FLOAT必须排在INT前面否则3.14会被INT匹配成3然后剩下.14无法处理。关键字识别采用二次判断策略——先用ID的正则匹配出单词再查关键字集合这样比单独写关键字正则更灵活增加关键字只需改集合。2.3 词法分析阶段最容易翻车的三个点第一个坑是最长匹配原则。比如和如果运算符正则写成[\-*/!]单字符匹配会被拆成和两个 token。解决办法是在运算符匹配时优先尝试双字符运算符或者把正则改成|||!|[\-*/!]这种多字符优先的模式。第二个坑是浮点数的边界情况。3.和.14在多数语言里都是非法的但你的正则\d\.\d会直接跳过它们导致报错信息不明确。建议在词法阶段就给出精确的错误位置和原因方便后续调试。第三个坑是注释和字符串的处理。如果实验要求支持注释需要在跳过空白之前先处理//和/* */否则注释里的内容会被当成 token 解析。字符串同理需要单独的状态来处理转义字符。3. 语法分析递归下降与 LR(1) 的选型对比及实现3.1 广工实验里语法分析的两种主流路线语法分析的任务是把 token 序列组织成抽象语法树AST。广工实验通常允许两种实现方式递归下降分析法和 LR(1) 分析法。递归下降适合文法比较简单的场景代码结构清晰每个非终结符对应一个函数LR(1) 适合处理更复杂的文法但需要构造分析表代码量更大。我的建议是如果实验要求的文法没有左递归优先用递归下降因为调试成本低得多。如果文法里有左递归或者需要处理运算符优先级LR(1) 更稳妥。下面给出递归下降的完整实现框架并说明如何消除左递归。3.2 递归下降分析器的代码实现与 AST 构建假设实验要求的文法如下简化版program → stmt_list stmt_list → stmt stmt_list | ε stmt → assign_stmt | if_stmt | while_stmt assign_stmt→ ID expr ; expr → term (( | -) term)* term → factor ((* | /) factor)* factor → INT | FLOAT | ID | ( expr )对应的递归下降分析器代码class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): # 返回当前 token不消耗 if self.pos len(self.tokens): return self.tokens[self.pos] return (EOF, ) def consume(self, expected_typeNone): # 消耗当前 token可校验类型 token self.peek() if expected_type and token[0] ! expected_type: raise SyntaxError(f期望 {expected_type}实际得到 {token}) self.pos 1 return token def parse_program(self): stmts [] while self.peek()[0] ! EOF: stmts.append(self.parse_stmt()) return (program, stmts) def parse_stmt(self): token self.peek() if token[0] KEYWORD and token[1] if: return self.parse_if() elif token[0] KEYWORD and token[1] while: return self.parse_while() elif token[0] ID: return self.parse_assign() else: raise SyntaxError(f无法识别的语句起始: {token}) def parse_assign(self): name self.consume(ID)[1] self.consume(OP) # 消耗 value self.parse_expr() self.consume(SEP) # 消耗 ; return (assign, name, value) def parse_expr(self): # expr → term (( | -) term)* node self.parse_term() while self.peek()[0] OP and self.peek()[1] in (, -): op self.consume(OP)[1] right self.parse_term() node (binop, op, node, right) return node def parse_term(self): # term → factor ((* | /) factor)* node self.parse_factor() while self.peek()[0] OP and self.peek()[1] in (*, /): op self.consume(OP)[1] right self.parse_factor() node (binop, op, node, right) return node def parse_factor(self): token self.peek() if token[0] in (INT, FLOAT): self.consume() return (num, token[1]) elif token[0] ID: self.consume() return (var, token[1]) elif token[0] SEP and token[1] (: self.consume(SEP) node self.parse_expr() self.consume(SEP) # 消耗 ) return node else: raise SyntaxError(f无法识别的因子: {token})逻辑说明每个非终结符对应一个parse_xxx方法方法内部根据当前 token 决定走哪条产生式。peek和consume是辅助方法前者只看不消耗后者消耗并可选校验类型。参数说明parse_expr和parse_term通过循环处理左递归把expr → term (( | -) term)*这种形式直接翻译成 while 循环避免了显式消除左递归的步骤。运算符优先级通过分层处理——expr处理加减term处理乘除factor处理括号和原子这样2 3 * 4会正确解析成2 (3 * 4)。3.3 语法错误恢复与报错信息设计实验里经常要求语法分析器在遇到错误时能给出有意义的报错而不是直接崩溃。常见的做法是恐慌模式恢复当consume失败时跳过 token 直到遇到一个同步集合中的 token比如;或}然后继续分析。这样一次运行能报出多个错误而不是遇到第一个就停。另一个实用技巧是在报错信息里带上行号和列号。词法分析阶段可以在 token 里附带位置信息语法分析报错时直接引用。广工实验的测试用例通常包含错误输入报错信息的质量直接影响评分。4. 语义分析与中间代码生成从 AST 到三地址码4.1 语义分析要解决的核心问题语法分析只保证结构正确语义分析要检查变量是否声明、类型是否匹配、函数调用参数是否一致。广工实验里通常要求实现符号表管理和类型检查。符号表可以用哈希表实现键是变量名值是类型、作用域层级和内存偏移等信息。类型检查的常见做法是在 AST 上做一次遍历自底向上推导每个节点的类型。比如binop节点的类型取决于左右操作数的类型两个int相加得intint和float相加得float。如果类型不匹配比如对float做取模运算就报语义错误。4.2 三地址码生成的代码实现中间代码生成的目标是把 AST 翻译成三地址码TAC每条指令最多有一个运算符和三个操作数。下面是在 AST 遍历过程中生成 TAC 的实现class TACGenerator: def __init__(self): self.temp_count 0 self.code [] self.symbol_table {} def new_temp(self): # 生成新的临时变量名 self.temp_count 1 return ft{self.temp_count} def generate(self, node): if node[0] program: for stmt in node[1]: self.generate(stmt) elif node[0] assign: # assign: (assign, name, expr) _, name, expr node result self.generate(expr) self.code.append(f{name} {result}) # 更新符号表记录变量类型 self.symbol_table[name] self.infer_type(expr) elif node[0] binop: # binop: (binop, op, left, right) _, op, left, right node left_val self.generate(left) right_val self.generate(right) temp self.new_temp() self.code.append(f{temp} {left_val} {op} {right_val}) return temp elif node[0] num: return node[1] elif node[0] var: return node[1] return None def infer_type(self, node): # 简单的类型推导根据节点结构判断 if node[0] num: return float if . in node[1] else int elif node[0] var: return self.symbol_table.get(node[1], unknown) elif node[0] binop: left_type self.infer_type(node[2]) right_type self.infer_type(node[3]) if float in (left_type, right_type): return float return int return unknown # 测试对之前解析出的 AST 生成 TAC # 假设 AST 为 (program, [(assign, count, (binop, , (var, count), (num, 1)))]) ast (program, [(assign, count, (binop, , (var, count), (num, 1)))]) gen TACGenerator() gen.generate(ast) for line in gen.code: print(line) # 输出t1 count 1 # count t1逻辑说明generate方法对每种 AST 节点类型做不同处理。binop节点递归生成左右操作数的值然后创建一个新临时变量存放运算结果。assign节点生成表达式值后直接赋值给变量名。参数说明new_temp用计数器生成唯一的临时变量名避免冲突。infer_type做简单的类型推导实际实验中可能需要更复杂的类型系统比如支持数组和结构体。4.3 符号表的作用域管理策略如果实验要求支持块级作用域比如if和while的花括号内可以声明局部变量符号表需要支持嵌套。常见做法是用栈式符号表进入一个块时压入新作用域退出时弹出。查找变量时从栈顶往下找找到第一个匹配的就返回。这样内层作用域的变量会遮蔽外层同名变量符合多数语言的语义。实现上可以用一个列表套字典的结构scopes [{}]进入块时scopes.append({})退出时scopes.pop()。查找时for scope in reversed(scopes): if name in scope: return scope[name]。这个结构简单但有效广工实验的规模完全够用。5. 实验避坑与常见问题排查5.1 词法分析报错位置不准现象报错信息说“非法字符在位置 15”但实际错误在位置 12。原因跳过空白和注释时没有更新位置信息或者正则匹配失败后没有回退位置指针。解决每次pos变更后都记录行号和列号报错时输出行列号而不是绝对偏移。可以在Lexer里维护line和col两个变量遇到\n时line 1, col 0。5.2 语法分析遇到左递归直接栈溢出现象程序运行后报RecursionError: maximum recursion depth exceeded。原因文法中存在直接左递归比如expr → expr term递归下降分析器会无限递归。解决把左递归改写成右递归或循环形式。expr → expr term | term改成expr → term (( | -) term)*代码里用 while 循环处理。如果文法复杂到无法手工消除左递归考虑改用 LR(1) 分析表驱动的方式。5.3 临时变量命名冲突导致 TAC 错误现象生成的三地址码里出现两个不同的表达式用了同一个临时变量名导致计算结果被覆盖。原因临时变量计数器在递归调用中被重置或者多个生成器实例共享了计数器。解决确保temp_count是实例变量而不是类变量每次new_temp都递增。如果多线程生成 TAC需要加锁或者用线程局部存储。5.4 符号表查找失败但变量明明声明了现象语义分析报“变量未声明”但代码里确实有int count 10;。原因符号表的作用域管理有问题声明时插入到了错误的作用域或者查找时没有从内层往外层遍历。解决在声明变量时打印当前作用域栈的深度和内容确认插入位置正确。查找时用reversed(scopes)从最内层开始找。另外注意声明和使用的顺序——如果语言要求先声明后使用语义分析必须按语句顺序遍历不能先收集所有声明再检查使用。5.5 浮点数常量解析精度丢失现象3.14被解析成3.1400000000000001导致后续类型检查或代码生成出错。原因直接用float()转换字符串会引入浮点精度问题。解决在词法分析阶段保留原始字符串形式只在需要计算时才转换。TAC 生成时直接输出字符串3.14让目标代码生成阶段决定如何处理。如果实验要求做常量折叠用decimal.Decimal代替float来保持精度。6. 用测试用例驱动开发从最小可运行到完整覆盖做编译器实验最有效的方法不是一次性写完所有模块再调试而是用测试用例驱动开发。我一般会先准备一组最小输入覆盖每个阶段的边界情况然后每实现一个功能就跑一遍测试确保没有回归。具体做法是建一个tests/目录每个测试文件包含输入代码和期望的 token 序列、AST 结构或 TAC 输出。用 Python 的unittest或者简单的assert就能跑。比如词法分析的测试def test_lexer(): lexer Lexer(int x 10;) tokens lexer.tokenize() expected [(KEYWORD, int), (ID, x), (OP, ), (INT, 10), (SEP, ;)] assert tokens expected, f期望 {expected}实际 {tokens} print(词法分析测试通过) test_lexer()语法分析的测试可以检查 AST 的结构是否正确def test_parser(): lexer Lexer(x 1 2 * 3;) tokens lexer.tokenize() parser Parser(tokens) ast parser.parse_program() # 期望 AST 中 2 * 3 先结合 expected (program, [(assign, x, (binop, , (num, 1), (binop, *, (num, 2), (num, 3))))]) assert ast expected, fAST 不匹配: {ast} print(语法分析测试通过) test_parser()这种测试驱动的方式有个额外好处广工实验的验收通常包含隐藏测试用例你提前覆盖了边界情况验收时就不容易翻车。我习惯在提交前跑一遍所有测试确认没有低级错误。另一个实用技巧是可视化 AST。写一个简单的递归打印函数把 AST 以缩进形式输出调试语法分析时比看嵌套元组直观得多def print_ast(node, indent0): if isinstance(node, tuple): print( * indent node[0]) for child in node[1:]: print_ast(child, indent 1) else: print( * indent str(node))最后说一个血泪经验不要等到所有模块写完再联调。词法分析写完后立刻用真实代码测试语法分析写完后立刻接上词法分析的输出测试语义分析和代码生成同理。每步都验证问题定位范围就小得多。我见过太多同学词法分析里有个隐藏 bug直到代码生成阶段才发现回头排查花了三倍时间。希望帮到你。本文还有配套的精品资源点击获取