简介东北大学秦皇岛分校编译原理课程实验报告聚焦PL/0语言词法分析程序的设计与实现系统记录了从实验目的、内容、环境到C源码实现的全过程。报告重点展示了词法分析器如何通过字符分类、关键词表匹配、非法字符检测等步骤将源程序字符串转换为单词类别二元组序列其中对数字、标识符、运算符、界符的识别逻辑均有清晰代码说明并包含错误处理能力例如可识别出“2A”这类非法单词。资源包为单个doc文档体积仅122KB内容紧凑、结构完整适合编译原理初学者对照学习也可作为课程设计或实验报告的写作参考。目前已有98人在CSDN学习下载体现了该资料对相关课程学习的实际帮助。报告中完整的主程序流程、详细的函数注释与输出设计可帮助读者深入理解词法分析在编译器前端的核心作用为后续语法分析、语义分析等环节打下扎实基础。1. 词法分析器与递归子程序为什么 2A 不报错、函数嵌套就是文法这份编译原理实验报告最有意思的地方在于它的词法分析器遇到2A这种非法单词时并不会报错而是心平气和地把它切成两个合法单词——数字2和标识符A。表面上看词法分析是「从左往右逐字符判断」但真正让它 work 的是一张 48 行的常量表加四个字符分类函数实验 4 的递归子程序分析器表面是层层嵌套的函数调用本质却是文法产生式到 C 函数的一一映射。把这两层拆开编译器最前面的黑匣子就算揭开了一半。这也是这份报告值得反复咀嚼的原因——它把编译器原理压缩成了一份能跑、能调试、也能让你踩坑的最小实现。2. 字符分类函数组为什么手写 isLetter 而不是用ctype.h词法分析要做的第一件事是把输入字符流按 ASCII 码值切出「字母、数字、运算符、界符、空白」这五类。PL/0 实验里没有使用 C 标准库ctype.h的isalpha、isdigit而是手写了isLetter和isDigit两个函数。看起来像重复造轮子但这里有一个很实际的理由教学代码要跑在各种编译器上显式写(chA chZ)不依赖语言环境对字符集的定制行为一目了然。另一个原因是标准库的isalpha受 locale 影响在非英文环境下可能把带变音符的字符也算作字母而词法分析要求「字符集边界完全可控」。2.1 isLetter / isDigit字符集硬编码背后的可移植性取舍bool isLetter(char ch) { if ((ch A ch Z) || (ch a ch z)) return true; else return false; } bool isDigit(char ch) { if (ch 0 ch 9) return true; else return false; }这两个函数只做了区间判断大写字母区间、小写字母区间、数字区间。注意它们没有处理EOF的情况也没有把下划线_放进字母集合——这意味着这份词法定义里的标识符不能含下划线max_len、_tmp这类写法在 PL/0 源程序里会被拆成max和len两个符号。代码里char ch0, ch;用的是有符号char当fgetc返回EOF即 -1时被截断成char后与EOF比较在标准 C 里是经典隐患好在此处文件正常结束未触发。字符分类在编译器前端属于热路径每个字符至少要被调用一次。两个布尔函数的代价是常数级比较主循环整体复杂度是 O(n)n 为源程序字符数。可移植性上的收益则是不管换到哪个平台、哪个 C 标准这组判断的结果都完全一致。我一般会这么理解——教学代码把「正确性」放在「高效」之前硬编码区间正是为了在课堂上不用解释 locale 是什么。2.2 isP 与 isJ运算符/界符的集合判定以及注释里被删掉的那行bool isP(char ch) { if (ch || ch * || ch - || ch /) return true; // ch:||ch,||ch||ch;||ch(||ch) 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的集合要大得多逗号、分号、句点、括号、方括号、花括号、比较符、赋值号:的组成字符、结束符#。注意被注释掉的那行ch:||ch,||ch||ch;||ch(||ch)——这是词法分析器设计上的「活化石」写代码的人曾经想把冒号、逗号、等号、分号、括号都归入isP后来删掉了。这个删除动作直接影响后续匹配顺序四则运算符在主循环里走「单字符运算符」分支查表范围是 34~37而冒号、等号、括号等走「界符」分支查表范围是 23~47。这个划分不是随意的。四则运算符在 PL/0 里都是单字符符号不需要向后看而:、、、、..这类多字符符号必须由isJ配合while循环连续读取才能拼完整。把「能组成复合符号的字符」和「不能组成复合符号的字符」分开本质上是在字符层面预先做了「最长匹配」的粗筛。代价是优先级问题同时也是的第一个字符但因为isP分支先被命中永远无法作为一个整体被识别——这个坑在第 5 章会展开讲。2.3 isBlank 与换行被忽略的字符也是词法的一部分bool isBlank(char ch) { if (ch || ch \t) return true; else return false; }空白字符在词法分析里不产生单词但它是词法分析器必须处理的输入。如果isBlank不存在空格和制表符会落到「无法识别」的分支要么报错要么静默吞掉。这份代码里空格和制表符被直接跳过\t之外的空白比如换行\n没有被isBlank吸收而是单独在主循环的else分支处理每遇到一个换行就把当前累积的单词类别串ste打印一行然后重置。也就是说换行符在这里承担了双重职责一是源码里的普通字符二是「输出缓冲区的刷新信号」。这个设计透露出实验报告的定位它要演示的不只是「把单词切出来」还要把「切出来的类别序列」按源代码行组织好方便肉眼核对。实际编译器的词法分析器不会让换行承担输出职责——行号信息需要单独维护空白要么丢弃要么变成 token 传给语法层。但在教学实验里这种「一行源程序对应一行输出」的映射能让学生直接看到CONST、VAR、PROCEDURE每行的单词序列验证成本低得多。要从这份代码里学到的不是「换行就该这么处理」而是「词法分析器可以自定义字符的语义关键是让这个语义在代码里保持一致」。3. ktt 常量表与类别码词法分析的词典机制藏在哪四个分类函数把字符切成了「字母流」「数字流」「符号流」但「这个单词是不是关键字」「这个符号对应什么类别」答案都藏在主循环开头定义的那张 48×20 的二维字符数组里。这是整份代码的核心数据结构也是一般初学者最容易忽略的部分——他们盯着while循环看半天却不知道真正做决策的是这张表。3.1 0~20 关键字、21/22 预留、23~47 符号一张表三种区char ktt[48][20] { and, begin, const, div, do, else, end, function, if, integer, not, or, procedure, program, read, real, then, type, var, while, write, 标识符, 无符号数, ,, ;, :, ., (, ), [, ], .., , --, , -, *, /, , , , , , , :, {, }, # };这张表的布局是有讲究的下标 0~20 是 PL/0 的 21 个关键字下标 21、22 分别预留给「标识符」和「无符号数」两种抽象类别下标 23~47 是 25 个具体符号。也就是说ktt里存的并不全是「单词」还包括了两个「类别占位符」。当主循环识别出一个关键字时比如begin它通过strcmp找到begin在下标 1 的位置于是类别码就是 1当它识别出一个查不到关键字的字母串时直接给类别码 21。类别码本身就是查表得到的下标省掉了一次「单词→二进制编码」的二次映射。这种把「字典」和「类别编码表」合并成一张二维数组的写法是编译器教科书里标准的表驱动思想数据驱动逻辑代码里不写死任何关键字。想加一个关键字只需要往数组里插一项想改单词的类别改一行数据即可。我一般会这么理解——这张表就是词法分析器的「词典」查表命中就是这个词在词典里有条目查不到就归类为「标识符」这个兜底类别。真正的词法分析器里这张表多半换成哈希表或 Trie但抽象模型完全一致。3.2 线性查表与 strcmp48×20 的代价为什么可以接受字母和数字分支的查表逻辑分别是这样的for (j 0; j 21; j) { int t strcmp(str, ktt[j]); if (t 0) { stringstream ss; ste |; ss ste; ss j; ss ste; break; } } if (j 21) { ste ste | 21; }字母串str先用strcmp依次和 0~20 的关键字比较命中则类别码为j否则归为标识符。数字串则完全不查表直接给类别码 22。界符分支用while(isJ(ch))连续读入若干字符组成一个串再在 23~47 的范围里线性查找。整个过程没有哈希、没有二分就是最朴素的顺序扫描。这种实现的时间复杂度是 O(n×21×20)n 是单词数21 是关键字的表项数20 是每项最大长度。实际 PL/0 源程序通常几百到几千个单词这个复杂度在 Windows PC 上肉眼完全无感。换成哈希表能将平均复杂度降到 O(n)但代码量会从几行膨胀到几十行还要设计哈希函数和冲突处理——在教学实验场景下这个「足够好」的取舍是合理的。真正的教训在这里优化必须建立在能正确运行的基础上先让查表逻辑跑通再谈查询效率。如果你动手改这份代码建议把ktt的维度换成vectorstringstrcmp换成可读性会立刻上一个台阶。3.3 错误检测的真实行为2A 被切成「2」和「A」而不是报错实验要求里写着「有一定检查错误的能力例如发现 2A 这类不能作为单词的字符串」但看代码的实际行为if (isDigit(ch)) { int i 0; while (isDigit(ch) || ch .) { str[i] ch; ch src[pos]; } str[i] \0; ste ste | 22; cout str; continue; }遇到字符2时进入数字分支。while循环的条件是「当前字符是数字或点」于是它读走2下一个字符是A不是数字也不是点循环停止。数字串2被输出类别码 22。外层循环继续A进入字母分支被读成标识符。最终输出的是两个合法单词数字2和标识符A。所谓的「发现 2A 非法字符串」的能力在这个代码里并没有真正实现。为什么会出现要求与实现的偏差因为数字分支只判断了「当前字符属于数字类」没有检查「数字串的后继字符是否紧跟着字母」。如果2A是一个变量名或者写错了的常量词法分析器应当报「非法单词」但这份代码选择了把它静默拆开。这种「拆开」在有些场景下是有意为之——比如把1e3拆成1和e3虽然语义不对但至少不会让词法分析器崩溃。可对于 PL/0 这种教学语言2A必须被标记为错误否则语法分析器拿到的是两个合法 token错误会在更后面的阶段以更诡异的方式暴露。排查思路很简单在数字串读完后加一句if (isLetter(ch))就报错。4. 递归子程序分析器为什么产生式右部能直接翻译成函数体实验 4 的递归子程序分析器处理的文法很短G[E]: E - e B a A A - a | b A c B B - d E d | a C C - e | d C代码结构更短四个函数E()、A()、B()、C()加一个全局字符数组和游标。这段代码如果只看表面就是「几个函数你调我、我调你」但把它和文法并排放在一起会发现每个函数体就是一条产生式右部的直译。这就是递归下降分析法recursive descent parsing的核心一种把 BNF 文法机械翻译成程序的方法。4.1 左部就是函数名右部展开成语句序列void E() { if (a[s] e) { s; B(); if (a[s] a) { s; A(); } } }对应产生式E - e B a A。函数体从左到右依次做了四件事匹配终结符e、调用B()、匹配终结符a、调用A()。终结符的匹配方式是「如果当前字符就是要找的那个游标后移一位」非终结符的匹配方式是「调用以它命名的函数」。反过来如果当前字符不是期望的终结符函数什么都不做静默返回——注意没有else报错这是后面要说的致命简化。为什么这样翻译能 work递归下降的约定是每个非终结符对应一个函数函数成功返回表示「该非终结符已经完整匹配」。E()里先调B()B()内部会完全消化掉B能推导出的子串等B()返回时游标正好停在B推导串的下一个位置E()再检查那个位置是不是a。这种「函数调用就是非终结符展开」的映射让文法的递归特性直接变成了程序里的函数递归。E的定义里间接引用了E自己通过B - d E d所以E()函数里会出现B()的调用而B()里又有E()的调用形成互相递归。4.2 终结符用 if、非终结符用调用选择分支的翻译规则A - a | b A c B是两条产生式的并集翻译出来就是一个多分支void A() { if (a[s] b) { s; A(); if (a[s] c) { s; B(); } } else if (a[s] a) { s; } }这里体现了递归下降的选路规则当前字符是b就走第一条分支当前字符是a就走第二条分支。它只靠「当前这一个字符」决定走哪条路不需要向前多看几个字符——这就是 LL(1) 文法的直觉一个 lookahead 符号足以决定推导方向。这份文法恰好是为 LL(1) 设计的每个非终结符的候选产生式都以不同的终结符开头不存在「两个候选都能匹配」的冲突。如果文法是左递归的比如E - E T这种翻译直接写成函数就会无限递归E()第一步调用E()永远不前进。所以递归下降要求文法先消除左递归这也就是为什么实验给的是右递归版本A - b A c B右递归在递归下降里表现为函数A()自己调用自己但每次调用至少先消费一个b递归深度有限。给代码加点注释会看得更清楚void C() { if (a[s] d) { s; C(); // C - d C右递归逐个消费 d } else if (a[s] e) { s; // C - e递归出口 } }C - d C | e的语义是「若干个d后跟一个e」。翻译成C()后每次遇到d就消费掉并递归调用自己直到遇到e再消费并返回。这里能直观看到右递归与while循环的等价性C()的递归深度等于d的个数如果源程序里有 1000 个连续的d函数调用栈就会压 1000 层。实际编译器里这种写法有栈溢出的风险但教学实验的输入规模不会触发。4.3 全局数组与游标 s显式状态机与错误恢复的缺失char a[10]; int s 0;这个设计的要点是所有函数共享同一个字符数组a和同一个游标s。函数之间不需要传参、不需要返回值B()消费了多少字符E()通过s的位置变化就能感知。递归下降的教科书实现通常会把这个游标作为参数传递或封装成TokenStream对象但实验代码选择了全局变量省掉一切传参噪音。这是教学代码的常见简化代价是不能同时跑两个分析实例也不能在多个输入串之间切换状态。更关键的问题是错误恢复缺失。所有函数的失败路径都是静默返回连布尔值都不给。看看main里的判定E(); if (a[s] #) printf(句子结构正确\n); else printf(分析失败\n);整个字符串消费完、游标正好停在#上才算成功否则失败。至于失败发生在哪个位置、错误字符是什么统统不输出。比如输入baeaaE()第一眼看到b不是e静默返回游标停在 0a[0]是b不是#输出「分析失败」。这没错但没法告诉学生「错误在第一个字符期望e」。真正的递归下降分析器会给每个函数加bool返回值失败时在调用帧里合成错误信息至少能定位到「哪个非终结符在哪个位置匹配失败」。这份代码把错误信息全丢在main的统一判定里属于「能判断对错、不能解释对错」的阶段——用它验证「句子是否属于该文法」够用用它做诊断教学则不够。5. 常见问题排查词法切分与递归下降最容易翻车的五个点把两份代码放在一起跑最值得记住的不是它们跑通时候的样子而是翻车时的表现。下面这五条踩坑记录现象、原因、解决方式都来自这两份实验代码的边界行为排查思路可以迁移到任何手写词法分析器和递归下降分析器上。5.1 现象2A 没被报非法反而输出「数字 2 标识符 A」数字分支在while循环里遇到非数字字符就停后继的A会被下一轮循环当成标识符读走。原因是数字分支只检查了「当前字符是否属于数字类」没有检查「数字串的后继字符是否紧跟字母」。解决方法是数字串读完以后立刻判断如果isLetter(ch)为真说明出现了2A这种非法单词应当直接报错并提示位置不能把它静默拆成两个合法 token。词法分析的原则是「报错要报在最早出现问题的位置」——拆开只会把错推给下游。5.2 现象和--从来没被识别成一个整体词法表里明明有和--两个表项但不管源程序怎么写输出里永远只有两个单独的或两个单独的-。原因是主循环先判断isP(ch)而isP()为真于是直接走单字符运算符分支只读一位就结束。界符分支的while(isJ(ch))本来有能力连续读入两个但isPlus分支优先级更高它根本没机会执行。解决方法是调整判断顺序在处理运算符之前先检查当前字符和后继字符能不能组成、--、:、这类复合符号能组成就走专门分支不能才退化为单字符。这就是最长匹配原则maximal munch在词法分析里的落地——先尝两字符不行再退回一字符。5.3 现象:能识别但::会被静默吞掉isJ对:和都返回真while(isJ(ch))会把:连续读成两个字符在表里查到下标 44正常输出。但如果源程序里写的是::同样会被连续读成::在 23~47 范围里查不到strcmp全不匹配既不输出单词、也不报错等于这个符号凭空消失。原因是界符分支查表失败后没有兜底处理直接continue跳过了。解决方法是查表失败时至少要打印一条「无法识别的符号」消息保留当前字符内容甚至可以回退游标让后续阶段能看到原始输入。词法分析器不能有「安静吞字符」的路径这是排查这类问题最值得记住的一条。5.4 现象递归下降把「第 2 个字符错」报成「整体失败」输入eaE()匹配e成功调用B()B()看到a走B - a C分支C()看到字符串末尾的\0既不是d也不是e静默返回整条链一路静默退到main最后输出「分析失败」。这里没有错报——ea确实不是文法句子——但错误信息完全不可用你不知道是B失败、C失败还是a没匹配上。原因是所有递归函数都没有返回成功/失败标记失败路径全是空的。解决办法是把void改成bool每个函数在成功匹配后返回true失败返回false调用方检查返回值并输出「在游标位置 X 期望字符 Y」。这个改动并不改变文法和识别逻辑但能把黑匣子变成可诊断的白盒。5.5 现象scanf(%s, a)遇到带空格的表达式直接截断%s以空白字符作为输入分隔符所以a b这样的串永远不可能读进来。原因是实验代码为了演示方便选了scanf却没有考虑表达式内部是否允许空格。PL/0 词法里空格是被跳过的语法分析天然容忍输入中间有空格但到了语法层实验输入方式反而限制了这一点。解决方法是换fgets(a, 10, stdin)读整行再去掉末尾换行同时把数组a的容量从 10 加大否则超过 9 个字符的句子会缓冲区溢出这是真正的安全隐患。排查这类问题时要记得输入读取方式决定了测试用例能覆盖的文法复杂度scanf(%s)只适合单词之间无空格的场景。6. 设计取舍查表法、递归下降与那些被简化掉的「债」把两份实验放在一起看会发现它们选择了同一条路线用最少的理论概念实现能跑的分析器。词法层没有上 DFA、没有用哈希表而是「字符分类函数 线性查表」语法层没有用 LL(1) 预测分析表、没有做 FIRST/FOLLOW 集合计算而是「函数体直译产生式」。这个选择不是偷懒而是教学场景下正确的复杂度收缩。PL/0 总共 21 个关键字、25 个符号线性查表的时间开销在数据规模下可以忽略文法只有四条产生式手写递归下降比构造预测分析表更快出成果也更容易把「文法-程序」的对应关系讲清楚。但每一处简化都在还债。查表法把字典和类别码合并成一张表代价是、--这类多字符符号在匹配顺序上吃了亏递归下降没有回溯机制遇到选择冲突只能靠文法本身是 LL(1) 来保证一旦文法出现公共前缀函数就会选错路bool返回值的缺失更是让错误诊断能力趋近于零。这些「债」恰恰是进阶的方向词法层把ktt换成unordered_mapstring,int或 Trie语法层给每个函数加返回值、在失败点输出游标位置再把scanf换成按行读入——三处改动不碰核心算法整个实验的可用性就会跃升一个量级。我一般会建议从这两个实验往真实编译器再迈一步词法分析器改成真正的 DFA递归下降换成带错误恢复的预测分析器你会发现「能跑」和「能诊断问题」之间的距离比想象中大得多。从那以后我每次打开一个词法分析器源码第一件事就是找它的 token 表放在哪第二件事是看多字符符号的匹配顺序是不是最长匹配第三件事是检查查表失败分支是否有输出。这套检查习惯让我避开了不少静默吞字符的坑。希望帮到你。本文还有配套的精品资源点击获取
简介东北大学秦皇岛分校编译原理课程实验报告聚焦PL/0语言词法分析程序的设计与实现系统记录了从实验目的、内容、环境到C源码实现的全过程。报告重点展示了词法分析器如何通过字符分类、关键词表匹配、非法字符检测等步骤将源程序字符串转换为单词类别二元组序列其中对数字、标识符、运算符、界符的识别逻辑均有清晰代码说明并包含错误处理能力例如可识别出“2A”这类非法单词。资源包为单个doc文档体积仅122KB内容紧凑、结构完整适合编译原理初学者对照学习也可作为课程设计或实验报告的写作参考。目前已有98人在CSDN学习下载体现了该资料对相关课程学习的实际帮助。报告中完整的主程序流程、详细的函数注释与输出设计可帮助读者深入理解词法分析在编译器前端的核心作用为后续语法分析、语义分析等环节打下扎实基础。1. 词法分析器与递归子程序为什么 2A 不报错、函数嵌套就是文法这份编译原理实验报告最有意思的地方在于它的词法分析器遇到2A这种非法单词时并不会报错而是心平气和地把它切成两个合法单词——数字2和标识符A。表面上看词法分析是「从左往右逐字符判断」但真正让它 work 的是一张 48 行的常量表加四个字符分类函数实验 4 的递归子程序分析器表面是层层嵌套的函数调用本质却是文法产生式到 C 函数的一一映射。把这两层拆开编译器最前面的黑匣子就算揭开了一半。这也是这份报告值得反复咀嚼的原因——它把编译器原理压缩成了一份能跑、能调试、也能让你踩坑的最小实现。2. 字符分类函数组为什么手写 isLetter 而不是用ctype.h词法分析要做的第一件事是把输入字符流按 ASCII 码值切出「字母、数字、运算符、界符、空白」这五类。PL/0 实验里没有使用 C 标准库ctype.h的isalpha、isdigit而是手写了isLetter和isDigit两个函数。看起来像重复造轮子但这里有一个很实际的理由教学代码要跑在各种编译器上显式写(chA chZ)不依赖语言环境对字符集的定制行为一目了然。另一个原因是标准库的isalpha受 locale 影响在非英文环境下可能把带变音符的字符也算作字母而词法分析要求「字符集边界完全可控」。2.1 isLetter / isDigit字符集硬编码背后的可移植性取舍bool isLetter(char ch) { if ((ch A ch Z) || (ch a ch z)) return true; else return false; } bool isDigit(char ch) { if (ch 0 ch 9) return true; else return false; }这两个函数只做了区间判断大写字母区间、小写字母区间、数字区间。注意它们没有处理EOF的情况也没有把下划线_放进字母集合——这意味着这份词法定义里的标识符不能含下划线max_len、_tmp这类写法在 PL/0 源程序里会被拆成max和len两个符号。代码里char ch0, ch;用的是有符号char当fgetc返回EOF即 -1时被截断成char后与EOF比较在标准 C 里是经典隐患好在此处文件正常结束未触发。字符分类在编译器前端属于热路径每个字符至少要被调用一次。两个布尔函数的代价是常数级比较主循环整体复杂度是 O(n)n 为源程序字符数。可移植性上的收益则是不管换到哪个平台、哪个 C 标准这组判断的结果都完全一致。我一般会这么理解——教学代码把「正确性」放在「高效」之前硬编码区间正是为了在课堂上不用解释 locale 是什么。2.2 isP 与 isJ运算符/界符的集合判定以及注释里被删掉的那行bool isP(char ch) { if (ch || ch * || ch - || ch /) return true; // ch:||ch,||ch||ch;||ch(||ch) 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的集合要大得多逗号、分号、句点、括号、方括号、花括号、比较符、赋值号:的组成字符、结束符#。注意被注释掉的那行ch:||ch,||ch||ch;||ch(||ch)——这是词法分析器设计上的「活化石」写代码的人曾经想把冒号、逗号、等号、分号、括号都归入isP后来删掉了。这个删除动作直接影响后续匹配顺序四则运算符在主循环里走「单字符运算符」分支查表范围是 34~37而冒号、等号、括号等走「界符」分支查表范围是 23~47。这个划分不是随意的。四则运算符在 PL/0 里都是单字符符号不需要向后看而:、、、、..这类多字符符号必须由isJ配合while循环连续读取才能拼完整。把「能组成复合符号的字符」和「不能组成复合符号的字符」分开本质上是在字符层面预先做了「最长匹配」的粗筛。代价是优先级问题同时也是的第一个字符但因为isP分支先被命中永远无法作为一个整体被识别——这个坑在第 5 章会展开讲。2.3 isBlank 与换行被忽略的字符也是词法的一部分bool isBlank(char ch) { if (ch || ch \t) return true; else return false; }空白字符在词法分析里不产生单词但它是词法分析器必须处理的输入。如果isBlank不存在空格和制表符会落到「无法识别」的分支要么报错要么静默吞掉。这份代码里空格和制表符被直接跳过\t之外的空白比如换行\n没有被isBlank吸收而是单独在主循环的else分支处理每遇到一个换行就把当前累积的单词类别串ste打印一行然后重置。也就是说换行符在这里承担了双重职责一是源码里的普通字符二是「输出缓冲区的刷新信号」。这个设计透露出实验报告的定位它要演示的不只是「把单词切出来」还要把「切出来的类别序列」按源代码行组织好方便肉眼核对。实际编译器的词法分析器不会让换行承担输出职责——行号信息需要单独维护空白要么丢弃要么变成 token 传给语法层。但在教学实验里这种「一行源程序对应一行输出」的映射能让学生直接看到CONST、VAR、PROCEDURE每行的单词序列验证成本低得多。要从这份代码里学到的不是「换行就该这么处理」而是「词法分析器可以自定义字符的语义关键是让这个语义在代码里保持一致」。3. ktt 常量表与类别码词法分析的词典机制藏在哪四个分类函数把字符切成了「字母流」「数字流」「符号流」但「这个单词是不是关键字」「这个符号对应什么类别」答案都藏在主循环开头定义的那张 48×20 的二维字符数组里。这是整份代码的核心数据结构也是一般初学者最容易忽略的部分——他们盯着while循环看半天却不知道真正做决策的是这张表。3.1 0~20 关键字、21/22 预留、23~47 符号一张表三种区char ktt[48][20] { and, begin, const, div, do, else, end, function, if, integer, not, or, procedure, program, read, real, then, type, var, while, write, 标识符, 无符号数, ,, ;, :, ., (, ), [, ], .., , --, , -, *, /, , , , , , , :, {, }, # };这张表的布局是有讲究的下标 0~20 是 PL/0 的 21 个关键字下标 21、22 分别预留给「标识符」和「无符号数」两种抽象类别下标 23~47 是 25 个具体符号。也就是说ktt里存的并不全是「单词」还包括了两个「类别占位符」。当主循环识别出一个关键字时比如begin它通过strcmp找到begin在下标 1 的位置于是类别码就是 1当它识别出一个查不到关键字的字母串时直接给类别码 21。类别码本身就是查表得到的下标省掉了一次「单词→二进制编码」的二次映射。这种把「字典」和「类别编码表」合并成一张二维数组的写法是编译器教科书里标准的表驱动思想数据驱动逻辑代码里不写死任何关键字。想加一个关键字只需要往数组里插一项想改单词的类别改一行数据即可。我一般会这么理解——这张表就是词法分析器的「词典」查表命中就是这个词在词典里有条目查不到就归类为「标识符」这个兜底类别。真正的词法分析器里这张表多半换成哈希表或 Trie但抽象模型完全一致。3.2 线性查表与 strcmp48×20 的代价为什么可以接受字母和数字分支的查表逻辑分别是这样的for (j 0; j 21; j) { int t strcmp(str, ktt[j]); if (t 0) { stringstream ss; ste |; ss ste; ss j; ss ste; break; } } if (j 21) { ste ste | 21; }字母串str先用strcmp依次和 0~20 的关键字比较命中则类别码为j否则归为标识符。数字串则完全不查表直接给类别码 22。界符分支用while(isJ(ch))连续读入若干字符组成一个串再在 23~47 的范围里线性查找。整个过程没有哈希、没有二分就是最朴素的顺序扫描。这种实现的时间复杂度是 O(n×21×20)n 是单词数21 是关键字的表项数20 是每项最大长度。实际 PL/0 源程序通常几百到几千个单词这个复杂度在 Windows PC 上肉眼完全无感。换成哈希表能将平均复杂度降到 O(n)但代码量会从几行膨胀到几十行还要设计哈希函数和冲突处理——在教学实验场景下这个「足够好」的取舍是合理的。真正的教训在这里优化必须建立在能正确运行的基础上先让查表逻辑跑通再谈查询效率。如果你动手改这份代码建议把ktt的维度换成vectorstringstrcmp换成可读性会立刻上一个台阶。3.3 错误检测的真实行为2A 被切成「2」和「A」而不是报错实验要求里写着「有一定检查错误的能力例如发现 2A 这类不能作为单词的字符串」但看代码的实际行为if (isDigit(ch)) { int i 0; while (isDigit(ch) || ch .) { str[i] ch; ch src[pos]; } str[i] \0; ste ste | 22; cout str; continue; }遇到字符2时进入数字分支。while循环的条件是「当前字符是数字或点」于是它读走2下一个字符是A不是数字也不是点循环停止。数字串2被输出类别码 22。外层循环继续A进入字母分支被读成标识符。最终输出的是两个合法单词数字2和标识符A。所谓的「发现 2A 非法字符串」的能力在这个代码里并没有真正实现。为什么会出现要求与实现的偏差因为数字分支只判断了「当前字符属于数字类」没有检查「数字串的后继字符是否紧跟着字母」。如果2A是一个变量名或者写错了的常量词法分析器应当报「非法单词」但这份代码选择了把它静默拆开。这种「拆开」在有些场景下是有意为之——比如把1e3拆成1和e3虽然语义不对但至少不会让词法分析器崩溃。可对于 PL/0 这种教学语言2A必须被标记为错误否则语法分析器拿到的是两个合法 token错误会在更后面的阶段以更诡异的方式暴露。排查思路很简单在数字串读完后加一句if (isLetter(ch))就报错。4. 递归子程序分析器为什么产生式右部能直接翻译成函数体实验 4 的递归子程序分析器处理的文法很短G[E]: E - e B a A A - a | b A c B B - d E d | a C C - e | d C代码结构更短四个函数E()、A()、B()、C()加一个全局字符数组和游标。这段代码如果只看表面就是「几个函数你调我、我调你」但把它和文法并排放在一起会发现每个函数体就是一条产生式右部的直译。这就是递归下降分析法recursive descent parsing的核心一种把 BNF 文法机械翻译成程序的方法。4.1 左部就是函数名右部展开成语句序列void E() { if (a[s] e) { s; B(); if (a[s] a) { s; A(); } } }对应产生式E - e B a A。函数体从左到右依次做了四件事匹配终结符e、调用B()、匹配终结符a、调用A()。终结符的匹配方式是「如果当前字符就是要找的那个游标后移一位」非终结符的匹配方式是「调用以它命名的函数」。反过来如果当前字符不是期望的终结符函数什么都不做静默返回——注意没有else报错这是后面要说的致命简化。为什么这样翻译能 work递归下降的约定是每个非终结符对应一个函数函数成功返回表示「该非终结符已经完整匹配」。E()里先调B()B()内部会完全消化掉B能推导出的子串等B()返回时游标正好停在B推导串的下一个位置E()再检查那个位置是不是a。这种「函数调用就是非终结符展开」的映射让文法的递归特性直接变成了程序里的函数递归。E的定义里间接引用了E自己通过B - d E d所以E()函数里会出现B()的调用而B()里又有E()的调用形成互相递归。4.2 终结符用 if、非终结符用调用选择分支的翻译规则A - a | b A c B是两条产生式的并集翻译出来就是一个多分支void A() { if (a[s] b) { s; A(); if (a[s] c) { s; B(); } } else if (a[s] a) { s; } }这里体现了递归下降的选路规则当前字符是b就走第一条分支当前字符是a就走第二条分支。它只靠「当前这一个字符」决定走哪条路不需要向前多看几个字符——这就是 LL(1) 文法的直觉一个 lookahead 符号足以决定推导方向。这份文法恰好是为 LL(1) 设计的每个非终结符的候选产生式都以不同的终结符开头不存在「两个候选都能匹配」的冲突。如果文法是左递归的比如E - E T这种翻译直接写成函数就会无限递归E()第一步调用E()永远不前进。所以递归下降要求文法先消除左递归这也就是为什么实验给的是右递归版本A - b A c B右递归在递归下降里表现为函数A()自己调用自己但每次调用至少先消费一个b递归深度有限。给代码加点注释会看得更清楚void C() { if (a[s] d) { s; C(); // C - d C右递归逐个消费 d } else if (a[s] e) { s; // C - e递归出口 } }C - d C | e的语义是「若干个d后跟一个e」。翻译成C()后每次遇到d就消费掉并递归调用自己直到遇到e再消费并返回。这里能直观看到右递归与while循环的等价性C()的递归深度等于d的个数如果源程序里有 1000 个连续的d函数调用栈就会压 1000 层。实际编译器里这种写法有栈溢出的风险但教学实验的输入规模不会触发。4.3 全局数组与游标 s显式状态机与错误恢复的缺失char a[10]; int s 0;这个设计的要点是所有函数共享同一个字符数组a和同一个游标s。函数之间不需要传参、不需要返回值B()消费了多少字符E()通过s的位置变化就能感知。递归下降的教科书实现通常会把这个游标作为参数传递或封装成TokenStream对象但实验代码选择了全局变量省掉一切传参噪音。这是教学代码的常见简化代价是不能同时跑两个分析实例也不能在多个输入串之间切换状态。更关键的问题是错误恢复缺失。所有函数的失败路径都是静默返回连布尔值都不给。看看main里的判定E(); if (a[s] #) printf(句子结构正确\n); else printf(分析失败\n);整个字符串消费完、游标正好停在#上才算成功否则失败。至于失败发生在哪个位置、错误字符是什么统统不输出。比如输入baeaaE()第一眼看到b不是e静默返回游标停在 0a[0]是b不是#输出「分析失败」。这没错但没法告诉学生「错误在第一个字符期望e」。真正的递归下降分析器会给每个函数加bool返回值失败时在调用帧里合成错误信息至少能定位到「哪个非终结符在哪个位置匹配失败」。这份代码把错误信息全丢在main的统一判定里属于「能判断对错、不能解释对错」的阶段——用它验证「句子是否属于该文法」够用用它做诊断教学则不够。5. 常见问题排查词法切分与递归下降最容易翻车的五个点把两份代码放在一起跑最值得记住的不是它们跑通时候的样子而是翻车时的表现。下面这五条踩坑记录现象、原因、解决方式都来自这两份实验代码的边界行为排查思路可以迁移到任何手写词法分析器和递归下降分析器上。5.1 现象2A 没被报非法反而输出「数字 2 标识符 A」数字分支在while循环里遇到非数字字符就停后继的A会被下一轮循环当成标识符读走。原因是数字分支只检查了「当前字符是否属于数字类」没有检查「数字串的后继字符是否紧跟字母」。解决方法是数字串读完以后立刻判断如果isLetter(ch)为真说明出现了2A这种非法单词应当直接报错并提示位置不能把它静默拆成两个合法 token。词法分析的原则是「报错要报在最早出现问题的位置」——拆开只会把错推给下游。5.2 现象和--从来没被识别成一个整体词法表里明明有和--两个表项但不管源程序怎么写输出里永远只有两个单独的或两个单独的-。原因是主循环先判断isP(ch)而isP()为真于是直接走单字符运算符分支只读一位就结束。界符分支的while(isJ(ch))本来有能力连续读入两个但isPlus分支优先级更高它根本没机会执行。解决方法是调整判断顺序在处理运算符之前先检查当前字符和后继字符能不能组成、--、:、这类复合符号能组成就走专门分支不能才退化为单字符。这就是最长匹配原则maximal munch在词法分析里的落地——先尝两字符不行再退回一字符。5.3 现象:能识别但::会被静默吞掉isJ对:和都返回真while(isJ(ch))会把:连续读成两个字符在表里查到下标 44正常输出。但如果源程序里写的是::同样会被连续读成::在 23~47 范围里查不到strcmp全不匹配既不输出单词、也不报错等于这个符号凭空消失。原因是界符分支查表失败后没有兜底处理直接continue跳过了。解决方法是查表失败时至少要打印一条「无法识别的符号」消息保留当前字符内容甚至可以回退游标让后续阶段能看到原始输入。词法分析器不能有「安静吞字符」的路径这是排查这类问题最值得记住的一条。5.4 现象递归下降把「第 2 个字符错」报成「整体失败」输入eaE()匹配e成功调用B()B()看到a走B - a C分支C()看到字符串末尾的\0既不是d也不是e静默返回整条链一路静默退到main最后输出「分析失败」。这里没有错报——ea确实不是文法句子——但错误信息完全不可用你不知道是B失败、C失败还是a没匹配上。原因是所有递归函数都没有返回成功/失败标记失败路径全是空的。解决办法是把void改成bool每个函数在成功匹配后返回true失败返回false调用方检查返回值并输出「在游标位置 X 期望字符 Y」。这个改动并不改变文法和识别逻辑但能把黑匣子变成可诊断的白盒。5.5 现象scanf(%s, a)遇到带空格的表达式直接截断%s以空白字符作为输入分隔符所以a b这样的串永远不可能读进来。原因是实验代码为了演示方便选了scanf却没有考虑表达式内部是否允许空格。PL/0 词法里空格是被跳过的语法分析天然容忍输入中间有空格但到了语法层实验输入方式反而限制了这一点。解决方法是换fgets(a, 10, stdin)读整行再去掉末尾换行同时把数组a的容量从 10 加大否则超过 9 个字符的句子会缓冲区溢出这是真正的安全隐患。排查这类问题时要记得输入读取方式决定了测试用例能覆盖的文法复杂度scanf(%s)只适合单词之间无空格的场景。6. 设计取舍查表法、递归下降与那些被简化掉的「债」把两份实验放在一起看会发现它们选择了同一条路线用最少的理论概念实现能跑的分析器。词法层没有上 DFA、没有用哈希表而是「字符分类函数 线性查表」语法层没有用 LL(1) 预测分析表、没有做 FIRST/FOLLOW 集合计算而是「函数体直译产生式」。这个选择不是偷懒而是教学场景下正确的复杂度收缩。PL/0 总共 21 个关键字、25 个符号线性查表的时间开销在数据规模下可以忽略文法只有四条产生式手写递归下降比构造预测分析表更快出成果也更容易把「文法-程序」的对应关系讲清楚。但每一处简化都在还债。查表法把字典和类别码合并成一张表代价是、--这类多字符符号在匹配顺序上吃了亏递归下降没有回溯机制遇到选择冲突只能靠文法本身是 LL(1) 来保证一旦文法出现公共前缀函数就会选错路bool返回值的缺失更是让错误诊断能力趋近于零。这些「债」恰恰是进阶的方向词法层把ktt换成unordered_mapstring,int或 Trie语法层给每个函数加返回值、在失败点输出游标位置再把scanf换成按行读入——三处改动不碰核心算法整个实验的可用性就会跃升一个量级。我一般会建议从这两个实验往真实编译器再迈一步词法分析器改成真正的 DFA递归下降换成带错误恢复的预测分析器你会发现「能跑」和「能诊断问题」之间的距离比想象中大得多。从那以后我每次打开一个词法分析器源码第一件事就是找它的 token 表放在哪第二件事是看多字符符号的匹配顺序是不是最长匹配第三件事是检查查表失败分支是否有输出。这套检查习惯让我避开了不少静默吞字符的坑。希望帮到你。本文还有配套的精品资源点击获取
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
