简介这份编译原理实验报告面向东北大学秦皇岛分校计算机与通信工程学院的学生及正在学习词法分析的读者围绕 PL/0 语言词法分析程序的设计与实现展开帮助理解编译器的第一阶段如何把源程序切分为单词、类别二元组序列并具备识别“2A”这类非法单词的错误检测能力。文档按实验目的、实验内容、实验环境、提交内容与源代码的顺序组织完整呈现了基于 C 的 isLetter、isDigit、isP、isJ、isBlank 等字符分类函数以及主程序读取 pl0.txt、逐字符扫描、查关键词表 ktt 并输出类别编号的实现流程可作为课程实验的参考范本与调试对照。整包为 1 个 doc 文件约 122KB轻量便于下载后直接查阅与摘录。目前已有 102 人学习适合需要完成同类实验、梳理词法分析实现细节或准备编译原理课程考核的读者参考。1. 词法分析不是“分词”一份实验代码在边界上栽的跟头编译原理实验里最容易被低估的一环是词法分析输入一串字符输出一串单词类别二元组看起来像把句子按空格切开那么简单。但这份不到两百行的代码真正卡住人的地方全在边界判定上2A到底该不该合并成一个非法单词、1.2.3算几个数、#是结束哨兵还是合法界符。字符谓词、48 项类别表、递归下降的四个函数拼出了一条最小可运行的编译前端流水线它在边界上翻车的每一处恰好是理解“单词”这个抽象怎么被机器构造出来的最佳入口。2. 字符谓词与最长匹配单词的边界到底由谁决定2.1 五个谓词把字符空间切成互不重叠的几块扫描器做的第一件事不是识别单词而是给每个字符贴标签。这份实现用了五个布尔函数isLetter只认 ASCII 大小写字母isDigit只认 0 到 9isP认 - * /四个算术运算符isJ认界符和关系运算符isBlank认空格和制表符。五个函数合起来把整个字符集划成若干互不重叠的格子主循环里的if-else if链就是按这些格子分流的。bool isP(char ch){ if(ch||ch*||ch-||ch/) return true; // 下面这串被注释掉了: , ; ( ) else return false; } bool isJ(char ch){ if(ch,||ch;||ch.||ch(||ch)||ch[||ch] ||ch||ch:||ch||ch||ch{||ch}||ch#) return true; else return false; }isP下面那行注释是关键线索:,;()原本也想放进运算符集合后来被挪到了isJ。挪动的理由不是审美而是判定顺序会决定语义——如果:同时属于两个集合那么主循环先命中哪个分支就决定了:会被拆成两个单词还是一个。把集合做成互斥的分支顺序才无关紧要这是扫描器设计里一条不成文但很硬的规矩。常见的实现思路是用一张 256 项的字符类别表替掉这五个函数ch直接当下标O(1)拿到类别代价是初始化时要把表填满。isBlank只覆盖空格和制表符没有把换行算进去换行在主循环里被单独拎出来处理因为换行要触发行号维护和当前的单词串输出。这种“把一个类别拆成两个处理路径”的写法在实验代码里很常见省事但会让后面的状态管理变复杂。2.2 最长匹配循环退出条件写错单词的边界就漂了识别单词的核心算法叫最长匹配只要当前字符还能延长这个单词就继续读读到不能延长为止回退一个字符把已经读到的部分作为一个单词交出去。这份代码在两个地方用了它。标识符的写法是首字符必须isLetter后续isLetter || isDigit都能继续吞else if(isLetter(ch)){ int i0, j; while(isLetter(ch) || isDigit(ch)){ // 最长匹配字母数字都继续吞 str[i] ch; ch src[pos]; // 读下一个为退出做准备 } str[i] \0; for(j0; j21; j){ // 在前 21 项关键字表里线性查找 if(strcmp(str, ktt[j]) 0){ /* 命中关键字类别码就是 j */ break; } } if(j 21) { /* 没命中按标识符处理类别码 21 */ } }数字的写法是另一套if(isDigit(ch)){ int i0; while(isDigit(ch) || ch.){ // 小数点也被吞进来 str[i] ch; ch src[pos]; } str[i] \0; ste ste | 22; // 类别码 22无符号数 cout str; continue; }两个循环的退出条件都只问了一件事当前字符是不是还能算作这个单词的一部分。但最长匹配真正需要判断的是两件事——当前字符能不能延长以及“不能延长”之后下一个字符是不是一个合法的后继。数字分支允许任意多个小数点1.2.3会被完整吞成一个“无符号数”标识符分支允许数字出现在非首位A1合法但2A根本不进这个分支因为首字符是2走的是数字分支。最长匹配的边界由“接受态 转出边”共同决定只写接受态、不写转出边扫描器就会在非法输入上给出看似正常的结果。3. 类别表与二元组48 项数组如何充当类型系统3.1 表的分区下标就是类别码char ktt[48][20]是一个 48 行、每行 20 字节的字符串数组初始化列表写满了关键字、占位符和符号。它的分区很有讲究下标区间内容数量用途0 ~ 20关键字从and到write21命中即返回下标作类别码21字符串“标识符”1非关键字的字母串22字符串“无符号数”1数字串23 ~ 47界符、运算符、复合符号25含..--:下标即类别码这是这份代码里最值得抄走的设计。扫描器输出的是二元组(单词, 类别)类别用整数表示如果为每个类别定义一个enum代码会更可读但实验环境里最省事的做法就是把类别码直接做成表的下标识别时只需返回一个整数无须再做一次映射。代价是这张表必须保持顺序稳定任何插入都会让所有硬编码的数字错位——代码里for(j34; j38; j)这种魔法数就是代价的具体体现。关键字查找用的是线性strcmp21 项遍历。对一个课程实验来说这个复杂度完全够用但在真实编译器里关键字通常走完美哈希或者 Trie因为每个标识符都扫 21 次字符串比较输入一大就会成为热点。常见的实现思路是先用标识符自己的哈希值去查一张小表命中才做一次strcmp确认把平均比较次数压到接近 1。3.2 二元组的拼接stringstream 来回倒的一次弯类别码的累积方式很特别stringstream ss; ste |; ss ste; // 把已有的串写进流 ss j; // 再写类别码 ss ste; // 整个读回来这段等价于ste | std::to_string(j)但绕了一个stringstream。绕的原因大概率是写代码时还不熟悉 C11 的to_string或者担心int和string不能直接相加。功能上没毛病问题出在时机ste是累积串每识别一个单词就追加一段但真正输出ste的地方在换行分支里else { // ch \n cout ste endl; ste ; }而每个单词分支里已经先执行了cout str只打印单词本身不打印类别码。结果就是屏幕上先连续滚出一串单词然后在换行处突然冒出一长串|21|23|22这样的数字单词和类别完全对不上。二元组的“输出”变成了两路错位的打印这是把“识别”和“格式化”耦合在一个循环里的典型后果。工程上会把 Token 先塞进一个vector扫描结束后统一遍历输出识别阶段不碰cout。3.32A为什么没被检出错误检测落空的那一步实验要求里写得很清楚程序要有一定检查错误的能力例如发现2A这类不能作为单词的字符串。但按代码逻辑走一遍2A的处理路径是这样的首字符2进数字分支循环读2下一个字符A不满足isDigit || ch.退出循环str 2输出然后continue。此时ch仍然是A主循环重新判断isLetter(A)为真进标识符分支读出A输出。最终得到两个合法单词没有任何错误提示。根因在 2.2 节已经埋下数字分支退出时没有检查“退出位置上的字符是否是一个非法后继”。标识符不允许以数字开头所以数字后面紧跟字母本身就是词法错误。正确的做法是在数字循环退出后加一道判定——如果isLetter(ch)报“标识符不能以数字开头”并跳过这个字符继续扫描或者更严格一点把整个2A吞掉作为一个非法单词上报具体选哪种取决于错误恢复策略。这里还牵出一个容易被忽略的细节isJ包含了#而主循环的终止条件也是ch ! #。也就是说源文件里只要出现一个#扫描就提前结束后面的内容全部丢掉。PL/0 里#是不等于号是合法符号这个冲突意味着任何带#的源程序都会被截断。终止哨兵和合法符号撞车是扫描器设计里最典型的一类“用一个字符干两件事”的翻车。4. 递归下降文法规则怎么变成函数调用栈4.1 四个函数与 FIRST 集的隐式编码实验给的文法不长E → eBaA A → a | bAcB B → dEd | aC C → e | dC四个非终结符对应四个void函数每个函数体就是对应产生式右部的直译遇到终结符就比对并推进下标遇到非终结符就调用同名函数。先算一下每个非终结符的 FIRST 集E是{e}A是{a, b}B是{a, d}C是{d, e}。四个集合各自内部没有交集意味着每个函数只要看一个字符就能决定走哪条候选产生式不需要回溯——这正是 LL(1) 的定义也是这份代码敢用一个全局下标s单向推进的底气。void B(){ if(a[s] d){ // 候选一B → dEd s; E(); if(a[s] d){ s; } } else if(a[s] a){ // 候选二B → aC s; C(); } }B的两个候选分支靠首字符d和a区分A靠a和bC靠d和eE只有一条产生式首字符必然是e。整棵语法树的形状完全由输入串的字符顺序决定函数调用栈的形状就是推导过程的形状。4.2 全局下标s无回溯下降的推进模型s是全局变量初值 0所有函数共享同一个读位置。匹配成功才s匹配失败什么都不做函数直接返回。这种“共享读指针 只进不退”的模型是递归下降最简单的一种实现也是它和 LL 分析表法的最大区别——后者用显式的栈加分析表前者把栈交给语言自身的函数调用栈。无回溯的前提是所有候选产生式的 FIRST 集两两不交。一旦出现A → aB | aC这种左公因子看一个字符就分不清该进哪个分支要么提取左公因子改文法要么老老实实加回溯。这份实验文法是精心挑过的四个 FIRST 集恰好互斥所以代码里看不到任何保存现场、回滚下标的动作。真实语言的表达式文法几乎不可能这么干净E → E T | T这种左递归必须先消除if语句的悬挂 else 问题也要单独处理那时候递归下降就得配合预测集或者回溯才能写下去。4.3void返回值带来的失败静默四个函数全部返回void这是整份实现里影响最大的一个设计决定。E()里如果首字符不是eif不成立函数什么都不做就返回调用者拿不到任何“失败”信号只能继续往下走。最终的合法性判定压缩成了main里的一行E(); if(a[s] #){ printf(句子结构正确\n); } else { printf(分析失败\n); }只检查末尾字符是不是#等价于“只要下标推进到了输入末尾就算成功”。这个判据在输入刚好卡在正确位置时会漏判比如输入e#E()匹配e推进到下标 1调用B()此时a[1]是#既不是d也不是aB()静默返回回到E()检查a[1] a不成立E()也静默返回。此时s 1a[1] #成立程序打印“句子结构正确”。但e#显然不是E → eBaA的句子BaA整段都缺失。根因是缺少“每个非终结符必须完整匹配自己那条产生式”的断言。正确的递归下降函数应该返回bool匹配失败时返回false并回滚s让调用者决定是换候选产生式还是上报错误。void版本把失败信息全部丢掉只在最外层用一个位置检查兜底兜得住正常输入兜不住任何提前结束的输入。还有一个更隐蔽的问题s是全局变量main里套了一个while(1)循环反复读输入但s从来没有被重置回 0。第一次分析结束后s停在某个位置第二次输入从那个位置接着读越界访问几乎是必然的。这类“全局状态忘了复位”的 bug 在单次运行的测试里完全看不出来只有连续输入两次才会暴露。5. 常见问题排查那些“跑通了但不对”的坑5.1 输入与状态相关的坑坑一第二次输入直接崩或者读到上一次的残留。现象程序第一次分析正常第二次输入任意串输出“分析失败”或者直接段错误。原因s在main外定义为全局变量初值 0while(1)每轮循环都调用E()但没有任何地方把s归零。第二轮开始时s还停在上一次分析结束的位置a[s]读到的是输入缓冲区里的残留字符甚至越界。同时scanf(%s, a)每次覆盖写但没有清空数组短串覆盖长串会留下尾部垃圾。解决在每次调用E()之前执行s 0; memset(a, 0, sizeof(a));。更彻底的做法是把s改成函数参数用int传给四个函数让状态的生命周期跟着一次分析走而不是跟着进程走。坑二源文件里出现#就中断后面的内容全丢。现象pl0.txt里只要有一个#扫描到那里就停后面的单词一个都不输出。原因主循环的终止条件是while(ch ! #)而isJ的字符集合里也包含#。两个身份撞在一起扫描器把合法的“不等于号”误认成文件结束哨兵。解决换一个不出现在语言符号集里的终止符比如\0或者EOF让哨兵和合法字符彻底分开。终止条件最好基于文件读取的返回值而不是基于某个特定字符这样源文件内容怎么变都不会影响循环的退出。坑三连续界符被合成一个单词类别码丢失。现象输入A:10;)输出里出现一个;)这样的组合并且没有对应的类别码。原因界符分支用的是while(isJ(ch))只要下一个字符还是界符就继续吞。单字符界符后面跟另一个界符时两个会被拼成一个strstrcmp在 25 项表里找不到匹配for循环走完不break但也没有else分支处理未命中直接cout str就完事了。解决界符分支不能无条件最长匹配。正确做法是先把双字符复合符号:..单独拿出来做前瞻判断命中就吞两个字符没命中就只吞一个。单字符界符的循环条件应该是“只读一个”。5.2 输出与判定相关的坑坑四单词和类别码错位二元组输出不成对。现象控制台先滚出一长串单词然后在换行处冒出一串|21|23|22这样的数字两者数量对不上。原因单词分支里执行cout str类别码追加到ste里但不立即输出ste只在遇到换行时才cout ste endl。识别和格式化被拆成了两条时间线。解决定义一个结构体struct Token { string lexeme; int code; };识别阶段只往vectorToken里塞扫描全部结束后统一遍历输出。识别逻辑不碰输出输出格式想怎么改就怎么改两者互不干扰。坑五e#被判为合法句子。现象输入一个明显不完整的串程序打印“句子结构正确”。原因四个递归函数返回void匹配失败时静默返回最终只看a[s] #。只要下标恰好停在#上不管中间跳过了多少该匹配没匹配的内容都算成功。解决把四个函数改成返回bool每条产生式右部逐项匹配任何一项失败就返回false并回滚s。最外层收到false直接报错不再用位置检查兜底。回滚的实现很简单进入函数时记下int saved s;失败时s saved;再返回。6. 设计取舍教学版前端为什么“笨”得有理这份代码里很多写法放到工程标准下都是要被挑刺的关键字线性查找、类别码硬编码、全局状态、void返回值、识别和输出耦合。但如果把它当成一份教学材料来看这些“笨”地方大多是有意为之或者至少是可以理解的取舍。关键字用 21 次strcmp而不是哈希表是因为这张表本身就是要展示给读者看的21 个关键字、2 个占位、25 个符号下标即类别码一眼能看明白类别码是怎么来的。换成完美哈希查找是快了但“类别码从哪来”这个教学点就消失了。同理五个手写谓词比一张 256 项的字符类别表更直观读者能直接看到“字母”“数字”“运算符”这些概念是怎么被翻译成布尔函数的。递归下降不写回溯是因为文法被特意设计成 LL(1) 的。四个 FIRST 集互斥看一个字符就能定分支加回溯纯属浪费。这个取舍在真实语言上不成立但作为“递归下降是什么”的入门示例它把函数调用栈和推导过程的对应关系展示得干干净净。真正的分界线在错误处理上。教学可以简化数据结构可以不做优化但不能在“错了要报错”这件事上省事。2A漏检、e#误判、#截断文件、全局s不复位这四件事的共同点是程序在错误输入上给出了“正确”的答案。这比崩溃更糟因为崩溃至少告诉你出事了静默通过会让你以为扫描器已经写好。维度课程实验版工程版常见做法关键字匹配21 次线性strcmp完美哈希 / Trie平均 O(1)字符分类五个手写谓词256 项类别表或位图单词边界只看接受态接受态 转出边双重判定错误处理无靠末尾位置兜底同步点恢复 行列号上报状态管理全局s封装成 Scanner 对象一次分析一个实例输出边识别边cout先产出 Token 流再统一消费从那以后我每次写扫描器都先把每个接受态的转出边单独列成一张表确认“读到什么字符必须报错”这一列不是空的再动手写代码。这一步花不了十分钟但能挡掉后面调试两小时的静默错误。希望帮到你。本文还有配套的精品资源点击获取
