编译原理实验：PL/0词法分析与递归下降分析器实现

简介：这份编译原理实验报告面向东北大学秦皇岛分校计算机与通信工程学院修读编译原理课程的学生，围绕 PL/0 语言词法分析程序的设计与实现展开，可用于理解词法分析基本概念、完成实验编码与报告整理。资源包仅含 1 个 doc 文件，压缩包约 122KB，篇幅集中，便于直接查阅实验目的、实验环境、提交要求与程序源码。报告以 Windows PC 和 C++ 为实现环境，详细给出 isLetter、isDigit、isP、isJ、isBlank 等字符判断函数，关键词表匹配、单词与类别二元组输出以及“2A”一类非法单词检测思路，并附 main 函数读取 pl0.txt、逐字符扫描和分类输出的完整流程。已有 102 人学习或下载，适合需要参考词法分析器结构、错误处理方式和实验报告组织方式的学生对照使用。

1. 从两份必做实验说起：词法分析器与递归下降分析器的交付边界

导师给的材料往往只有一页纸：一张 PL/0 关键字表、一段 G[E] 文法、一个两周的截止日期，然后要求交两份能跑的程序和一份编译原理实验报告。看起来简单，真正动手才发现坑全在边界上——词法分析器输出什么格式、错误串怎么报、语法分析器怎么判断"这个串不是句子"而不是"程序崩了"。这篇内容按一份完整交付物的顺序走：先把需求和总体设计定死，再落到词法分析的查表与最长匹配、语法分析的 FIRST 集与四个下降函数，最后给一套能自证的测试用例和答辩演示脚本。适合正在赶编译原理课设、毕设里要写一个前端模块，或者需要给团队新人讲清"一个最小可用的编译器前端长什么样"的人。

2. 总体设计：48 项种别表、三层职责与二元组输出约定

动手写代码之前，先把"单词"这件事定义清楚。词法分析器的输出不是字符串，是二元组序列，每个二元组是（单词原文，类别码）。类别码怎么编，直接决定后面语法分析器好不好写、错误信息好不好读。我见过太多人一边写扫描循环一边临时决定编号，写到一半发现关键字和界符的编号混在一起，查表区间全乱，只能推倒重来。

2.1 种别表怎么排：48 项、四个区间与编号约定

PL/0 的种别表按"关键字 → 标识符 → 无符号数 → 界符与运算符"四段连续排布，一共 48 项，编号 0 到 47。这个顺序不是随便定的：它让每一类都有一个连续的闭区间，查表时只要给对上下界，一次循环就能定位，不需要写四个不同的查找函数。

这张表要作为一个常量数组落地，元素的顺序就是编号，不要另外维护一份映射。编号即下标，是后面所有查表逻辑的前提。注意 21 和 22 是"兜底类别"，它们不对应任何具体字符串，只在对关键字表匹配失败时使用；而 23 到 47 里的每一项都是实打实的字符串，包括..、<>、<=、>=、:=这些双字符符号。

2.2 三层职责划分：字符层、扫描层、输出层

整个词法分析器拆成三层，每层只干一件事，这样出问题时能快速定位是哪一层错了。

字符层是一组判断函数：是不是字母、是不是数字、是不是空白、是不是运算符首字符、是不是界符字符。这一层最容易被写废——很多人把所有符号判断塞进一个大函数，后面想加一个:=就要改三处。正确做法是让字符层只回答"这个字符属于哪一类"，不做任何前看后看。

扫描层是主循环，负责按首字符分流、连续读取、最长匹配。它是唯一持有读取位置指针的地方，所有位置的推进都在这里发生。

输出层负责把（单词，类别码）写出去，同时把错误信息写到独立的错误通道。正常输出和错误输出必须分开，否则测试的时候错误行混在 token 流里，根本没法比对预期结果。

2.3 输入输出契约：源文件、结束符与二元组格式

输入约定写死在文档里：源程序放在纯文本文件里，一次性读成字符串，末尾补一个#作为结束标记。补#这个动作要在读完之后做，不要指望源文件里本来就有。补完之后主循环的条件就是"当前位置的字符不是#"，简洁且不会越界。

输出格式固定成每行一个二元组，形如：

(const, 2) (a, 21) (=, 38) (10, 22) (;, 24)

括号里前面是原文，后面是类别码。之所以不用"单词 类别"这种空格分隔，是因为标识符和关键字里不会有逗号，而英文逗号在 PL/0 里本身就是界符，用括号和逗号包裹反而不会歧义。有人喜欢输出成2 21这种纯数字对，答辩的时候自己都读不出来，不建议。

