编译原理实验：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。这个顺序不是随便定的它让每一类都有一个连续的闭区间查表时只要给对上下界一次循环就能定位不需要写四个不同的查找函数。区间项数内容查表上下界0 – 2021and、begin、const、div、do、else、end、function、if、integer、not、or、procedure、program、read、real、then、type、var、while、write0 ~ 20211标识符固定值221无符号数固定值23 – 4725, ; : . ( ) [ ] .. -- - * / : { } #23 ~ 47这张表要作为一个常量数组落地元素的顺序就是编号不要另外维护一份映射。编号即下标是后面所有查表逻辑的前提。注意 21 和 22 是兜底类别它们不对应任何具体字符串只在对关键字表匹配失败时使用而 23 到 47 里的每一项都是实打实的字符串包括..、、、、:这些双字符符号。2.2 三层职责划分字符层、扫描层、输出层整个词法分析器拆成三层每层只干一件事这样出问题时能快速定位是哪一层错了。字符层是一组判断函数是不是字母、是不是数字、是不是空白、是不是运算符首字符、是不是界符字符。这一层最容易被写废——很多人把所有符号判断塞进一个大函数后面想加一个:就要改三处。正确做法是让字符层只回答这个字符属于哪一类不做任何前看后看。扫描层是主循环负责按首字符分流、连续读取、最长匹配。它是唯一持有读取位置指针的地方所有位置的推进都在这里发生。输出层负责把单词类别码写出去同时把错误信息写到独立的错误通道。正常输出和错误输出必须分开否则测试的时候错误行混在 token 流里根本没法比对预期结果。层输入输出不该做的事字符层单个 charbool不读文件、不推进指针扫描层源串位置token 新位置不格式化输出输出层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::vectorToken scan(const std::string src) { std::vectorToken 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 集看每个非终结符的多个候选能不能靠首符号区分开。非终结符FIRST 集候选产生式是否可区分E{ e }只有一条天然确定A{ a, b }a / bAcBa 与 b 不相交可区分B{ d, a }dEd / aCd 与 a 不相交可区分C{ e, d }e / dCe 与 d 不相交可区分结论很明确这份文法既没有直接左递归不存在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是讲不清自己做了什么。十分钟里要让评审相信这套分析器是能跑、能错、能定位的靠的不是念代码是现场跑一组设计好的用例。我一般会准备一张测试表每条用例对应一个考察点跑完正好覆盖词法、语法、错误处理三块。序号输入期望结果考察点1const a10;五个 token类别码依次为 2、21、38、22、24关键字、标识符、运算符、常数、界符全覆盖22A报数字后面不能紧跟字母非法组合检测3X:1..101、..、10三个独立 token最长匹配与小数点歧义4[][和]两个独立 token界符不能连续吞5eae结构正确递归下降正常路径6ba分析失败停在偏移 0首符号不在 FIRST 集7eae#结构正确指针停在#结束符处理跑的时候按词法三条、语法三条、错误一条的顺序每条跑完停两秒让评审看清输出。第 3 条和第 4 条是最能体现设计水平的因为这两处正是最容易写错的地方你能主动演示说明你知道坑在哪。演示之外答辩问题基本集中在三个方向。第一个是为什么这份文法不用消除左递归答案就是 4.1 节的 FIRST 集表直接指着表说每个非终结符的候选首符号互斥不需要回溯。第二个是错了怎么定位答案是把失败位置和剩余串打出来这个前面已经埋好了。第三个是两个实验怎么串起来答案就是 4.4 节那层 token 到符号的映射说清楚映射表在哪、规则是什么。还有一个小技巧把词法分析的输出重定向到文件答辩前先跑一遍把结果整理成表格放进实验报告。现场演示时如果机器环境出问题编码、路径、控制台字体都可能导致中文乱码可以直接拿报告里的结果说话不至于当场卡住。中文乱码这件事我吃过亏ktt表里那些中文类别名在有的控制台里直接显示成方块后来干脆把类别名改成英文缩写报告里再附一张对照表现场就再没出过问题。从那以后我每次带这种实验都强制自己先写测试用例表再写代码最后拿表逐条勾。代码可以改表不能改表就是验收标准。希望帮到你。本文还有配套的精品资源点击获取

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

相关推荐

8款论文写作工具评测与高效写作指南

JMeter HTTP信息头管理器详解与应用实践

青蛙跳台阶问题：动态规划与斐波那契数列解析

更多资讯

ERP与电商平台高效对接实战：金蝶云星空与旺店通集成方案

Python AI应用开发五阶段学习路线：从零基础到工程化部署

Nginx proxy_pass配置与优化实战指南

2026年AI学习路线：工具链、框架与实操全指南

2026年AI学习生态全景：从大模型到应用层工程师的完整路线

Java AI框架选型指南：Spring AI、LangChain4j、AgentScope与Embabel实战定位

今日更新

AI辅助技术栈评估：提升研发决策效率60%

从生成Token到直接决策：Jev如何重塑AI Agent工程实践

32G统一内存跑大模型：内存账、TPS实测与端云分流

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？