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

简介：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 < 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 集的情况，比如<因子> ::= 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" 2>&1 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)退出，说明报告描述的“同步恢复”并没有在代码中真正实现，需要自己补上。

把这三组破坏性实验的输出全部贴进自己的报告里，比展示十组正确样例更能体现你对词法分析、语法分析底层机制的掌握程度。在很长一段时间里，我拿到任何编译原理课设报告都会先跑这三个实验再决定要不要认真读——能扛住破坏性输入的报告，才是值得逐行看的那种。希望这份华东理工的报告也能帮你少走几条弯路。

本文还有配套的精品资源，点击获取