提示：源文件如果是在 Windows 下用记事本存的，换行是\r\n，\r必须在字符层被判为空白，否则它会变成一个"无法识别的字符"混进 token 流，测试结果全错，而且极难发现。

2.4 错误通道：和正常输出分开走

错误信息至少包含三样东西：错误类型、行号、列号。行号列号不是扫的时候顺手记，而是出错那一刻根据当前位置从头数一遍算出来的——源程序一般就几十行，重算一次的成本可以忽略，换来的是代码里不用维护两个额外的计数器，也就不会出现"行号加了两次"这种低级错误。

// 根据偏移量反算行列，只在报错时调用，避免主循环维护额外状态 static void reportError(const std::string& src, size_t pos, const std::string& msg) { size_t line = 1, col = 1; for (size_t i = 0; i < pos && i < src.size(); ++i) { if (src[i] == '\n') { ++line; col = 1; } else ++col; } std::cerr << "第 " << line << " 行第 " << col << " 列：" << msg << "\n"; }

这个函数只在出错时调用，主循环里不需要任何行号变量，扫描逻辑因此保持干净。参数pos是当前读取位置，msg是具体描述，比如"无法识别的字符"或"数字后面不能紧跟字母"。把错误通道独立出来之后，正常 token 流可以直接重定向到文件，做批量测试比对。

3. 词法分析实现：关键字查表、最长匹配与非法字符定位

词法分析器最容易写错的地方，不是循环怎么写，而是"什么时候该多看一个字符"。多看一眼是前瞻，少看一眼是漏读，看错方向就是翻车。这一章把主循环拆成几个可验证的片段，每段都能单独测。

3.1 字符分类函数：边界条件比函数名更重要

五个判断函数，看似简单，但每一个都有边界要处理。字母判断要同时覆盖大小写；数字判断只认 0 到 9；空白判断必须包含空格、制表符、回车和换行四种；运算符首字符集合是+ - * /；界符字符集合则是剩下那批，包括逗号、分号、冒号、点、括号、方括号、尖括号、等号、花括号和#。

// 字符层：只回答"属于哪一类"，不做任何位置推进 static bool isLetter(char c) { return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'); } static bool isDigit(char c) { return c >= '0' && c <= '9'; } static bool isBlank(char c) { return c == ' ' || c == '\t' || c == '\r' || c == '\n'; }

注意isBlank里多了\r和\n。原始材料里的版本只判空格和制表符，换行单独在主循环里处理，结果就是行尾的回车符被当成未知字符。这类 bug 属于玄学范畴：在本机测试通过，换一台机器存文件就报错，查半天查不出原因。

3.2 主扫描循环：按首字符分流与最长匹配回退

主循环的结构是"看首字符 → 决定走哪条支路 → 连续读取 → 输出 → 推进位置"。四条支路：数字、字母、运算符界符、其他。

// 扫描层：所有位置推进都发生在这里 std::vector<Token> scan(const std::string& src) { std::vector<Token> out; size_t pos = 0; while (pos < src.size() && src[pos] != '#') { char ch = src[pos]; if (isBlank(ch)) { ++pos; continue; } // 空白直接跳过 if (isDigit(ch)) { // 无符号数 size_t start = pos; while (pos < src.size() && isDigit(src[pos])) ++pos; // 只有"小数点后面还跟着数字"才并进常数，否则留给界符处理 if (pos + 1 < src.size() && src[pos] == '.' && isDigit(src[pos + 1])) { ++pos; while (pos < src.size() && isDigit(src[pos])) ++pos; } out.push_back({22, src.substr(start, pos - start)}); continue; } if (isLetter(ch)) { // 标识符或关键字 size_t start = pos; while (pos < src.size() && (isLetter(src[pos]) || isDigit(src[pos]))) ++pos; std::string word = src.substr(start, pos - start); int code = lookup(word, 0, 20); out.push_back({code >= 0 ? code : 21, word}); continue; } // 界符与运算符：先试两字符，不中再退回单字符 std::string two = (pos + 1 < src.size()) ? src.substr(pos, 2) : ""; int code = two.empty() ? -1 : lookup(two, 23, 47); if (code >= 0) { out.push_back({code, two}); pos += 2; continue; } std::string one(1, ch); code = lookup(one, 23, 47); if (code >= 0) { out.push_back({code, one}); ++pos; continue; } reportError(src, pos, std::string("无法识别的字符 '") + ch + "'"); ++pos; // 跳过坏字符，继续往下扫 } return out; }

