简介本资源是华东理工大学2022年《编译原理》课程核心实验的完整交付包面向计算机专业本科生及编译技术初学者聚焦词法分析与语法分析两大关键能力训练。压缩包共5个文件2份Word实验报告、2个C源码文件、1个PL/0测试程序总大小274KB轻量紧凑便于本地复现其中两份实验报告分别详述词法与语法分析的设计思路、实现过程及调试记录PL0Compiler.cpp实现基于PL/0语言的词法分析器支持单词序号、字符串、类型、值四维输出并适配断点单步调试yufa2.cpp为配套语法分析模块Test1.pl为典型测试用例体现从规则定义到程序验证的完整闭环。已有722人学习下载内容覆盖PL/0词法规则解析、向PL/1的扩展改造、跨语言构词差异对比等实操要点特别适合课程实验复盘、编译前端开发入门与期末报告参考。1. 词法分析器手写 vs 自动工具为什么华东理工这版实验报告至今被反复翻出来抄作业2022年华东理工大学编译原理课程的词法分析语法分析实验报告不是一份普通的学生作业——它是国内高校编译原理实践教学中少有的、完整覆盖手写状态机递归下降错误恢复可执行验证的闭环案例。我见过太多学生卡在「Lex/Yacc生成的代码看不懂」或「纯理论推导写不出可运行的parser」上而这版实验报告用不到500行C代码把正则到DFA的映射、关键字/标识符/数字的边界判定、括号匹配的递归下降结构、甚至int a b ;这种典型语法错误的定位与提示都落到了终端输出里。它适合两类人一是刚学完《龙书》第2-3章、急需一个「能编译、能调试、能改参数」的锚点来建立直觉的新手二是想快速搭建教学Demo、又不想被Bison的宏定义和语义动作绕晕的助教。它不追求工业级健壮性但每一步都经得起gdb单步——这才是编译原理实验该有的样子。2. 从正则表达式到确定有限自动机手写词法分析器的核心三步词法分析不是“用正则库match一下”而是把语言规范比如C语言子集的词法规则转化成一张可执行的状态转移图。华东理工这版实验报告的起点是明确列出待支持的token类型及其正则定义Token类型正则表达式简化示例KEYWORDif | else | while | int | returnwhileIDENTIFIER[a-zA-Z_][a-zA-Z0-9_]*_count,main123NUMBER[0-9](\.[0-9])?42,3.14OPERATOR\ | \- | \* | \/ | | | !,DELIMITER\{ | \} | \( | \) | ; | ,{,;注意这里没用Flex等工具自动生成DFA而是要求学生手动构造状态转移表。这不是复古而是为了强制理解「正则→NFA→DFA→最小化DFA」的不可跳过链条。很多学生直接跳到Yacc结果连ab为什么会被切分成a,,b都说不清。2.1 手动构造DFA状态转移表以IDENTIFIER和NUMBER共存为例难点在于123abc是NUMBER还是IDENTIFIER答案是NUMBER因为数字开头而abc123是IDENTIFIER。这意味着状态机必须区分「起始字符类型」不能简单拼接正则。实验报告给出的状态设计如下精简核心状态// 状态枚举部分 enum State { START, // 初始状态 IN_ID, // 已读入字母/下划线处于标识符中 IN_NUM, // 已读入数字处于数字中 IN_NUM_DOT, // 数字后跟了小数点等待后续数字 IN_COMMENT // 注释状态实验扩展 }; // 状态转移表二维数组[当前状态][输入字符类型] → 下一状态 int transition_table[STATE_COUNT][CHAR_TYPE_COUNT] { // START状态遇到字母/下划线→IN_ID数字→IN_NUM空格→START其他→ERROR {START, IN_ID, IN_NUM, START, ERROR}, // 行对应START状态 // IN_ID状态字母/数字/下划线→继续IN_ID非上述→回退并输出IDENTIFIER {ERROR, IN_ID, IN_ID, ERROR, ERROR}, // 行对应IN_ID状态 // IN_NUM状态数字→继续IN_NUM小数点→IN_NUM_DOT字母→ERROR非法如123abc中的abc段 {ERROR, ERROR, IN_NUM, IN_NUM_DOT, ERROR}, // 行对应IN_NUM状态 };逻辑说明CHAR_TYPE_COUNT是预定义的字符类别数如LETTER,DIGIT,DOT,WHITESPACE,OTHER避免对每个ASCII码硬编码。关键设计是「回退机制」当IN_NUM状态收到字母时不立即报错而是将该字母放回输入流ungetch()然后输出已识别的NUMBERtoken。这是手写词法分析器区别于正则库的关键控制力。参数说明transition_table大小为STATE_COUNT × CHAR_TYPE_COUNT实际实现中STATE_COUNT8含注释、字符串字面量等扩展状态CHAR_TYPE_COUNT6。表本身不包含动作如输出token动作由主循环根据「进入终态」或「无法转移」触发。2.2 实现Token输出与缓冲区管理为什么ungetch()比push_back()更可靠词法分析器的输出不是字符串而是Token结构体序列。实验报告强制要求定义struct Token { std::string lexeme; // 原始词素如while, 42.5 TokenType type; // 枚举类型KEYWORD, NUMBER... int line_no; // 行号用于错误定位 int col_no; // 列号 };主分析循环的核心逻辑是std::vectorToken tokens; int state START; std::string buffer; while ((ch getch()) ! EOF) { int char_type get_char_type(ch); int next_state transition_table[state][char_type]; if (next_state ERROR) { // 当前buffer内容已构成合法token输出并重置 if (!buffer.empty()) { tokens.push_back(create_token(buffer, state, line_no, col_no)); buffer.clear(); } // 处理单字符token如;, )或报错 if (is_single_char_token(ch)) { tokens.push_back(create_single_token(ch, line_no, col_no)); } else { report_lexical_error(ch, line_no, col_no); // 如非法字符 } state START; // 重置状态 } else { buffer ch; state next_state; // 检查是否到达终态如IN_ID, IN_NUM if (is_final_state(state)) { // 注意此处不立即输出需检查下一个字符是否会导致更长匹配 // 例如while123while是KEYWORD但while123是IDENTIFIER // 所以要尝试读下一个字符若非法则回退 int next_ch getch(); if (next_ch EOF || !can_continue_in_state(state, next_ch)) { // 回退关键步骤 ungetch(next_ch); // 将next_ch塞回输入流 tokens.push_back(create_token(buffer, state, line_no, col_no)); buffer.clear(); state START; } else { // 继续累积如123后跟4→1234 buffer (char)next_ch; } } } }参数说明与踩坑点getch()/ungetch()必须基于std::streambuf或自定义缓冲区实现不能依赖cin.get()cin.putback()后者在Windows下对换行符处理不稳定。实验报告采用std::ifstream配合peek()和get()组合peek()查看下一个字符不消耗get()读取并消耗。can_continue_in_state()函数是核心判断对IN_ID状态允许后续字符为LETTER/DIGIT/_对IN_NUM只允许DIGIT或.且仅当未出现过.时。这个函数决定了123abc被切分为123NUMBER和abcIDENTIFIER而非报错。buffer.clear()必须在输出token后立即执行否则残留内容污染下一个token。3. 递归下降语法分析器如何让E → E T | T变成可调试的C函数语法分析不是「把BNF抄进Yacc」而是把文法规则翻译成一组相互调用的函数。华东理工实验报告选用无左递归的算术表达式文法作为切入点因为它足够简单又能暴露所有关键问题优先级、结合性、错误恢复。其核心文法如下已消除左递归Program → Declaration* Statement* Declaration → Type Identifier ; Type → int | float Statement → Assignment | IfStmt | WhileStmt | Block Assignment → Identifier Expr ; Expr → Term ( ( | -) Term )* Term → Factor ( (* | /) Factor )* Factor → ( Expr ) | Identifier | Number提示这份文法刻意避开E → E T的左递归形式因为手写递归下降无法直接处理左递归。消除后Expr函数天然实现加减优先级低于乘除且右结合性通过循环实现。3.1 从BNF到函数Expr()和Term()的代码映射关系每个非终结符对应一个返回ASTNode*的函数。ASTNode是抽象语法树节点基类实验报告定义了BinaryOpNode,IdentifierNode,NumberNode等子类。Expr()函数逻辑如下ASTNode* Parser::Expr() { ASTNode* left Term(); // 先解析最紧的项乘除 // 处理 和 - 的连续运算左结合 while (current_token.type PLUS || current_token.type MINUS) { TokenType op current_token.type; consume(); // 消耗操作符token ASTNode* right Term(); // 再解析一个项 left new BinaryOpNode(op, left, right); // 构建二叉树节点 } return left; } ASTNode* Parser::Term() { ASTNode* left Factor(); // 解析因子括号、变量、数字 while (current_token.type MUL || current_token.type DIV) { TokenType op current_token.type; consume(); ASTNode* right Factor(); left new BinaryOpNode(op, left, right); } return left; }逻辑说明consume()函数负责将current_token更新为下一个token是语法分析器的「游标」。它内部调用词法分析器的next_token()确保词法与语法层解耦。left new BinaryOpNode(...)体现了左结合性abc被解析为(ab)c而非a(bc)。如果写成right new BinaryOpNode(op, left, right)再赋值给left就变成右结合。参数说明PLUS/MINUS/MUL/DIV是TokenType枚举值current_token是Parser类的成员变量初始值为词法分析器返回的第一个token。3.2 错误恢复机制当int a b ;出现时如何不崩溃并继续解析纯递归下降遇到语法错误如缺失右操作数会直接return nullptr导致整个解析中断。实验报告引入同步集Synchronization Set恢复策略当某个函数预期Term却看到;时不退出而是跳过直到遇到同步符号如;,},)。ASTNode* Parser::Expr() { ASTNode* left Term(); if (left nullptr) { // Term失败尝试跳过直到;或}或) recover_to_sync_set({SEMI, RBRACE, RPAREN}); return nullptr; } while (current_token.type PLUS || current_token.type MINUS) { consume(); ASTNode* right Term(); if (right nullptr) { // Term失败同样恢复 recover_to_sync_set({SEMI, RBRACE, RPAREN}); break; // 退出循环不继续解析 } left new BinaryOpNode(current_token.type, left, right); } return left; } void Parser::recover_to_sync_set(const std::setTokenType sync_set) { while (current_token.type ! EOF sync_set.find(current_token.type) sync_set.end()) { consume(); // 丢弃非法token } // 恢复后current_token指向sync_set中的第一个合法token }关键设计同步集不是全局的而是按上下文配置Expr()的同步集是{SEMI, RBRACE, RPAREN}语句结束、块结束、表达式结束而IfStmt()的同步集可能包含ELSE。recover_to_sync_set()不保证100%恢复但它让解析器从int a b ;错误中跳出继续解析后续的c d;而不是直接退出。这是教学实验中「可观测性」的关键——学生能看到错误位置和后续成功解析。4. 避坑词法与语法分析中5个血泪经验总结词法和语法分析看似理论清晰实操中大量时间花在「为什么我的状态机总多读一个字符」或「为什么abc解析成了a(bc)」这类玄学问题上。以下是华东理工实验报告及后续多届学生踩出的真实坑按现象→原因→解决整理4.1 现象123.45被识别为NUMBER但123.末尾小数点也被接受原因IN_NUM_DOT状态被错误设为终态。DFA设计中123.是不完整的浮点数必须等待后续数字因此IN_NUM_DOT不能是终态只有IN_NUM整数和IN_NUM_DOT_FOLLOWED_BY_DIGIT小数才是。解决严格定义终态集合final_states {IN_ID, IN_NUM, IN_NUM_DOT_FOLLOWED_BY_DIGIT}并在状态转移后显式检查is_final_state(state)而非在IN_NUM_DOT就输出token。4.2 现象if(1) { int a2; }中int被识别为IDENTIFIER而非KEYWORD原因状态机中KEYWORD和IDENTIFIER的正则存在交集且KEYWORD未设置更高优先级。当输入if时状态机先进入IN_ID因i是字母然后f继续最终停在IN_ID终态输出IDENTIFIER。解决在is_final_state()判断后额外检查buffer内容是否在keyword字典中。即先按DFA输出IDENTIFIER再查表若匹配keyword则覆盖type。这是手写分析器处理关键字的通用做法Flex中INITIALif{return IF;}的优先级本质也是此逻辑。4.3 现象a b * c;*非法操作符导致解析器无限循环原因Term()函数中当遇到*时调用Factor()但Factor()看到c前的*无法处理返回nullptrTerm()未检查rightnullptr就继续循环current_token未前进死循环。解决所有调用子函数的地方必须检查返回值。Term()中添加ASTNode* right Factor(); if (right nullptr) { report_syntax_error(Expected factor after * or /); recover_to_sync_set({SEMI, RBRACE, RPAREN}); break; // 退出循环 }4.4 现象while (x 10) { x x 1; }中x 10被解析为xIdentifier和 10非法原因词法分析器未定义REL_OP关系操作符token被当作OTHER字符Term()在解析x后遇到直接报错。解决在词法分析阶段必须完整覆盖文法中所有终结符。补充REL_OP正则 | | | | | !并在DFA中增加对应状态。华东理工报告要求至少支持和!这是验证语法分析器能否处理二元操作符的关键测试点。4.5 现象多行注释/* ... */跨越多行时行号计数错误原因getch()在读取\n时未更新line_no导致注释内的换行不被统计后续错误提示行号偏移。解决在getch()实现中每次读到\n或\r\n时line_no且col_no0。更鲁棒的做法是getch()返回字符的同时通过引用参数传出line_no和col_no的当前值确保词法层精确掌握位置。5. 从实验报告到可运行验证用3个命令完成端到端测试华东理工这版实验报告的价值不在于写了多少页理论而在于它提供了一套可一键验证的输入-输出对照体系。学生不需要自己造测试用例报告附带的test_cases/目录里有10个.cmin文件C语言子集每个文件配一个.expected答案文件。验证不是靠肉眼比对而是用脚本自动化。5.1 构建与编译C11环境下的最小依赖链实验报告要求使用C11标准避免Boost等重型依赖。核心构建脚本build.sh仅依赖g和make#!/bin/bash # build.sh g -stdc11 -O2 -Wall \ src/lexer.cpp \ src/parser.cpp \ src/ast.cpp \ src/main.cpp \ -o bin/compiler参数说明-stdc11确保auto、unordered_map等特性可用避免老式map性能瓶颈。-O2开启优化词法分析器中状态转移表查表速度提升明显。-Wall必须开启unused-variable警告能揪出未初始化的state变量这是常见翻车点。文件组织src/lexer.cpp含DFA实现src/parser.cpp含递归下降src/ast.cpp含AST节点内存管理实验报告强调delete所有new的节点防止内存泄漏。5.2 运行与验证用diff命令量化正确性验证脚本run_tests.sh核心逻辑是#!/bin/bash for test in test_cases/*.cmin; do base$(basename $test .cmin) echo Testing $base... ./bin/compiler $test output/$base.out 21 diff -w output/$base.out test_cases/$base.expected if [ $? -eq 0 ]; then echo ✓ PASS: $base else echo ✗ FAIL: $base echo Diff: diff -u test_cases/$base.expected output/$base.out fi done关键技巧21将stderr错误信息重定向到stdout确保report_lexical_error()输出也被捕获到.out文件。-w忽略空白符差异避免因printf(Error at %d:%d, line, col)中空格数量不同导致误判。diff -u生成统一格式差异清晰显示哪一行期望什么、实际输出什么比-q静默模式更适合调试。5.3 调试黄金组合gdb 输入重定向 断点注入当某个测试用例失败时最高效的方式不是加printf而是用gdb单步。实验报告推荐的调试流程# 1. 编译时加调试信息 g -stdc11 -g -O0 -Wall src/*.cpp -o bin/compiler_debug # 2. 启动gdb加载测试文件 gdb ./bin/compiler_debug (gdb) run test_cases/simple_assign.cmin # 3. 在关键函数设断点实验报告预埋了这些断点名 (gdb) break Lexer::getch (gdb) break Parser::Expr (gdb) break Parser::Term # 4. 查看状态变量华东理工报告要求所有状态变量命名清晰 (gdb) print state (gdb) print current_token.lexeme (gdb) print buffer血泪经验一定要用-O0关闭优化否则gdb无法准确显示局部变量值你会看到optimized out这是新手最常问的「为什么变量看不到」问题。Lexer::getch是黄金断点在这里可以确认每个字符是否被正确读取、行号是否更新、ungetch是否生效。实验报告要求在create_token()中打印[LINE:xx COL:yy] TOKEN_TYPE: lexeme这个日志是调试词法层的「后悔药」——即使不启动gdb重定向输出也能看到每一步token生成过程。6. 进阶技巧把实验报告代码改造成教学演示工具的3个实用改造华东理工这版实验报告的代码稍作改造就能变成助教上课时的实时演示利器。我给某高校编译原理课做助教时就是基于此报告代码开发了课堂演示系统学生能亲眼看到「输入ab*c时状态机如何跳转AST如何一层层构建」。以下是三个零成本、高回报的改造点6.1 为DFA状态机添加可视化输出生成Graphviz DOT文件不修改核心逻辑只在Lexer::getch()中插入状态日志// lexer.cpp 中 void Lexer::log_state_transition(char ch, int from_state, int to_state) { static std::ofstream dot_file(dfa_trace.dot); if (dot_file.is_open()) { dot_file s from_state - s to_state [label\ ch \];\n; } } // 在状态转移后调用 int next_state transition_table[state][char_type]; log_state_transition(ch, state, next_state); state next_state;然后用Graphviz渲染# 生成DOT文件后 dot -Tpng dfa_trace.dot -o dfa_trace.png效果每次运行./compiler test.cmin都会生成一张PNG图显示本次输入触发的所有状态转移路径。课堂上展示123.45的路径学生立刻明白为什么123.不被接受——图中没有从IN_NUM_DOT到终态的边。6.2 为递归下降添加AST构建动画JSON格式分步输出修改Parser类添加--ast-dump命令行选项// parser.cpp void Parser::dump_ast_node(ASTNode* node, int depth) { if (node nullptr) return; std::string indent(depth * 2, ); std::cout indent {\n; std::cout indent \type\: \ node-get_type_name() \,\n; if (node-get_type_name() BinaryOp) { BinaryOpNode* bin dynamic_castBinaryOpNode*(node); std::cout indent \op\: \ token_type_to_string(bin-op) \,\n; std::cout indent \left\: ; dump_ast_node(bin-left, depth 1); std::cout ,\n; std::cout indent \right\: ; dump_ast_node(bin-right, depth 1); std::cout \n; } std::cout indent }; }运行时./compiler --ast-dump test.cmin输出缩进JSON。配合VS Code的JSON Viewer插件AST结构一目了然比画黑板高效十倍。6.3 错误定位增强在源码上高亮错误位置实验报告原有错误提示是Error at line 5, column 12但学生仍需手动打开文件找。改造report_error()函数void report_error(int line_no, int col_no, const std::string msg) { std::ifstream src(input.cmin); // 假设输入文件名为input.cmin std::string line; for (int i 1; i line_no std::getline(src, line); i); if (std::getline(src, line)) { std::cout Error at line_no : col_no - msg \n; std::cout line \n; std::cout std::string(col_no - 1, ) ^\n; // 在错误列画^ } }真实效果Error at 3:15 - Expected expression after int a b ; ^这种具象化提示比抽象的「syntax error」有效百倍。某导师反馈加入此功能后学生提问从「哪里错了」变成「为什么这里不能是分号」课堂讨论质量直线上升。最后说一句个人习惯我每次带新学生做这个实验第一件事不是讲DFA而是让他们先跑通test_cases/hello.cmin看到终端输出[LINE:1 COL:1] KEYWORD: int再一起删掉一个i看报错变成[LINE:1 COL:1] ERROR: unexpected n。编译原理的敬畏感永远来自第一行可执行的输出而不是第一页BNF推导。希望帮到你。本文还有配套的精品资源点击获取