简介面向编译原理课程实验的一份完整报告依托 Engintime CP Lab 集成环境覆盖从正则表达式到 NFA 的转换以及使用 Lex 自动生成扫描程序两大核心任务适合正在完成同类实验、需要理解实现原理或撰写实验报告的本科生参考。资源为单个 doc 文档体积 1.75MB按实验环境使用、正则到 NFA 转换、Lex 扫描程序生成三部分展开系统梳理了入口程序、正则转后缀、NFA 片段栈等核心模块的作用解释了 re2post、post2nfa、CreateNFAState 等关键函数的设计思路并完整记录在 CP Lab 中生成项目、处理语法错误及观察点调试的过程。已有 1471 人浏览学习报告步骤清晰、细节完整既可用于对照检查自己的实现也可作为实验报告写作和编译器前端复习的参考资料。1. 编译原理 CP lab 实验报告先搞清楚这份报告到底让你交什么到了学期末编译原理CP lab实验报告.doc几乎是计算机专业通用的问候语。这份报告不是让你把课堂 PPT 抄一遍而是要把词法分析、语法分析、语义分析这三层编译器前端完整走一遍并且把每一步的设计取舍写成可读的东西。它适合两类人一类是正在赶实验、需要知道报告里必须有实打实的内容才能过查重和答辩的学生另一类是工作后想补编译基础、拿实验题当迷你项目练手的开发者。报告本身不要求你写出惊为天人的编译器但要求你讲清楚从字符串到 token从 token 到语法树每一步做了哪个决策为什么。2. CP lab 的四个标准实验词法、语法、语义报告里的重点考核项2.1 词法分析实验正则到 NFA/DFA 的落地写法词法分析是 CP lab 里最容易拿分、也最先卡住人的一环。实验要求通常是读入字符串识别整数、浮点数、标识符、关键字、运算符和括号输出 (类型, 值, 行号) 的 token 流有些老师还要求统计符号表。原理层面你要在报告里写清楚两件事第一为什么用正则表达式描述单词第二怎么从正则表达式构造 NFA、再确定化为 DFA、再最小化。但在实际 lab 里除了少数学校强制用 Flex大多数人只用两种选择手写状态机或者直接用一个循环做模式匹配。我的建议是报告原理部分认真写三态模型NFA、DFA、最小化代码部分却不必真的去写子集构造——你只需要把状态转换图画出来然后在代码里用一个直观的逐字符扫描流程实现最后拿两种结果做对比。这么做的理由很简单子集构造算法是理解型考点不是工程型交付交一个你自己都看得懂的状态机代码答辩时不会一问就慌。最小可落地的词法分析流程是四步跳过空白和注释在当前位置尝试匹配最长的合法 token分类并记录值更新行号与错误信息。有一个隐蔽的坑叫最长匹配与规则优先不一致比如 else 和 elsex 在同一个程序里如果你按遇到 e 就当成标识符的短匹配走else 这个关键字就丢了正确写法是先收集完整的最长字母序列再在关键字表里查是否存在。报告里如果能把这一条写成实验现象 → 原因 → 修正的小段落比单独贴一百行代码更能拿分因为老师最想看到的就是你踩过这个坑。2.2 语法分析实验LL(1) 与 LR(1) 选型报告里要写清楚的理由语法分析是 CP lab 的硬骨头因为这里第一次出现理论好像懂了、代码无从下手的局面。常见实现路线有三条手写递归下降、用预测分析表做 LL(1)、用 Bison/Yacc或 JavaCC做 LALR(1)。报告一定要有一个小节专门讲选型依据而不是默认一种方案一行不解释。我的经验是如果你写的是 C/Java/Python优先手写递归下降因为代码可读性好、出错好调试而且刚好避开 LL(1) 分析表的构造细节如果你想表现对形式化方法的掌握就补一张预测分析表和一个 LR 冲突的案例。注意递归下降要求文法必须是 LL(1) 的变体你要在报告里展示你是如何消除左递归、提取左公因子的——这是老师查代码最爱抽查的位置。选型还要考虑实验规模如果题目只要求解析算术表达式和简单的声明语句递归下降最省篇幅如果题目要做完整的类 C 文法含 if-else、while、函数定义手写递归下降会变得很长此时用 Bison 更合适。但用 Bison 也有代价冲突归约信息你要能看懂不能把 42 个 shift/reduce conflict 直接贴进报告里当正常现象。报告里的正确姿势是写参与构建的文法共 X 个非终结符、Y 个终结符Bison 报告 2 个冲突经排查为悬空 else 引入采用优先级声明消除并把冲突消除过程写清楚。没有这句话只贴出 conflict 输出老师一眼就知道你没理解自己的文法。2.3 语义分析与中间代码生成符号表和三地址码是报告核心产出到了语义分析这一环实验报告终于从能跑走向有价值。语义分析的核心产出有两个符号表和中间代码。符号表不是简单放一个 HashMap 就完事你需要记录标识符的名字、类型、作用域深度、声明位置和引用位置。很多同学的代码在词法分析阶段已经建过一个 token 表语义阶段又建一个符号表两套东西对不上导致变量重定义和类型检查功能双双失效。报告里应该有一张表说明符号表每个字段的设计理由并画一个作用域压栈/出栈的示意这将直接证明你不是在贴玩具代码。中间代码生成的考核点通常是短路语义和类型转换。以 C 语言常见的 和 || 为例原理上要生成短路跳转的三地址码t1 a 0if_false t1 goto L1t2 b 0if_false t2 goto L1result 1goto L2L1: result 0L2: ...。如果你的实验报告里有类似这样一段完整的三地址码输出并标注了每条语句的跳转目标答辩时基本能镇住大部分同学。语义阶段还有一个老师说烂了但总有人不做的操作错误恢复。真实编译器不可能一遇到错误就停机你要在报告里写清楚错误处理策略是恐慌模式还是同步记号法以及实验里出现的三个典型语义错误变量未定义、类型不匹配、越界常量分别由哪一层捕获。2.4 实验环境与工具链Flex/Bison 和手写递归下降怎么选用什么环境完成 CP lab很多同学觉得无所谓但实验报告往往要求提供开发环境一节而这节的答法会影响老师对报告可信度的判断。常见组合是三种C Flex/Bison适合课程指定 Linux 环境特点是能接触到经典的 lex/yacc 体系但调试门槛高Java JavaCC适合面向对象基础好的同学语义动作写起来顺手Python 手写适合快速出效果、自动机代码易读但会被个别老师认为是纯调库。首选通常是 C Flex/Bison因为这个组合和教材贴合度最高但如果你的实验环境是 Windows 且没有装 GNU 工具链直接用 Python 手写也不丢人关键是在报告里说明你用了什么方法来保证可复现性比如命令、测试脚本、退出码。关于环境能跑和能复现是两回事。我检查实验报告时经常看到同学写在本机测试通过却没有任何运行参数和输入文件说明老师重新运行得到的输出和报告里的输出不一致对方连解释都解释不了。我的建议是报告里固定写清三个东西输入文件格式比如 test.c 为 C 子集支持哪些语法、运行命令比如 flex lex.lbison -d parse.ygcc lex.yy.c parse.tab.c -o cpc./cpc test.c、一组标准输入输出样例。如果报告里有 Makefile 片段更好因为 Makefile 本身就是在声明实验的构建边界。3. 把实验报告写成能答辩的文档结构、图表、代码块组织3.1 报告骨架目的、原理、设计、测试、结论五段式一份能扛住答辩的 CP lab 报告结构上遵循五段式实验目的与要求、实验原理与环境、总体设计与模块划分、测试与分析、实验总结与改进方向。很多同学的报告问题是实验原理占了六成、把编译原理教材第二章的答案整个抄进去而设计与实现只有几段废话加一堆代码。正确的篇幅分配应该是原理占两成设计占四成测试与总结占四成。关键认知是原理部分写为什么设计部分写在你的工程里具体做成什么样测试部分写怎么证明它成立三者的比例失衡会让老师根本找不到你的工作量。总体设计这一节要有层次先画一张数据流图表示源程序 → 预处理器可选→ 词法分析器 → 符号表 → 语法分析器 → 中间代码生成 → 输出的链条然后逐个模块写输入-输出-内部结构。比如词法分析模块的输入是字符流输出是 Token 序列内部维护一个当前状态变量和一个行号计数器语法分析模块的输入是 Token 序列输出是抽象语法树或直接输出三地址码内部维护一个下一个 Token指针。每个模块用一百到两百字描述配关键数据结构类名、函数签名老师就能判断你到底写了没有。最忌讳的写法是词法分析模块本模块实现了词法分析功能一句话带过或者把整个源码粘贴进代码实现小节。3.2 图表和状态转换图怎么画才不算反坑编译原理实验报告的图表要求与其它课程最大的区别是状态转换图不是示意图是交付物。词法分析报告里必须要有标识符、整数常量、关系运算符的状态转换图而且这张图要画对接受态进入接受态的路径比如整数常量从 digit 状态遇到非数字字符要回到 start 态并且回退一个字符如果这张图把回退行为画丢了老师一旦追问102abc 你怎么处理你就会当场翻车。状态转换图推荐两种画法手绘拍照清晰就行或 Graphviz 写 dot 脚本后者还能把最小化前后的 DFA 对比做出来。不推荐用 Word 自带的形状乱拼因为图元不对齐反而会被认为态度有问题。语法树parse tree / AST的图可以在报告里放两颗一颗是表达式 a b * c 的 AST一颗是 if-else 语句的 AST用来解释你的递归下降调用层次。这里有个小技巧用程序自动打印 AST每层递归输出 indent 加节点名把输出截图贴进报告比手绘图可信且省力。千万注意不要贴一堆无意义的运行截图课程报告最常见的败笔是连续六张终端截图每张只看到程序启动正确做法是贴输入文件一个、token 输出一个、语法树输出一个、错误报告一个每张旁边加两行图注说明这张图对应哪个模块、哪个测试用例。3.3 代码附录怎么贴只贴核心、注释到位、次要代码省略代码怎么收纳进报告是一个容易被低估的加分项。原则是附录只放核心代码次要的错误处理、打印函数用省略表达正文里出现的代码必须和附录一致不能两份代码版本对不上。我的经验是代码块按模块切分每个模块开头给一个两行说明本文件是什么、编译命令是什么。代码行数控制在三百行以内太长了老师不想看如果你真的是千行工程把 Makefile 和目录结构树贴出来再挑三个关键函数比如词法分析器的 nextToken、语法分析器的 parseExpression、语义分析的 typeCheck完整给出。这样保证报告厚度够又不显得在凑页数。代码里的注释也要讲究不是每行都写// 加 1那种而是在函数签名上方写职责、在分支条件处写为什么这么判定。比如 nextToken 里读到/时要决定是不是行注释开头注释应当写读到 /需要 peek 下一个字符判断是 / 还是 *这种注释能直接向老师展示你对边界情况的思考。另外附录里的代码不要用截图代替文本原因有两个一是查重系统处理不了截图二是老师想复制到本机验证时截图完全不可用。凡是被要求提交源码的实验报告附录给文本另外单独传一个 zip。4. 从零跑通一个最小词法语法分析器可复现的 CP lab 最小工程4.1 用 Python 手写一个能交差的最小词法分析器下面这个例子对应 CP lab 中手工实现词法分析器的题目我用 Python 写一个不依赖第三方库的最小版本。它只识别数字、标识符、加减乘除运算符、括号、分号并输出 token 流。代码尽量保持形状和你在报告里画的状态转换图一一对应。import re class Lexer: def __init__(self, text: str): self.text text self.pos 0 self.line 1 self.tokens [] TOKEN_SPEC [ (NUM, r\d(\.\d)?), (ID, r[A-Za-z_][A-Za-z0-9_]*), (OP, r[\-*/!]), (LPAR, r\(), (RPAR, r\)), (SEMI, r;), (WS, r\s), ] def next_token(self): while self.pos len(self.text): # 按规则表顺序尝试匹配数字分支额外做混合字符检查 for token_type, pattern in self.TOKEN_SPEC: regex re.compile(pattern) match regex.match(self.text, self.pos) if match: value match.group(0) self.pos match.end() if token_type WS: self.line value.count(\n) break # 数字后面紧跟字母或下划线属于非法标识符如 123abc if token_type NUM and self.pos len(self.text): ch self.text[self.pos] if ch.isalpha() or ch _: raise SyntaxError( fline {self.line}: 无效的数字/标识符混合 {value}{ch}...) self.tokens.append((token_type, value, self.line)) break else: raise SyntaxError(fline {self.line}: 无法识别的字符 {self.text[self.pos]!r}) return self.tokens if __name__ __main__: code x 12.5 34 * (y - 1); ts Lexer(code).next_token() for t in ts: print(t)实现逻辑说明next_token 内部不断用各规则的编译正则从当前 pos 尝试匹配匹配成功后推进 pos并把 (类型, 值, 行号) 追加到 tokens空白规则匹配时不产出 token只更新行号。关键点在 for...else 结构for 尝试匹配所有 token 规则如果某个规则命中就 break如果所有规则都没命中else 分支抛 SyntaxError 并提示位置。这个结构直接对应词法分析里的无法识别字符分支。特别说明一下 NUM 分支里的混合字符检查正则匹配到 123 之后如果下一个字符是字母或下划线立即报数字/标识符混合这对应状态转换图中数字接收态遇到非法后继字符的边界处理。参数说明若要支持关键字 int/float可以在类里加一个集合KEYWORDS {int, float, if, while}然后在 ID 分支加一层if value in KEYWORDS: token_type KEYWORD。如果要支持 C 风格的//注释在 TOKEN_SPEC 增加(COMMENT, r//.*)并在命中时直接忽略。有一点要特别注意正则匹配顺序里 NUM 必须放在 ID 之前否则像 123abc 这种字符串会被 ID 规则吃掉即使 ID 规则禁止数字开头也要保留 NUM 分支后的非法字符检查否则 123abc 会被拆成两个 token 而不是报错这是我调试时踩过的第一个坑。4.2 递归下降解析表达式不带优先级和结合性的解析器会翻车光有 token 流不够CP lab 一般要求做语法分析。下面用递归下降法解析表达式 赋值语句的文法statement → ID expr ;expr → term ( (|-) term )*term → factor ( (*|/) factor )*factor → NUM | ( expr )。class Parser: def __init__(self, tokens): self.tokens tokens self.index 0 def peek(self): return self.tokens[self.index] if self.index len(self.tokens) else None def consume(self, expected_type): tok self.peek() if tok and tok[0] expected_type: self.index 1 return tok raise SyntaxError(f期望 {expected_type}实际 {tok}) def parse_statement(self): ident self.consume(ID) op self.consume(OP) if op[1] ! : raise SyntaxError(赋值语句必须使用 运算符) expr self.parse_expr() self.consume(SEMI) return (assign, ident[1], expr) def parse_expr(self): node self.parse_term() while self.peek() and 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): node self.parse_factor() while self.peek() and 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): tok self.peek() if tok and tok[0] NUM: self.consume(NUM) return (num, tok[1]) if tok and tok[0] LPAR: self.consume(LPAR) node self.parse_expr() self.consume(RPAR) return node raise SyntaxError(f非法的因子起始 token: {tok}) if __name__ __main__: lexer Lexer(x 12.5 34 * (y - 1);) parser Parser(lexer.next_token()) ast parser.parse_statement() print(ast)逻辑说明parse_expr 和 parse_term 都做了先消费一个子节点再看下一个 token 是否属于当前层的运算符这实际上是 EBNF 的 while 循环实现等价于左递归消除后的文法expr → term expr和expr → (|-) term expr | ε。好处是运算符左结合天然成立因为循环里每遇到一个运算符就把左节点当作已经算好的左侧操作数。为什么用 while 而不是递归去写 expr两种写法都正确但 while 版本对 Python 递归深度更友好而且报告里更好解释终结符驱动循环。参数说明parse_statement 里我对 OP 做了值检查必须是如果要支持x 1这种复合赋值需要扩展运算符表并在这里增加分支。准备答辩时你至少要在报告里回答三个问题如果输入没有分号会怎样、如果括号不匹配会怎样、12*3输出哪棵 AST。这三个问题分别对应代码里的异常处理和优先级分层。用(12)*3和12*3两个用例的输出对比可以直接在测试部分展示你的优先级处理是符合 C 语言规则的。4.3 测试用例和输出验证token 流和语法树怎么检查实验报告里测试部分的核心不是程序没崩而是输出正确性可验证。我建议你自己准备三组测试用例合法程序、非法语法、非法语义如果需要语义层。合法程序用一段覆盖所有运算符和嵌套括号的代码比如x 12.5 34 * (y - 1);然后打印 token 流和 AST(NUM, 12.5, 1) (OP, , 1) (NUM, 34, 1) (OP, *, 1) (LPAR, (, 1) (ID, y, 1) (OP, -, 1) (NUM, 1, 1) (RPAR, ), 1) (SEMI, ;, 1) (assign, x, (binop, , (num, 12.5), (binop, *, (num, 34), (binop, -, (id, y), (num, 1)))))把这段输出原样贴进报告并在旁边写一行判断AST 中 * 的父节点是 与 C 语言优先级一致。非法语法用例选一个最常见的x 1 ;期望在 parse_term 层抛出 SyntaxError。报告里展示错误发生在第几行、错误消息是什么比展示正确运行更能反映调试能力。最后再给一个边界用例空文件、只有分号、只有注释如果支持注释。这些用例不是越多越好而是每个用例对应一种你可能写错的路径老师提问时通常也是按这些路径问的。5. CP lab 避坑报告和代码里最容易翻车的五个点5.1 悬空 else 导致语法分析器二义现象语法分析器在处理if (a) if (b) c1; else d2;时报语法错误或者结果树的归属和想象中不一样。原因绝大多数语言的 if-else 文法天生二义——else 既可以属于内层 if 也可以属于外层 if如果不做约束递归下降/预测分析器按先匹配到的分支处理得到的语义就不对。解决报告里明确声明采用最近匹配规则即 else 必须匹配最近的未配对 if在递归下降实现中每个 if 分支在解析 else 子句之前先把当前 token 上下文保存好遇到 else 时直接附加给最近的 if 节点。如果使用 Bison就写一句对 if-else 文法声明优先级或直接消除二义并把预报告中的 conflict 数量变化写进实验记录。5.2 左递归没消除递归下降无限递归现象运行语法分析器输入一个合法表达式程序直接 RecursionError 或段错误。原因直接把课本文法抄进代码比如expr → expr term | term第一个产生式右边又出现 exprparse_expr 第一步又调用 parse_expr形成无限循环。解决在报告里必须有一段消除左递归的过程展示例如把expr → expr term | term改写为expr → term expr、expr → term expr | ε更工程化的方案是像 4.2 节那样用 while 循环代替显式的 ε 产生式。这个坑是最容易让新手从报告只写原理变成报告里有真实现的契机。5.3 数字与标识符混合输入被错误拆包现象输入123abc或elseif得到的结果不是报错而是把123abc当成整数 123 加标识符 abc或者把elseif拆成关键字 else 加标识符 if。原因正则规则各自独立匹配没有做当前正在构成一个 token的统一状态管理也没有做最长匹配与关键字表配合。解决词法分析器不要按规则优先级简单蛮干要在读到数字后立即检查下一个字符是否仍属于数字集合如果在数字后遇到字母直接报非法标识符/数字混合。实现方法是把状态机的接收态和回退逻辑显式写出来数字串结束于非数字字符且该字符不是分隔符时做非法字符检查。在报告里放123abc的报错截图是这类题目最有说服力的证据。5.4 测试用例太少答辩一问就露馅现象报告里只有一个 test.c跑了输出正常感觉实验完成老师随便问括号不匹配会产生什么错误除数为 0 谁检查while 条件里写赋值语句允不允许当场答不上来。原因测试用例不是为了跑通设计的而是为了覆盖每个语法规则的边角情况。解决按三类准备测试脚本normal、boundary、error三类各不少于五个用例。boundary 里放空文件、只有注释、超长标识符、最大整数、嵌套一百层括号error 里放缺少分号、括号不匹配、非法数字混合、未定义变量。在每个用例里写一行预期输出运行后对照。报告里只选三到五个最有代表性的展开剩余放在附录或 zip 里。这个习惯能让你在答辩时对任何如果...会怎样的问题都接得住。5.5 报告把设计思路当成名词解释现象报告里写词法分析是指将字符序列转换为记号序列的过程递归下降分析是一种自顶向下的分析方法大段照抄教材没有一句属于你自己的工程。原因写报告的人没有真正把实验当工程而是当作文科作业在凑字数。解决设计部分一律用我采用了什么结构 为什么 在哪个函数里体现的句式比如我采用优先级分层实现表达式文法parse_expr 调用 parse_termparse_term 调用 parse_factor从而保证乘除高于加减。老师想从报告里看到的是你的决策记录不是复述教材。以后每写一个实验报告都问自己一句这一段去掉之后报告是不是就不完整了如果去掉完全不影响那它就不该存在。6. 报告交了之后还能用它长出什么从最小分析器到可验证的小编译器如果你做到这一步手里的东西其实已经是一个可扩展的编译器前端别再把它当一次性作业。我建议你做一件低成本高回报的事把 4.1 和 4.2 的 Python 代码绑成一个脚本再用 README 记录输入输出约定这样答辩时可以直接当场演示而不是翻阅报告如果还有余力更好的方向是给语法分析器加一个简单的中间代码生成层。目标不是写 LLVM而是把表达式输出成三地址码并做基本块划分比如对x 12.5 34 * (y - 1);生成t1 34 * (y - 1) t2 12.5 t1 x t2然后对比你手算的结果把对比表放进报告附录。具体做法是写一个继承 Parser 的 CodeGen 类在 parse_expr 返回 AST 之后做后序遍历每次遇到 binop 就分配一个临时变量并输出指令。这里值得注意的坑是临时变量编号要全局唯一否则两个表达式共用 t0 会把数据覆盖。我的习惯是用一个 self.temp_count每次需要临时变量时自增生成 t0、t1...并且每个语句结束后清理临时变量池防止长期运行内存膨胀。这个三地址码输出可以作为全实验报告运行成果部分的压轴内容比单独发 token 流有说服力得多。这段经历也让我养成了一个习惯以后接触任何编译相关的工具链从 grep 的正则到前端构建工具都下意识想它的词法/语法层是怎么组织的。实验报告本身可能只会被判分一次但这个把源文件变成结构化数据的思考方式会一直留在你脑子里。希望这份从零到能交差的拆解能帮到你至少让你在提交那份编译原理CP lab实验报告.doc之前心里清楚哪些内容是被认真做出来、能经得住当场提问的。本文还有配套的精品资源点击获取