这段代码里有三个关键决定。第一，数字扫描只在"小数点后确实是数字"时才吞掉小数点，这样X:=1..10里的1和..才能分开，否则1..10会被吞成一个畸形常数。第二，标识符扫描不额外判断长度，靠pos < src.size()兜住边界，不需要固定大小的字符数组。第三，符号识别严格按"两字符优先、单字符兜底"的顺序，<=和<因此不会互相抢。

lookup是一个只在指定闭区间内做线性比对的小函数，区间参数就是种别表的编号区间：

// 在 [lo, hi] 闭区间内查表，命中返回编号，否则返回 -1 static int lookup(const std::string& s, int lo, int hi) { for (int i = lo; i <= hi; ++i) if (s == ktt[i]) return i; return -1; }

3.3 关键字查表与类别码回填

关键字识别本质上就是查表。标识符分支扫出一个完整单词后，先在 0 到 20 的区间里查，命中说明它是关键字，用命中的编号；没命中就归为标识符，编号 21。这个"先扫完再查表"的顺序不能颠倒——如果边扫边查，whi扫到第三个字符时查不到，你就提前判成标识符了，后面le又成了新标识符，整个单词被拆碎。

这里的答疑点在于：为什么关键字表的顺序要和编号严格一致。因为后面如果要打印"这个编号对应的单词是什么"，只需要ktt[code]一次下标访问。如果表里顺序和编号错开，就得维护一份反查表，多一处冗余就多一处出错的机会。我一般会在程序启动时做一次自检，确认 48 个位置都非空且不重复，跑测试之前先把这种低级错误挡掉。

3.4 错误检测：2A、孤立符号与行列定位

实验要求里明确写了要能发现2A这类不能作为单词的字符串。按上面的主循环，2A会被拆成数字2和标识符A，两个 token 各自合法，错误就漏过去了。所以必须加一条规则：数字扫描结束后，如果下一个字符是字母，直接报错。

// 数字分支收尾处补一句：数字后面紧跟字母不是合法单词 if (pos < src.size() && isLetter(src[pos])) { reportError(src, pos, "数字后面不能紧跟字母，这不能作为一个单词"); while (pos < src.size() && (isLetter(src[pos]) || isDigit(src[pos]))) ++pos; continue; }

注意这里要把后面那段字母数字一起跳过去，否则2A报完错，A又会被当成一个正常标识符输出，一次错误变成两次输出。

除了2A，还有三类常见错误要覆盖：孤立的符号，比如单独一个&或者@，走"无法识别的字符"分支；不完整的双字符符号，比如文件末尾孤零零一个<，会被单字符兜底命中<而不是报错，这一般可以接受；被注释或字符串截断的输入，PL/0 本身没有字符串，但花括号注释如果没闭合，最好在扫描结束后补一次检查，报"注释未闭合"而不是让后面的内容全部错位。

注意：错误恢复策略要提前定。是遇错停止，还是跳过继续？课程实验里推荐"报错并继续"，因为这样一次运行就能暴露多个错误，答辩演示时一屏能看出分析器到底覆盖了多少情况。

4. 语法分析实现：G[E] 的 FIRST 集与四个非终结符的下降路径

词法分析交给语法分析的不是原始字符串，是符号串。G[E] 这道题的输入符号只有e a b c d五个终结符，外加一个#作结束标记，也就是说语法分析器处理的是已经"抽象过一层"的符号序列，不需要再关心关键字和标识符的分类。

4.1 先判断这份文法能不能直接递归下降

给定的产生式是四组：

G[E]： E → eBaA A → a | bAcB B → dEd | aC C → e | dC

在写任何代码之前，先算 FIRST 集，看每个非终结符的多个候选能不能靠首符号区分开。

结论很明确：这份文法既没有直接左递归（不存在A → Aα这种形式），各候选产生式的首符号也互不重叠，所以可以原封不动地写递归下降，不需要消除左递归，也不需要提取公共左因子。这是这道题的设计意图，也是答辩时最容易被问到的点——很多同学一上来就习惯性地改写文法，改完发现推导路径和题目给的对不上，反而说不清。

4.2 四个非终结符对应四个函数

