PL/0扫描器与递归下降解析：类别码、最长匹配和LL(1)实践

简介东北大学秦皇岛分校编译原理课程实验报告面向正在学习词法分析、需要完成PL/0语言词法分析程序设计与实现的学生。文档围绕词法分析器的输入输出、单词与类别二元组生成、非法字符串检测等任务展开结合C环境说明字符分类函数、关键词表匹配、源文件读取和逐字符处理流程并附有可参考的实验代码与结果输出思路便于对照理解GETSYM的工作方式及常见错误处理。压缩包共1个doc文件约122KB篇幅集中适合课程实验复盘、报告撰写参考和代码实现查漏补缺。已有102人学习对刚接触编译原理、希望把词法分析流程落到实处的读者较有借鉴价值。1. 词法分析不是“切词”是给编译器立一套不会歧义的编号很多人翻开编译原理实验报告第一反应是照着课本抄一个扫描器跑通交差。真正值得琢磨的是另一件事词法分析器输出的为什么不是一堆字符串而是一堆「单词 类别码」的二元组材料里的 PL/0 扫描器把write编成 20、把标识符统一编成 21、把无符号数编成 22第一眼看挺反直觉——明明知道单词长什么样为什么还要多套一层整数编号答案在于一旦下游只认这几十个整数整个前端就拿到了一条极强的不变量任何记号的身份都能用一次整数比较敲定字符串比较被彻底赶出了语法分析阶段。这份材料真正能教给人的不是 C 语法而是这条不变量靠字符分类、关键字查表、最长匹配三条规则共同守住的全过程。2. 字符分类与关键字查表扫描器的骨架为什么长这样字符流的可能性是 128 个 ASCII 码位而一门语言的记号种类只有几十个。扫描器的全部工作就是把这个无限长的字符序列收敛到有限的类型集合上。收敛动作分成两层第一层在字符粒度上判定“这个字符能开启哪类记号”第二层在记号粒度上判定“这个串到底属于哪个具体类型”。两层之间靠一张表连接。2.1 五个 isXxx 谓词判据不是“它是什么”而是“后面还能接什么”// 字符级判定把 ASCII 空间切成互斥的几块是后续所有分支的前提 bool isLetter(char ch){ // 字母标识符与关键字的唯一合法起点 return (chAchZ)||(chachz); } bool isDigit(char ch){ // 数字无符号数的唯一合法起点 return ch0ch9; } bool isP(char ch){ // 单字符运算符不可能有第二个字符 return ch||ch-||ch*||ch/; } bool isJ(char ch){ // 界符其中一部分允许两字符组合 return ch,||ch;||ch.||ch(||ch)|| ch[||ch]||ch||ch:||ch|| ch||ch{||ch}||ch#; } bool isBlank(char ch){ // 空白不产生记号只影响排版 return ch ||ch\t; }这五个函数都只接收一个char、返回bool、没有副作用所以可以被反复调用而不改变扫描状态。它们的定位不是“分类器”而是“入口判据”主循环只看当前字符落在哪个谓词里就决定走哪条处理分支进入分支之后同一个谓词又被拿来判断“还能不能继续吞”。 - * /被单独拆成isP而 :留在isJ里这个拆分不是随手写的。 - * /在语言里永远只占一个字符而 :都可能由两个字符组成必须和, ; .这类纯单字符界符走同一条“允许变长”的处理路径。换句话说谓词的划分依据不是“符号长得像不像”而是“这个位置有没有可能多读一个字符”。这条区分在真正动手改代码时非常关键因为一旦把变长和定长混进同一个分支后面的吞字符循环迟早会把两个相邻的短记号粘成一个长串。还有一个容易忽略的点isLetter只覆盖英文字母没有处理下划线。教材里的 PL/0 标识符确实只允许字母开头但很多人从别的语言迁移过来下意识会把_加进去结果就是关键字表里那 21 项全是纯字母标识符却出现了下划线两边规则不一致。要么两边都放行要么两边都不放行别只改一半。2.2 最长匹配数字分支里那个被低估的 while 循环if(isDigit(ch)){ // 当前字符是数字进入无符号数分支 int i0; while(isDigit(ch)||ch.){ // 贪心向后读直到遇到既不是数字也不是点 str[i]ch; chsrc[pos]; // 读头前移注意这一步在循环体内 } str[i]\0; steste|22; // 类别码 22 直接拼进累积串 coutstr; continue; // 跳出后 ch 已经是下一个记号的第一个字符 }这段循环体现的是词法分析里最核心的一条规则最长匹配。当扫描器看到一个1它无法立刻断定这是常数1还是常数123的开头只能一路往后读直到读到第一个不可能属于这个记号的字符为止。循环结束时ch停在那个“越界”的字符上而这个字符没有被消费掉它必须作为下一个记号的起点被重新判定。continue的作用就是跳过循环体末尾的推进语句让控制流回到while(ch!#)重新做一次入口判断。参数上i是写入缓冲区str的下标pos是全局读头位置两者不共享。这里用了一个长度为 20 的局部数组承接结果超过长度就会写越界属于典型的教学代码简化——真实扫描器要么用std::string动态追加要么在写入前判断i sizeof(str)-1。最长匹配的代价是它只认局部信息。1.2.3会被吞成一个记号1.2.3.4也是因为循环只判断“是不是数字或点”从不验证点的数量。更麻烦的是.5这种写法.本身是isJ的成员主循环会先把.判成界符送进界符分支根本轮不到数字分支处理于是.5被拆成.和5两个记号。这不是 bug而是规则顺序的必然结果——入口判断的优先级决定了哪些写法被允许。如果确实需要支持.5只能把数字判定条件改成“数字开头或者点后面紧跟数字”代价是入口判据从单字符判断升级成需要向前看一位的判断。2.3 关键字表 ktt为什么标识符的类别码刚好是 21表里的 48 个位置是按类型分段排的下标本身就是类别码下标区间内容说明0 – 2021 个关键字andbeginconst…whilewrite21标识符所有用户自定义名字共用这一个码22无符号数所有数字字面量共用这一个码23 – 46界符与运算符,;:.()[]..-*/:{}47#结束符只用于终止扫描不参与查表标识符用统一的 21、而不是“21 序号”背后是一条边界划分原则扫描阶段只回答“这是什么种类”不回答“这是哪一个”。A和B都是标识符具体是哪个由后面的符号表去区分。如果把编号做成“每个标识符一个码”那编号空间就不再是有限的 48 个而是随源程序规模增长下游就无法用固定大小的判定表做分派。这条原则在很多真实编译器里被推到极致——类别码是个枚举标识符的文本被单独存进字符串池语法分析器拿到的永远是一个小整数。关键字查表用的是strcmp逐个比对找到就break循环变量j的最终值承担了“是否命中”的语义for(j0;j21;j){ // 只在关键字段里找 if(strcmp(str,ktt[j])0){ stringstream ss; ssste|j; // 命中类别码就是表下标 ssste; break; } } if(j21){ steste|21; } // 循环跑满仍未命中说明是标识符这里依赖“for正常结束则j等于上界”这一语言细节来表达“没找到”。写法在教材里很常见但它把“查表结果”编码进了循环变量任何人后来把for改成while、或者加一个if提前break这个判定就静默失效了。我在自己写这类代码时更倾向于把查表抽成独立函数命中返回下标未命中返回-1调用点只判断返回值不关心循环怎么写的。3. 扫描节奏pos指针、ch超前读与ste缓冲的三方配合理解一个扫描器最快的办法是把它的“读头”模型画清楚。这段代码里只有一个真正的状态变量posch是src[pos]的一份快照ste则是输出侧的累积缓冲区。三者之间的推进约束决定了程序会不会死循环、会不会丢字符。3.1chsrc[pos]这个惯用法埋了什么主循环的骨架是chsrc[pos]; // 取当前字符同时把读头推到下一个位置 while(ch!#){ // # 由 src# 在末尾兜底补上 if(isDigit(ch)){ /* 数字分支内部自行推进 ch 和 pos */ continue; } else if(isLetter(ch)){ /* 标识符分支同上 */ continue; } else if(isP(ch)){ /* 运算符分支 */ continue; } else if(isJ(ch)){ /* 界符分支内部循环推进 */ continue; } else if(isBlank(ch)){ chsrc[pos]; continue; } else{ /* 换行或其他刷出缓冲 */ } chsrc[pos]; // 只有走到这里才由循环体统一推进 }这套写法的隐含契约是每条continue之前分支自己必须负责把ch推进到下一个待判定字符否则就会原地打转。数字分支靠while里的chsrc[pos]完成推进标识符分支同理运算符分支在手动读了第二个字符后又单独推了一次界符分支在while(isJ(ch))里推进。运算分支和界符分支的推进逻辑分散在不同位置一旦有人给某个分支加了个if提前return或者提前continue读头就不再前进程序立刻进入死循环。src#这一步是把结束符手动补到输入串末尾。它的作用是让主循环有一个天然的终止条件——源文件读进来之后不管最后是什么字符末尾总有一个#在等着。这个技巧省掉了每次读字符时判断EOF的麻烦但也带来了一个副作用后面排查章节会细说。3.2 换行才刷缓冲ste的累积与二元组的输出时机ste是一个字符串每识别出一个记号就把| 类别码拼到它尾部。真正把它打印出来是在遇到换行的时候else{ // 当前字符既不是数字字母也不是运算符界符空白 coutsteendl; // 把本行的类别码序列刷出去 ste ; // 重置缓冲注意带了一个前导空格 }换行本身不是记号的边界用换行做刷出单位纯粹是对齐源程序的排版方便人眼对照。这套“累积 → 换行刷出”的机制在两个地方露出了粗糙ste被初始化为一个带空格的字符串 导致每行输出的开头都多一个空格拼出来的序列是|20|21|38这种形状拼接用的是steste|22和stringstream两种方式混写可读性差但结果一致。从机制上看这份缓冲设计暴露出词法分析器的一个真实职责分工扫描器逐个产出记号调用方这里是cout负责成批消费。教材里的 PL/0 的GETSYM用的是另一个模型——每调用一次GETSYM就返回一个sym同时把具体的标识符或数值填到全局变量id、num里。那种模型下没有缓冲区因为语法分析器是主动“拉”记号的这段代码是主动“推”记号的所以需要缓冲区。两种模型对词法分析逻辑没有任何影响只影响接口形态。3.3 和教材GETSYM的差距省掉的恰恰是最难的部分对比 PL/0 原始版的GETSYM这段实现少了四样东西每一样都不是可有可无的装饰符号表原始版在识别出标识符后不做任何登记因为词法层确实不需要但只要词法层想区分“第一次出现的名字”和“重复定义的名字”就必须引入符号表结构。行号计数GETSYM维护一个line变量出错时能报出“第几行第几列”。这段实现完全没有行号出错只能靠人肉数换行。双字符界符的正确合并原始版对:是显式两字符判断先读一个再看下一个这段实现靠while(isJ(ch))一路吞吞得对不对全靠运气。错误恢复原始版遇到非法字符会跳过并继续保证一次扫描能报出多个错误这段实现遇到不认识的分支直接落到换行逻辑上等于把错误字符静默丢弃。四样里的后两个是这份代码在真实使用中最容易翻车的地方也是“跑通测试用例”和“实现一个扫描器”之间的分水岭。测试用例里刚好没出现两个相邻界符所以循环吞字符的行为看起来正常一旦换成);这种组合问题立刻暴露。4. 递归下降把文法产生式直接抄成函数凭什么能跑实验的第二个任务是给一个四非终结符的文法写递归子程序分析器。文法长这样G[E]: E → eBaA A → a | bAcB B → dEd | aC C → e | dC四个非终结符对应四个函数每个函数体内用一个if-else链对应产生式的多个候选。看起来像是把 BNF 逐字翻译成了代码这种“翻译”之所以成立背后有两条硬性条件。4.1 First 集决定if的先后顺序也决定了能不能不回溯对每个非终结符算它的候选首符号集First 集非终结符候选First 集EeBaA{e}Aa/bAcB{a}/{b}BdEd/aC{d}/{a}Ce/dC{e}/{d}四条产生式里凡是候选多于一个的A、B、C各自候选的 First 集两两不相交。这意味着解析器只要看当前字符一眼就能唯一确定该走哪个候选不需要“先试第一个失败了退回来再试第二个”。这就是 LL(1) 的定义性条件也是递归下降能写成无回溯if-else的全部依据。void A(){ if(a[s]b){ // 候选 bAcB 的 First 集是 {b} s; // 吃掉终结符 b A(); // 递归展开非终结符 A if(a[s]c){ // 吃掉终结符 c s; B(); // 递归展开非终结符 B } } else if(a[s]a){ // 候选 a 的 First 集是 {a} s; // 吃掉终结符 a产生式结束 } }函数里的顺序不是随便排的先判b再判a是因为这两个字符互斥谁先谁后都对但如果把文法改成A → aX | aY两个候选的 First 集都是{a}这个if-else结构立刻失效——解析器看完a仍然不知道该走哪条路只能改成“先按 X 解析失败则回退到a之后重新按 Y 解析”。回退意味着s要能被还原意味着每个函数都要保存进入时的s值意味着最坏情况下指数级的重复解析。递归下降的简洁性是用“文法必须满足 LL(1)”这个约束换来的不是白给的。4.2 全局下标s递归下降的“栈”藏在调用栈里四个函数都不带参数共享一个全局数组a和一个全局下标s。s是输入串上的读头s的动作就是“消费一个终结符”。这个设计的关键在于递归调用本身就是栈。以A的bAcB分支为例执行顺序是“吃掉b→ 递归解析一个完整的A→ 吃掉c→ 解析一个完整的B”。在吃掉b之后、递归A()之前解析器必须记住“我回来之后还要吃掉一个c、再解析一个B”。这条待办事项没有被存进任何显式数据结构它就存在 C 语言调用栈的返回地址里——A()返回时程序自然回到if(a[s]c)那一行继续。这解释了为什么递归下降不需要手写栈每个非终结符的“未完成工作”恰好等价于一次函数调用。也解释了为什么它怕深递归——文法嵌套越深调用栈越深源程序里一个长得离谱的嵌套表达式就能把栈撑爆。真实编译器在这一点上通常会设一个最大嵌套层数超了就报“嵌套过深”。4.3B → dEd里嵌了E间接递归为什么安全左递归为什么致命文法里最值得多看一眼的是B → dEd。E出现在B的产生式内部而E的第一个产生式又是eBaAB又回到了E的展开路径里。这种互相引用看起来像是循环但它和“左递归”是两回事。判断标准很简单看递归发生时读头有没有前进。B → dEd要求先吃掉一个d才去展开E读头前进了所以展开E的规模严格小于展开B的规模递归一定会收敛。而如果写成E → Ea展开E的第一步又是展开E读头一个字符都没动函数会无限自我调用直到栈溢出。B → dEd里这个d实际上扮演了分隔符角色它保证了E的展开边界是明确的。这条规则在很多手写解析器里被反复踩坑只要把文法写成Expr → Expr Term代码就跑不起来必须改写成Expr → Term ( Term)*的右递归形式把“先消费一个终结符”这件事提到递归之前。5. 排查这两份实验代码最容易翻车的几个点把这段代码当“能跑就行”的作业和把它当“理解扫描器机制”的样本会踩到完全不同的坑。下面几条是照着这两份代码实际动手改的时候几乎必然撞上的。5.1 词法分析器上的踩坑记录现象一输入2A不报错反而顺利输出两个记号。原因数字分支的while(isDigit(ch)||ch.)遇到A立刻停止退出时ch停在A上主循环重新进入入口判断把A当成标识符的开头正常处理。两个记号都“合法”错误从来没被触发。实验要求里明确写着要能发现2A这类串但代码里没有任何一处检查“数字后面能不能紧跟字母”。解决在数字分支的while结束、str收尾之后加一句判断——如果ch仍然是字母说明数字和字母贴在一起了报“数字后不能紧跟字母”并把这个错误连同当前行号一起输出。判断要放在continue之前否则读头已经交给下一轮了。现象二源程序里出现);这种相邻界符时两个记号被粘成一个匹配失败后静默丢弃。原因界符分支用的是while(isJ(ch))只要下一个字符还是界符就继续往str里塞。(和)都是isJ的成员;也是所以);会被吞成一个两字符的串);到 23–46 的表段里一比对找不到任何匹配项。而查找循环结束后代码没有对“未命中”做任何处理既没输出也没报错这两个记号就此消失。解决界符的识别顺序必须反过来——先尝试两字符组合查.. -- :这七个双字符项不命中再回退一格、按单字符查表。回退的动作就是把读头退回去一个位置pos--或等价的s--。这一步是词法分析里少见的“必须能后退”的场景写惯了只向前读的扫描器很容易在这里翻车。现象三源程序里出现#就直接截断后面的内容全部不分析。原因主循环的终止条件是while(ch!#)而末尾又用src#手动补了一个结束符。如果源程序本身含有#比如某些教学方言拿它做注释引导符扫描会在第一个#处停下文件后半段完全被忽略而且不报任何错。更麻烦的是isJ把#判成了界符可界符查表的范围是j47第 47 项恰好就是#永远查不到——两条规则对#的处理互相矛盾却因为循环提前终止而掩盖了。解决把“文件结束”和“记号#”彻底分开。读文件时用真正的 EOF 判断终止#如果有语法含义就正常走界符分支并给它一个类别码如果没有含义就报非法字符。用同一个字符身兼二职是这类扫描器里最难查的一类问题。5.2 语法分析器上的踩坑记录现象四语法分析程序编译不过报While未声明。原因main里写的是While(1){...}首字母大写。C 区分大小写While不是任何已声明的标识符。这类问题在实验报告里很常见因为代码是手抄或者跨环境粘贴的肉眼扫过去完全正常。解决改成小写while(1)。但更值得顺手处理的是循环本身——while(1)加scanf(%s,a)的组合一旦用户输入的串长度超过数组边界这里只有 10 字节就会直接踩坏相邻内存。正确做法是用fgets加长度限制或者在scanf里写%9s。这个习惯比起“改个大小写”重要得多因为数组越界不会当场报错它会在别的地方以完全无关的形式炸开。现象五明明是正确的串判定失败或者错误的串判定成功。原因解析函数在匹配失败时什么都不做直接返回s不前进上层函数接着自己的流程走。比如E()里if(a[s]e)不成立时函数直接返回调用方拿不到任何“这里出错了”的信号只能靠最后检查a[s]#来判断成败。问题在于某个分支失败后s停在原地后续的检查可能恰好落在#上于是错误输入被判成正确。解决让每个解析函数返回布尔值失败就立刻向上传播不要等到最外层再统一判断。同时把s的位置和期望字符一起报出来——只报“分析失败”四个字对定位问题毫无帮助。这里有个血泪经验调试递归下降时最有效的办法是在每个函数入口打印一次函数名和当前字符看一眼调用序列就知道它在哪一步走岔了。6. 设计取舍预测式分析把复杂度挪到了哪里这两份实验代码放在一起看能看出一个贯穿编译器前端的共同思路把运行时的搜索成本提前挪到文法设计阶段一次性付清。词法层的体现是最长匹配。扫描器看到1时不做任何猜测一路读到读不动为止这个规则简单到可以用一个while表达完。代价是它放弃了上下文——1.2.3会被当成一个数typedef名字在 C 里到底是类型还是标识符词法层永远分不清只能交给语法层用上下文判断。用局部贪心换全局简洁这是词法分析的既定取舍。语法层的体现是 LL(1)。只要文法满足 First 集不相交递归下降就能写成无回溯的if-else每个字符只被看一次复杂度是线性的。代价是文法必须被改造成 LL(1) 形式提左公因子、消除左递归、必要时引入新的非终结符。这份实验里的四个产生式天生就是 LL(1) 的所以代码看起来毫不费力一旦换成带公共前缀的文法同一个写法就得加入回溯最坏情况退化成指数级。方案语法约束运行时开销适合场景无回溯递归下降文法必须是 LL(1)每个字符看一次手写解析器、教学语言带回溯递归下降无最坏指数级文法不规则、输入规模小表驱动 LL(1)文法必须是 LL(1)查表 显式栈自动生成解析器自底向上移进归约更强可处理左递归移进归约动作 状态栈工业级语言的完整语法我自己的习惯是只要动手写扫描器先把类别码表完整打印出来逐项核对每个字符落进哪个谓词、每个谓词的分支会不会互相抢字符写递归下降之前先把每个非终结符的 First 集列成一张表确认两两不相交再动键盘。这两步各花不到十分钟能省掉后面大半天盯着调用序列猜哪里走岔的时间。从那以后我每次写这类解析代码都强制先把“读头什么时候前进”这件事在纸上标一遍再落成s的位置。希望帮到你。本文还有配套的精品资源点击获取