编译原理课设报告：词法分析状态图与递归下降语法分析详解

简介2022年华东理工大学编译原理课程实验材料包围绕词法分析与语法分析两大实验环节整理适配本科生实验复习与报告撰写也适合自学PL/0编译器实现的读者参考。压缩包内含5个文件以2份doc实验报告为主体另配2份cpp源程序及1份pl测试用例总大小274KB。目前已有722人学习/下载资料热度较好。报告完整记录了词法分析实验从编写PL/0测试用例、断点运行PL0Compiler到修改标识符构词规则生成PL/1语言并编写新测试用例的实践过程语法分析部分则有对应的yufa2.cpp源程序便于对照算法与代码实现。读者可通过源码理解单词序号、单词值、单词类型等字段的输出原理也可从PL/1扩展案例中体会不同语言词法规则的差异适合在实验前预习或撰写报告时参考。1. 这份华东理工编原实验报告写给所有课设周才开始焦虑的人编译原理课设最折磨人的不是代码本身而是你明明写了三天的代码打开 Word 却不知道实验报告该怎么写。特别是当你要把词法分析器的状态图画出来、把语法分析器的 FIRST 集和 FOLLOW 集推导过程写清楚的时候。这份2022年华东理工大学的《编译原理词法分析语法分析实验报告》好就好在它把课设要求的每个环节都做成了一份能直接对照的工程样例。报告里不只是贴代码它把词法分析从 token 设计到状态图再到 DFA 实现的推导路径写完整了语法分析则从文法设计到递归下降函数再到冲突消解每一步都有对应的标注和说明。你在网上能找到大量源码但很难找到一份告诉你“为什么这样设计、状态图为什么长这样、测试用例为什么要这么写”的报告。这份资源适合三类读者正在写编译原理课设的学生、准备把课设报告写到能被老师认可的挣扎者、以及想通过一份完整样例快速复盘词法分析和语法分析核心流程的从业者。2. 拆报告之前先看骨架词法分析与语法分析的课设报告到底在写什么2.1 报告封面之外的三块硬内容token表、状态图、文法设计一份能拿到高分的编译原理实验报告重点不在封面和实验环境而在三块硬内容。第一块是 token 记号设计表也就是你的词法分析器可以识别哪些单词。第二块是词法分析状态图也就是把 token 识别过程画成自动机。第三块是语法分析的文法定义比如用 EBNF 或巴克斯范式写出表达式、赋值语句、声明语句的构成规则。华理这份报告在这三块上都有完整呈现而且每块都配了对应代码不是那种只写结果不写过程的报告。先看 token 设计。报告里常见的划分方式是五类保留字关键字、标识符、常量、运算符、界符。注意保留字和标识符是有交集的比如if、else既是保留字从词法结构上说它们也是字母串处理方式通常是在识别出字母串后查保留字表而不是在状态图里为每个关键字单独画分支。这个设计决策直接决定后续代码的写法也是报告里值得细看的第一个知识点。华理报告中 token 表会给每类 token 一个编号比如TOKEN_INT、TOKEN_IDENTIFIER、TOKEN_PLUS这个编号会一直沿用语法分析阶段前后一致性是老师判分时很在意的一点。状态图是词法分析报告里的核心。报告中一个典型的状态图结构是这样的起始状态 0 读取首字符是字母就进入标识符收集状态是数字进入数字收集状态是运算符则根据具体的符号进入不同的状态分支。这里的关键是状态转移条件的完备性很多学生画的状态图少了字符分类的完整分支比如下划线、单引号、双引号没处理或者数字识别的浮点分支没画全。华理报告会把每个分支画到状态图边上下面再附一段代码做映射这份报告的价值就在这里——图不是摆设代码也不是独立存在的两者可以逐行对应。文法设计这块报告通常会给出一组 EBNF 规则比如程序 :: 语句 | 程序 语句 语句 :: 赋值语句 | 声明语句 | 表达式语句 表达式 :: 项 | 表达式 加法运算符 项 项 :: 因子 | 项 乘法运算符 因子 因子 :: 标识符 | 常量 | ( 表达式 )这就是后面写递归下降解析器的直接依据。报告的写法通常是先给出文法再解释为什么这样定义消除左递归之后做递归下降或者用 LL(1) 做预测分析然后把每个非终结符对应到一个函数。2.2 从这张状态图走到可运行代码DFA转程序的四条路径报告里状态图画完之后接下来就是把你设计的 DFA 转成可执行代码。这个转换过程是词法分析实验的核心工作量华理报告中给出的实现思路通常可以归纳为四种路径按工程难度从低到高分别是if-else 分支法、switch 状态分支法、表驱动法、自动生成器法。我一般会建议课设学生优先掌握 if-else 和表驱动两种。if-else 分支最直观每个状态对应一个函数或一个分支块缺点就是状态多了以后代码膨胀维护困难。表驱动法是把状态转移条件存在二维数组里用状态号和输入字符类型做索引查表代码量小但表格设计时容易出错。华理报告里用的是 if-else 和 switch 混合的方式这符合课设规模——状态数量在十几个左右不需要上自动生成器但代码结构比纯 if-else 更清晰。做代码级映射时有一个容易被忽略的点状态图里的“字符分类”不等价于单个字符判断。比如状态图里把输入字符分为“字母”“数字”“运算符”“界符”四类多数课设代码写成if (ch a ch z || ch A ch Z)这样做可以但更好的做法是一开始就写一个classify(ch)函数返回字符类别编号。这样后面如果用表驱动法查表拿类别编号直接做下标不用在每个状态里重复写字符判断区间。华理报告里在词法分析代码之前放了一个字符分类函数这个细节看起来很基础但到了语法分析阶段要处理前瞻符号lookahead的时候你会发现字符分类和 token 分类的统一设计让整个代码干净很多。报告中状态图到代码的映射还有一个时间线问题就是状态图的版本和代码的版本必须一致。很多同学代码改了图没改最后答辩时被问“这里为什么和代码不一样”直接翻车。我自己做课设时吃过这个亏从那以后我每完成一次代码重构就强制自己回过去把状态图同步更新一遍这个问题在实验报告里比代码本身更能拉开分差。3. 词法分析部分状态图怎么变成能跑的代码3.1 token表与编码设计报告里最容易忽略却决定全局的第一步读这份报告时值得带着一个追问报告里的 token 表为什么要把编号这样排以常见的 C 语言子集词法分析器为例报告设计出的 token 编号一般是这样的token 类别编号区间示例保留字1-32int、float、if、else、return标识符33id变量名、函数名常量34-38INT_CONST、FLOAT_CONST、CHAR_CONST算术运算符39-47、-、*、/、%关系运算符48-55、、、、、!逻辑运算符56-58、赋值与界符59-65、;、,、(、)、{、}这个编号顺序不是随便写的。保留字编号在最前是因为语法分析器里要用token 33判断当前 token 是否为关键字这种数值区间判断比逐个比较字符串快得多。报告里还有一个容易忽略的细节标识符统一用一个编号TOKEN_ID表示token 的字符串值存放在全局的lexeme缓冲区里而不是给每个变量名单独编号。语法分析阶段只关心“这里该不该是一个标识符”具体叫什么名字只有在生成符号表时才需要。做词法分析代码复现时token 编码直接决定后面输出的分析结果格式。华理报告里的输出格式通常是每一行“token 编号、token 字符串、所在行号、所在列号”。我第一次复现时把 token 编号和枚举类型没对齐打印出来的分析结果全部错位排查了一整晚才发现是枚举里少算了一个TOKEN_INVALID项。3.2 状态图到代码的映射if-else、switch、表驱动三种写法对比把状态图的每个状态转成代码最痛苦的是状态多了以后代码逻辑乱成一团。华理报告里的代码结构是状态转移函数 全局字符读取函数核心部分大致是这样的// 词法分析核心函数从输入流读取一个 token Token get_next_token() { int state 0; // 初始状态 char ch; // 当前读入字符 clear_lexeme(); // 清空词素缓冲区 while (1) { ch get_next_char(); // 读入下一个字符 if (ch EOF_CHAR) { if (state 0) return make_token(TOKEN_EOF, ); return get_error_token(); // 文件末尾但状态未归零报错 } switch (state) { case 0: // 起始状态按首字符分类决定分支 if (is_letter(ch)) { state 1; append_char(ch); } else if (is_digit(ch)) { state 2; append_char(ch); } else if (ch ) return make_token(TOKEN_PLUS, ); else if (ch ) { state 4; // 需要判断下一个字符是不是 append_char(ch); } else { return make_token(TOKEN_INVALID, ch); } break; case 1: // 标识符/保留字状态 if (is_letter(ch) || is_digit(ch)) { append_char(ch); } else { backtrack(); // 关键操作多读的字符要回退 return resolve_keyword_or_id(lexeme); } break; case 2: // 整数常量状态 if (is_digit(ch)) { append_char(ch); } else { backtrack(); return make_token(TOKEN_INT_CONST, lexeme); } break; case 4: // 判断 后是 还是单独赋值号 if (ch ) { append_char(ch); return make_token(TOKEN_EQ, ); } else { backtrack(); return make_token(TOKEN_ASSIGN, ); } break; } } }这段代码里有三个细节值得重点看。第一个是backtrack()也就是我们常说的“多读一个字符要回退”。比如识别完标识符abc后下一个字符是空格这时代码已经把它读走了必须把指针回退一位否则下一个 token 会丢首字符。第二个是resolve_keyword_or_id()查保留字表报告里通常是线性查找或二分查找。第三个是EOF_CHAR的处理文件读完时如果状态不是 0说明最后一个 token 被截断了一定要报错而不是静默忽略。3.3 词法分析的四个隐蔽坑最长匹配、关键字表、注释跳过与缓冲区第一个坑是最长匹配。C 语言里和是两个不同的 token状态图设计时必须走到能识别双字符运算符的分支而不是读到就立即返回。华理报告里给出的做法是在状态 0 遇到时先不返回而是设置一个待定状态读下一个字符判断是还是。这个机制我在复现报告时写错过一次状态图画的是对的但代码里提前 return 了结果被识别成和两个 token。第二个坑是关键字表的存储位置。如果每次识别完标识符都去查字符串表性能尚可但如果在状态图里为每个关键字单独加分支状态数量会爆炸。报告里是维护一个静态字符串数组keywords[]代码里用二分查找匹配。第三个坑是注释跳过。// 和 /* */ 的处理不能放在状态图主流程里否则每个 token 识别都要先判断注释起始符。常见做法是在get_next_char()里做预处理读字符时如果发现是/再读一个字符判断是/还是*然后直接跳过到行尾或匹配的*/。华理报告里专门有一小节写注释处理因为这是测试用例里很爱出题的地方。第四个坑是缓冲区边界。课设要求从文件读入源码如果一次把整个文件读进内存处理简单但内存占用大如果每次只读一行backtrack()和跨行 buffer 管理就很麻烦。报告里采用的是一次性读取整个文件到内存的方式用一个全局input_line[]和line_no变量记录行号。这种方式适合课设规模代码简单且不容易出越界问题。4. 语法分析部分递归下降与LL(1)的课设级实现4.1 文法表达式怎么设计EBNF到递归下降代码的映射词法分析完成后语法分析的输入就是 token 流。华理报告里实现的是递归下降分析器选择递归下降而不是 LR 是因为递归下降代码和文法规则一一对应报告既能写清楚推导过程代码实现也不需要额外的分析表生成工具完全适合课设展示。报告给出的文法通常会把表达式部分做左递归消除。左递归消除后表达式规则变成表达式 :: 项 { ( | -) 项 } 项 :: 因子 { (* | /) 因子 } 因子 :: ( 表达式 ) | ID | NUM注意这种写法的花括号{}表示“重复零次或多次”这正是 EBNF 比标准 BNF 更适合递归下降的地方。每个非终结符对应一个函数花括号对应的代码就是 while 循环或 if 判断。华理报告中语法分析核心代码大致是// 表达式项后跟零个或多个加减号项 void parse_expression() { parse_term(); // 先解析第一个项 while (current_token TOKEN_PLUS || current_token TOKEN_MINUS) { int op current_token; // 记录运算符后面生成中间代码时用 advance_token(); // 读下一个 token parse_term(); // 解析运算符右边的项 // 报告里这里会输出一个四元式比如 (, arg1, arg2, result) } } // 项因子后跟零个或多个乘除号因子 void parse_term() { parse_factor(); while (current_token TOKEN_MUL || current_token TOKEN_DIV) { int op current_token; advance_token(); parse_factor(); // 输出 (*, arg1, arg2, result) } } // 因子处理括号、标识符、常量三种情况 void parse_factor() { if (current_token TOKEN_LPAREN) { advance_token(); // 跳过 ( parse_expression(); // 括号内继续解析表达式 expect(TOKEN_RPAREN); // 必须匹配右括号否则报错 } else if (current_token TOKEN_IDENTIFIER) { advance_token(); } else if (current_token TOKEN_INT_CONST) { advance_token(); } else { // 报告里的错误处理指明期望的 token 和实际遇到的 token syntax_error(expected expression factor); } }我在多个版本的课设里看到同一个问题advance_token()函数里忘记跳过 EOF 到末尾的空白 token结果语法分析在读到文件结束符时死循环。递归下降对EOF的处理非常重要最稳妥的写法是在advance_token()里判断current_token是TOKEN_EOF后就不再继续读因为文件已经结束。4.2 FIRST/FOLLOW集与冲突消解报告中“预测分析表”其实是后写的很多学生拿到报告时有个错觉认为报告里的 FIRST 集、FOLLOW 集是语法分析器写好之后才补算的。实际上递归下降分析器在实现前文法必须已经验证过无回溯冲突。验证方法就是算 FIRST 集和 FOLLOW 集。华理报告里对表达式文法给出的结果大致是非终结符FIRST 集FOLLOW 集表达式ID、NUM、(;、)、EOF项ID、NUM、(、-、;、)、EOF因子ID、NUM、(*、/、、-、;、)、EOF报告里如果出现两个产生式有相同 FIRST 集的情况比如因子 :: ID | NUM它们都是终结符开头的因为首字符不同所以没有冲突而因子 :: ID | ( 表达式 )首字符分别是ID和(也不会冲突。真正的冲突是像语句 :: ID 表达式 | ID [ 表达式 ]这种两个产生式都以ID开头这时候就必须提取公共左因子。报告在这部分的写法通常是把公共左因子提取后的文法列出来再写分析器代码。需要注意的一点是报告里语法分析器的错误处理分支往往是按 FOLLOW 集来设计的。比如在parse_factor()里如果当前 token 既不是ID、NUM、(说明语法出错了这时候报告里的错误消息会打印 FOLLOW 集允许的 token 列表来做提示这种设计在答辩时很加印象分。4.3 错误处理怎么做才让报告拿到高分错误位置、预期token与恢复策略错误处理是编译原理实验报告里最容易被敷衍处理的部分。大部分同学的代码是遇到错误直接printf(syntax error)然后exit(1)这在课设评分里只能拿及格分。华理报告的做法是分层设计词法错误输出“行列号错误字符描述”语法错误输出“预期期望何种 token 实际遇见的 token 所在行号”并对可以恢复的错误做同步处理。报告里给出了一种常见的错误恢复策略——在advance_token()里维护一个同步集合遇到错误时跳过 token 直到遇到;或}这样的同步点然后继续解析。错误处理的价值在测试用例中体现。一份好的报告会设计一个非法输入样例比如int 3abc;或a (b c;然后展示分析器的报错输出和恢复行为。报告里一般会有专门一节叫“错误处理测试”列出错误输入和运行输出。你在复现时如果发现自己的报告少了这部分建议补上两个用例词法错误非法字符、语法错误缺失右括号。这里还有一个反直觉的经验错误恢复代码比正确路径代码更容易写崩。报告里错误恢复的典型写法是每个解析函数维护一个自己的同步 token 集合比如parse_expression()遇到错误时跳过直到遇到;或 EOF因为这表示一条语句的边界。我当时复现报告时在这里翻过一次车——无限循环跳过 token 直到越界原因是跳过逻辑里没判断 EOF事后只能加一个if (current_token TOKEN_EOF) return;的硬保护。5. 避坑这份报告里最值得抄的是这几处踩坑记录5.1 关键字和标识符混淆测试时int被识别成标识符现象输入源码int a;词法分析输出中int被识别为TOKEN_IDENTIFIER而不是TOKEN_INT。原因resolve_keyword_or_id()函数里的关键字比较写成了strcmp(lexeme, int)但lexeme缓冲区末尾没加\0。解决在append_char()之后补上lexeme[len] \0并在构造 token 前打印一下调试信息对比字符串内容。这个问题在报告复现时非常常见因为报告里只贴了核心逻辑缓冲区管理的细节容易被忽略。5.2 状态图里有分支代码里却没实现现象状态图画了和两个分支但实际输入a 3;时输出和两个 token。原因状态图是前一个版本代码是后一个版本的 case 分支里提前 return 了没走到读下一个字符判断的逻辑。解决每改一次代码就回到状态图旁边做一次逐状态核对用不同颜色的笔把已经实现的状态和未实现的状态区分开。这是我在复现报告时学会的笨办法但确实有效。5.3 递归下降解析器遇到(直接死循环现象输入a (b c);语法分析器在解析因子时进入死循环程序卡死。原因parse_factor()处理(时调用parse_expression()之后没有匹配右括号的expect()。如果解析器在左括号分支里没有调用advance_token()它会反复处理同一个TOKEN_LPARENtoken。解决检查每个函数是否做到了“每个分支至少前进一个 token”并且在调试时给advance_token()加一个计数器超过 100000 次就强制中止并打印当前位置。5.4 测试用例只测合法输入非法输入一测就崩现象报告里的运行截图全是正确的解析结果自己拿非法输入int 1a;一测程序直接崩溃或输出乱码。原因词法分析器对数字加字母的混合输入没有做错误状态处理比如1a这个字符串在数字状态读到a后backtrack()但回溯后没回到起始状态就直接返回了错误 token。解决状态图里一定要画一个无法转移时的错误状态error通过get_error_token()输出行列号和错误字符。5.5 报告和代码的行号对不上答辩时被老师现场拆穿现象报告截图里测试用例输出行号是 5 行代码里跑出来是 6 行。原因复制代码到报告里时把测试源码中的空行或注释行删掉了但运行截图的图没重新截。解决写报告前强制用一份统一的测试文件报告里贴的所有运行截图都从这个文件跑出来同时把当前文件的md5sum值记在报告附录里答辩时如果被问到直接现场重跑一遍。6. 从报告反向重建一个可跑的课设验证方法与验收清单6.1 报告里的测试用例表是最高效的验收清单华理这份报告的测试用例表在验证阶段价值最大。一般会覆盖算术优先级、括号嵌套、连续赋值、错误处理四类场景。我复现时会把测试用例表转成一份testcases/目录下的文件一条用例一个.txt文件外加一个.expect文件记录期望输出。然后写一个 shell 脚本自动跑回归验证核心命令for f in testcases/*.c; do ./compiler $f testcases/$(basename $f).out 21 if diff -q testcases/$(basename $f).out testcases/$(basename $f).expect /dev/null; then echo $f PASS else echo $f FAIL fi done这样做的意义不是让测试覆盖率看起来漂亮而是能在你改代码时第一时间发现回归。比如你修了一个词法分析 bug结果语法分析器的行为全变了脚本能立刻告诉你哪里被连带影响了。6.2 三个必做的“破坏性实验”错一个字符、少一个分号、多一层括号报告里最薄弱的环节是错误恢复。想验证你自己复现的代码真的处理了错误而不是碰巧没崩溃可以做三个破坏性实验一是把int main;改成int ma1n;观察词法分析器是否正确处理数字出现在标识符中间的情况二是删掉表达式末尾的分号观察语法分析器是否给出了含行号的报错并且没有死循环三是写一个嵌套五层的括号((((1))))确认递归深度足够且不会栈溢出。用真实输入把这些结果跑出来对照报告中的错误处理描述能看出报告里的错误恢复策略是否完整。如果只是exit(1)退出说明报告描述的“同步恢复”并没有在代码中真正实现需要自己补上。把这三组破坏性实验的输出全部贴进自己的报告里比展示十组正确样例更能体现你对词法分析、语法分析底层机制的掌握程度。在很长一段时间里我拿到任何编译原理课设报告都会先跑这三个实验再决定要不要认真读——能扛住破坏性输入的报告才是值得逐行看的那种。希望这份华东理工的报告也能帮你少走几条弯路。本文还有配套的精品资源点击获取