递归下降的核心约定只有两条：每个非终结符对应一个函数；函数内部严格按产生式右部的顺序匹配，匹配成功返回真并推进指针，匹配失败返回假且不保证指针位置。第二条很重要，失败时指针可能已经走了一段，所以调用方一旦收到假，必须立刻向上返回，不能装作没事继续往下走。

// 全局读取指针 p 和文法符号串（以 '#' 结尾） static const char* p; bool E(); // 前置声明，四个函数互相调用 bool A(); bool B(); bool C(); bool E() { // E → eBaA if (*p != 'e') return false; ++p; if (!B()) return false; // 中间任何一步失败立即向上返回 if (*p != 'a') return false; ++p; return A(); } bool A() { // A → a | bAcB if (*p == 'a') { ++p; return true; } if (*p == 'b') { ++p; if (!A()) return false; if (*p != 'c') return false; ++p; return B(); } return false; // 首符号不在 FIRST(A) 里，直接判失败 } bool B() { // B → dEd | aC if (*p == 'd') { ++p; if (!E()) return false; if (*p != 'd') return false; ++p; return true; // 第二条产生式的尾符号是 d，这里已经吃掉 } if (*p == 'a') { ++p; return C(); } return false; } bool C() { // C → e | dC if (*p == 'e') { ++p; return true; } if (*p == 'd') { ++p; return C(); } return false; }

注意 B 的第一条产生式dEd，末尾那个d是终结符，必须显式匹配并推进，不能因为"前面已经吃过一个 d"就省掉。同理 A 的bAcB里B是递归调回非终结符，函数返回值必须原样往上抛。这种地方一旦写成"调用完不管返回值"，分析器就会在错误输入上假装成功，这是递归下降最典型的假阳性来源。

4.3 失败路径：把"分析失败"变成可定位的信息

主函数里判断成功的条件有两个：E()返回真，并且指针停在#上。只判前者不够，因为E()可能只匹配了输入的前半段就返回真，剩下的部分被忽略了。

int main() { char buf[256]; while (std::cin >> buf) { p = buf; bool ok = E(); if (ok && *p == '#') { std::cout << "句子结构正确\n"; } else { std::cout << "分析失败：停在偏移 " << (p - buf) << "，剩余符号 \"" << p << "\"\n"; } } }

把失败位置和剩余串打印出来，是答辩时最容易加分的一处。评审老师随手输一个错误串，你不需要现场调试，程序自己告诉你"走到第几个符号、剩下什么没匹配"，说明分析过程的每一步都是可控的，不是黑匣子。

4.4 和词法分析器对接：符号串从哪来

如果两个实验要串成一条链，词法分析器输出的是二元组序列，语法分析器需要的是纯符号串。中间加一层轻量的转换就行：把类别码映射成文法里的终结符字符，比如把标识符统一映射成a，把常数统一映射成b，拼接成字符串后补#送给E()。

这一步不必做得很复杂。课程实验里推荐的做法是单独写一个tokenToSymbol函数，映射规则写在一张小表里，输入 token 序列，输出符号串。这样两个实验各自独立可测，串起来又能演示完整链路，答辩时"单测 + 联调"两套证据都能拿得出来。

5. 避坑与排查：五个让实验结果对不上的高频翻车点

编译原理实验的特点是"程序跑起来了，但结果不对"，而且错得很安静——不崩、不报错，只是输出的 token 数量少了几个，或者本来该判错的串被判成了正确。下面五条是按出现频率排的，每一条都给出可操作的排查手段。

5.1 界符连续吞字符，导致类别码整段丢失

现象：输入里有[]或者[[时，输出的 token 流里这两个符号消失了，后面的编号整体错位。

原因：界符分支写成了while (isJ(ch))，只要当前字符还是界符就继续吃，于是[]被一次性读成字符串"[]"，去表里查不到，匹配失败后类别码没有被回填，这个 token 就变成了"有原文、无类别"的残缺项。

解决：改成最长两字符匹配，先试两字符，命中就前进两步；不中再试一字符，命中前进一步；都不中就报错。前文 3.2 节的主循环就是这个结构。判断依据很简单：种别表里最长的符号是<>、<=、>=、:=、..这五个，都是两字符，所以最长匹配长度就是 2，不需要更长的前瞻。

5.2 数字后跟字母没检测，错误检测形同虚设

现象：实验要求里明确说2A是非法的，但程序跑出来把它分成了2和A两个合法 token，一个错误都没报。

原因：数字扫描和字母扫描各自独立，扫描完数字后指针移到A，主循环下一轮看到字母，正常走标识符分支。两条支路之间没有交叉检查，非法组合就这么被合法化了。

解决：在数字分支收尾处加一次前瞻判断，如果下一个字符是字母，立即报错，并把后续连续的字母数字一起跳过，避免同一个错误被反复报告。这条规则要写进实验报告的设计说明里，因为它体现了"词法错误不只是非法字符，还包括非法组合"这一层理解，答辩时是个不错的说明点。

5.3 递归下降的 if 没有 else，错误串被判成"结构正确"

现象：随手输入一个明显不合文法的串，比如以b开头的符号串，程序输出"句子结构正确"。

原因：某个非终结符函数里只有if (匹配)分支，没有else return false，首符号不在 FIRST 集里时函数直接走到末尾，返回了未定义行为或者隐式的成功。上面 4.2 节里每个函数结尾都有一个裸return false;，就是为了堵这个洞。

解决：逐个检查四个函数，确认每个函数的所有出口都显式返回布尔值，不存在"掉到底部"的路径。另外主函数必须同时检查E()返回值和指针是否停在#上，只查一个都不够。排查手段是准备一组"应该失败"的用例，每条至少一个，跑一遍看是不是全都报失败。

5.4 固定长度缓冲区与死循环，长输入直接冲掉栈

现象：输入稍微长一点的源程序，程序输出一半就停，或者直接异常退出；交互模式下输入一个非预期字符后开始无限刷屏。

原因：标识符用char str[20]存，超过长度就写穿；读入用scanf("%s", a)，没有宽度限制；主循环用while(1)且没有退出条件，输入流结束也不跳出。

解决：全部改用std::string和std::vector，长度由容器自己管；读入用std::cin >> buf或者scanf("%255s", buf)限定宽度；交互循环的条件改成"读到输入就继续，读不到就退出"，例如while (std::cin >> buf)。这一条属于纯工程习惯，跟编译原理没关系，但每年都有人的实验卡在这里，调试半天以为是算法错了。

5.5 文件读取与结束符处理，分析提前中断

现象：源文件明明有几十行，程序只分析了第一行就结束；或者最后几个 token 怎么都不出现。

原因：读文件时用fgetc循环拼字符串，拼完补#，但源文件里如果本身含有#（PL/0 里#是合法的界符），主循环遇到第一个#就停了；另一种情况是拼接时把 EOF 也写进了字符串，末尾多出一个乱码字符。

解决：读取时明确判断EOF再退出循环，不要把返回值直接塞进字符串；源文件里的#作为普通符号处理，结束标记用额外的布尔变量或者在下标层面控制，而不是靠"遇到某个字符就停"。测试用例里专门放一个含#的源文件，一跑就知道处理得对不对。

6. 验收与答辩：十分钟演示脚本与一组能自证的测试用例

答辩最怕的不是程序有 bug，是讲不清自己做了什么。十分钟里要让评审相信这套分析器是能跑、能错、能定位的，靠的不是念代码，是现场跑一组设计好的用例。我一般会准备一张测试表，每条用例对应一个考察点，跑完正好覆盖词法、语法、错误处理三块。

跑的时候按"词法三条、语法三条、错误一条"的顺序，每条跑完停两秒，让评审看清输出。第 3 条和第 4 条是最能体现设计水平的，因为这两处正是最容易写错的地方，你能主动演示，说明你知道坑在哪。

演示之外，答辩问题基本集中在三个方向。第一个是"为什么这份文法不用消除左递归"，答案就是 4.1 节的 FIRST 集表，直接指着表说每个非终结符的候选首符号互斥，不需要回溯。第二个是"错了怎么定位"，答案是把失败位置和剩余串打出来，这个前面已经埋好了。第三个是"两个实验怎么串起来"，答案就是 4.4 节那层 token 到符号的映射，说清楚映射表在哪、规则是什么。

还有一个小技巧：把词法分析的输出重定向到文件，答辩前先跑一遍，把结果整理成表格放进实验报告。现场演示时如果机器环境出问题（编码、路径、控制台字体都可能导致中文乱码），可以直接拿报告里的结果说话，不至于当场卡住。中文乱码这件事我吃过亏，ktt表里那些中文类别名在有的控制台里直接显示成方块，后来干脆把类别名改成英文缩写，报告里再附一张对照表，现场就再没出过问题。

从那以后我每次带这种实验，都强制自己先写测试用例表，再写代码，最后拿表逐条勾。代码可以改，表不能改，表就是验收标准。希望帮到你。

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