编译原理实验报告：词法分析器与递归下降解析器实现剖析

简介东北大学秦皇岛分校编译原理课程实验报告围绕PL/0语言的词法分析程序设计展开完整记录词法分析器的构建与调试过程适合高校计算机专业学生及编译原理初学者作为实验参考与模板。压缩包内含1个doc格式报告文档仅122KB内容精炼完整目前已有98人学习下载。报告详细展示了在Windows环境下使用C编写词法分析器的全过程包括字符类别判断函数isLetter、isDigit、isP、isJ、isBlank、关键词表匹配、运算符与界符识别以及将源程序字符串转换为“单词-类别”二元组序列的输出逻辑同时具备对“2A”等非法单词的错误检测能力。此外报告还附有可运行的程序源码、实验目的、详细流程与总结能帮助读者深入理解词法分析在编译过程中的作用并为后续语法分析、语义分析及代码生成等编译器组件的学习打下扎实基础。1. 编译原理实验报告一份藏着可运行词法分析器与递归下降解析器的完整代码很多人对编译原理的第一印象是理论课直到自己动手写词法分析程序才发现课本上的状态转换图落地成代码有多容易翻车。我拿到这份名为《编译原理实验报告》的课程资源时本以为只是作业存档读完才发现里面有两份能直接跑起来的C源码一份是针对PL/0语言的词法分析器一份是递归子程序语法分析器。前者把源程序逐字符拆成单词类别二元组序列后者用四个互递归函数完成指定文法G[E]的句子判定。适合正在上编译原理课、需要交词法/语法分析实验的学生也适合想快速复习经典实现的开发者——代码量小、无第三方依赖、Windows下用VC或MinGW都能编译。这份报告的价值在于理论书里讲得再清楚的算法都不如一份能跑、能改、能踩坑的代码让你记得牢。2. 词法分析核心拆解PL/0单词识别与二元组输出的完整链路2.1 编码表设计与字符分类用一张二维数组承载全部单词类别词法分析器的关键设计决策是类别编码表。实验代码用char ktt[48][20]定义了一张全局编码表下标即类别编号020是PL/0关键字21是标识符22是无符号数2347是界符与运算符。这种把关键字、标识符、运算符统一编号的做法和很多编译原理教材附录里的PL/0词法表一一对应后续匹配只需要查表。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 关键字 标识符, 无符号数, // 21, 22 固定类别 ,, ;, :, ., (, ), [, ], .., , --, , -, *, /, , , , , , , :, {, }, #}; // 23~47字符串太长会被截断但PL/0关键字最长的是procedure9个字符放进[20]的列宽里绰绰有余。这个表的设计有个细节值得注意运算符里 - * /的编号是3437界符的编号是2347两者在表中有重叠区间——、、既出现在界符分支里也属于运算符语义实验代码把它们归入界符isJ处理只把 - * /当运算符isP。分类函数因此写得很直接bool isLetter(char ch) { return (ch A ch Z) || (ch a ch z); } bool isDigit(char ch) { return ch 0 ch 9; } 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 #; }isP和isJ的判断范围直接决定了主循环的分支走向如果一个字符既不是字母、数字也不是 -*/还不在界符集合里就会被空白分支或换行分支吞掉逻辑上不留非法字符的出口。实际测试里输入这种符号既不匹配任何分支也不会被isBlank拦截循环会在chsrc[pos]里直接跳过去——识别不出错误也不报错这是实验代码和检查错误能力要求之间的第一个落差。2.2 主循环从 pl0.txt 到单词串的逐字符识别整个词法分析器没有用状态机而是用if-else链加while循环手工模拟了最长匹配过程。主程序先把整个源文件读入字符串src末尾追加一个#作为结束符然后从pos0开始逐个字符扫描。fp fopen(pl0.txt, r); ch0 fgetc(fp); while (ch0 ! EOF) { src ch0; ch0 fgetc(fp); } src #; ch src[pos]; while (ch ! #) { char str[20]; if (ch ! \n) { if (isDigit(ch)) { // 拼合无符号数数字和小数点都吸收 int i 0; while (isDigit(ch) || ch .) { str[i] ch; ch src[pos]; } str[i] \0; ste |22; // 类别固定为22 cout str; continue; } else if (isLetter(ch)) { // 拼合标识符字母开头后字母数字都可跟 int i 0, j; while (isLetter(ch) || isDigit(ch)) { str[i] ch; ch src[pos]; } str[i] \0; for (j 0; j 21; j) { if (strcmp(str, ktt[j]) 0) { stringstream ss; ste |; ss ste; ss j; ss ste; break; } } if (j 21) ste |21; // 非关键字则归为标识符 cout str; continue; } else if (isP(ch)) { int i 0, j; str[i] ch; str[i] \0; for (j 34; j 38; j) { if (strcmp(str, ktt[j]) 0) { stringstream ss; ste |; ss ste; ss j; ss ste; break; } } cout str; ch src[pos]; continue; } else if (isJ(ch)) { int i 0, j; while (isJ(ch)) { // 注意连续界符会被拼成一个串 str[i] ch; ch src[pos]; } str[i] \0; for (j 23; j 47; j) { if (strcmp(str, ktt[j]) 0) { stringstream ss; ste |; ss ste; ss j; ss ste; break; } } cout str; continue; } else if (isBlank(ch)) { cout ch; ch src[pos]; continue; } } else { cout ste endl; ste ; } ch src[pos]; }运行逻辑链描述如下扫描到数字时while (isDigit(ch) || ch .)会把10.5、3.14这类带小数点的串整体吸收进同一个单词类别写死为22这步没做数字合法性校验2.和2.3.4也会被当成一个无符号数吞掉。扫描到字母时按字母开头、后续字母或数字的规则拼合标识符拼完后先跟020号关键字比对命中就记录关键字编号不命中就记为21号标识符。这里是典型的先识别单词、后查表定类别的教学实现比边读边判状态的做法更直观。运算符分支只处理单字符的 - * /读取一个字符匹配3437号。界符分支的实现是整段代码里问题最大的地方while (isJ(ch))会把连续出现的界符合并成一个串比如输入;(时str变成;(去查2347号表必然查不到这个单词就直接被丢弃连类别编号都不输出——我在2.4节会详细说这个坑。2.3 运行方法与结果解读类别流字符串怎么读把上面的源码存成lexer.cpp在程序同目录放一个pl0.txt写入报告里给出的测试源程序然后编译运行g lexer.cpp -o lexer.exe ./lexer.exe运行后控制台会先打印整个源程序文本和一张0~47 编号对照表接着在每一个换行处输出一行以|分隔的类别串。以测试文件里的CONST A10;为例期望的类别串是|0CONST|21A|38|2210|24;但实际输出会因为界符分支的合并问题出现丢类别的情况。类别串的意义是每个词法单元在ktt表中的下标后续语法分析器可以直接拿这串编号做终结符匹配这正是PL/0编译器把词法分析和语法分析解耦的标准做法。想要输出更直观的(单词, 类别)二元组最简单的方式是把ste累积逻辑改成printf((%s,%d)\n, tok, type)一次打印一个。2.4 关键缺陷与读码笔记界符合并、2A检测失效与文件判空逐行读这个主循环会读出几个报告的实验要求对不上的地方。最明显的是错误检测能力报告要求发现2A这类不能作为单词的字符串但实际代码把2识别为无符号数22接着A被识别为标识符21根本不报错。另一个是界符分支的合并问题我在前面讲过连续界符;(会被拼成查不到表的字符串而静默丢弃。还有一个隐患是fpfopen(pl0.txt,r)后没判空文件不存在时会直接内存访问出错。这三个点放在一起恰好构成了一个完整的实验代码到工程代码的改进清单先补文件判空再把界符改成单字符匹配最后加真正的词法错误处理。看懂这三处代码问题比看懂那些正确的教科书示例更有收获因为真实项目的维护工作大部分就是在跟这类边界条件较劲。3. 递归子程序分析器实战文法G[E]的递归下降实现3.1 文法结构与FIRST集推导四个非终结符为什么能直接翻译成函数实验4要求对如下文法实现递归子程序分析G[E] E → e B a A A → a | b A c B B → d E d | a C C → e | d C这个文法没有左递归也没有公共左因子四个非终结符的产生式右部都以不同终结符开头所以可以无回溯地做递归下降预测分析。推导一下FIRST集就能验证FIRST(E) {e} FIRST(A) {a, b} FIRST(B) {a, d} FIRST(C) {d, e}每个非终结符的候选式首符集互不相交满足LL(1)文法的基本条件。这意味着写递归子程序时不需要回溯每个函数只需要看当前输入字符是哪个首符就能唯一确定走哪条产生式分支。这是递归下降法里最令人舒适的场景——代码结构与文法规则几乎一一对应translate一遍就行。报告里的实现正是这样全局字符数组a[10]存输入串全局变量s当下标指针四个函数E、A、B、C相互调用构成一棵隐式的语法分析树。3.2 子程序调用链走读从入口E到递归出口的逐字符消费void E() { if (a[s] e) { s; B(); if (a[s] a) { s; A(); } } } void A() { if (a[s] b) { s; A(); if (a[s] c) { s; B(); } } else if (a[s] a) { s; } } void B() { if (a[s] d) { s; E(); if (a[s] d) { s; } } else if (a[s] a) { s; C(); } } void C() { if (a[s] d) { s; C(); // 右递归dC } else if (a[s] e) { s; // 终结符 e } }执行过程从E()开始E期望看到e成功消费后调用B()B若看到d则递归调用E()形成E - B - E的中嵌套结构。用测试串eaeaa手动推演一遍E消费e→ B看到a走第二条产生式调C → C看到e消费 → B返回 → E看到a消费 → A看到a消费 → 指针越到串尾a[s] #判定句子结构正确。整个过程不需要维护栈调用栈本身就是分析栈这是递归下降法比表驱动预测分析更直观的地方。main函数里有个大写While(1)C编译必报错是报告里的一个笔误改成小写while(1)即可。另一个值得注意的点是scanf(%s,a)读入的字符串里如果含#以外的非法字符四个函数都不处理分析会在某个分支里静默失败——实际交作业时可以加一个default分支打印错误位置。整个分析器没有输出推导过程或语法树只判定句子是否合法这是课程实验的验收标准使然二次开发时想可视化推导过程只要在每个函数入口打印进入 E()当前位置字符 %c即可。3.3 词法分析到语法分析怎么衔接类别号序列才是真正的接口做完实验2再写实验4很容易问词法分析器输出的|0|21|38|22|24这种字符串能直接喂给递归子程序分析器吗答案是现在不能因为两个实验是分开提交的语法分析器直接操作原始字符数组a[10]相当于把词法分析结果丢在一边重新对源程序做了一次裸字符级扫描。但真正编译器的做法应该是词法分析器输出(单词, 类别编号)的token流语法分析器只消费token流里的类别编号并读取单词文本做必要检查比如标识符值。一个最小改造方案是把词法分析里拼好的str和类别编号存入结构体数组struct Token { int type; char text[20]; }然后把实验4里所有a[s]的比较改成对tokens[pos].type的比较例如原来检查a[s]e现在检查tokens[s].type 00是e对应的编码。这样一个链路下来词法、语法两级分析就串起来了。实验报告里没写这个衔接步骤但作为课程设计答辩时的加分项值得动手试一下。4. 词法分析避坑手册常见问题与排查记录4.1 运行闪退pl0.txt 不存在时的文件判空问题现象编译通过运行时程序直接崩溃退出控制台没有输出。原因fpfopen(pl0.txt,r)这行没有检查返回值。文件路径写错或文件不存在时fp为NULL紧接着fgetc(fp)在空指针上取数据在Windows的VC运行时里通常表现为访问冲突。解决在打开文件后加判空分支这是所有涉及文件读取实验的第一道防线fp fopen(pl0.txt, r); if (fp NULL) { printf(无法打开 pl0.txt请确认文件位于程序同目录\n); return 1; }从那以后我每次写课程实验代码凡是涉及fopen、scanf、new这类会产生外部依赖的操作第一件事都是想如果这一步失败程序会怎样这也成了我现在写生产代码时检查输入边界的一种习惯。4.2 输出串里缺了界符类别连续界符被 while(isJ(ch)) 合并现象词法分析输出中某些;、(、)后的类别编号缺失类别串里出现连续的||。原因界符分支用的是while (isJ(ch))吸收所有连续界符。例如源程序里出现;(两个字符都会被拼进同一个str得到;(去查2347号编码表。表里根本没有这个组合匹配失败后既不输出类别也不报错直接把单词扔了。解决把while (isJ(ch))改成只取单字符即去掉循环只保留str[i]ch; chsrc[pos];。如果要支持:43号、42号、这类双字符运算符应该用两字符前瞻匹配而不是用循环吸收。最实用的改法是先取一字符再预读下一字符能拼成已定义的双字符运算符就取两位否则按单字符出号。4.3 编译报错While 大写导致无法通过编译现象实验4源码贴进编译器后报错While未定义。原因源码第41行写的是大写While(1)C的关键字是while大小写敏感。解决全局替换成小写while(1)。这个问题虽然低级但从侧面反映出实验报告提交前的编译验证不够也提醒所有拿课程代码学习的同学先找编译错误再分析运行逻辑顺序不能反。类似的还有实验2里if(j%0021)的写法C里数字字面量前导0是合法的八进制002会被解析成八进制2这里能编译过但读代码的人容易懵改成if (j % 2 1)更清楚。4.4 发现不了 2A 类错误错误检测名不副实现象测试源文件里写2B、2E程序照常输出类别串不报任何非法单词。原因主循环的数字分支把2识别为无符号数22字母分支把B识别为标识符21。两个合法token相邻词法分析器认为一切正常。实验要求里写的发现2A这类不能作为单词的字符串代码并没有实现。解决在数字分支拼完数字串后加一个后续字符检查——如果紧跟着isLetter(ch)说明是2A这类数字与字母直接相邻的非法词素立即报错并跳过if (isDigit(ch) isLetter(src[pos])) { printf(词法错误数字后紧跟字母\n); // 跳过整个非法串 while (isDigit(ch) || isLetter(ch)) ch src[pos]; continue; }更完备的做法是给每个token记录行号错误信息输出到文件这是从能交作业跨到能用的分水岭。4.5 分析结果错误但不报错语法分析器的静默失败问题现象实验4输入eda输出分析失败但程序不提示失败发生在哪个字符。原因E()第一个if (a[s]e)为真后B()内部可能走完分支第a个字符整个调用链结束后a[s]不是#就判定失败。整个过程没有任何中间诊断输出失败位置全靠人肉断点。解决调试期在每个else if不匹配时加一条printf(位置 %d 期望 %c 实际 %c\n, s, expected, a[s])很快就能定位是哪一步消费错误。这也是递归下降法的既有痛点——错误恢复能力弱实战中要做同步符号集FOLLOW集里的关键字如begin、end来做错误恢复而不是一报错就停止。5. 二次开发改造把课程实验代码升级成可复用的PL/0前端两个实验的代码加起来不到300行功能停留在能跑。真要拿去做下一个编译原理课程设计的起点我建议按三个步骤改造第一步把词法分析器重构成Lexer类输出结构体token流而不是字符串累积。定义struct Token { int type; char text[32]; int line; };把ste字符串累积逻辑全部删掉换成一个vectorToken。主循环里每次识别完一个单词就tokens.push_back({type, str, line})这样语法分析器就能直接消费token数组。类的好处是可以在析构函数里关文件、可以在构造函数里做开文件判空逻辑内聚。第二步把语法分析器的字符指针改成token指针。实验4里a[s]是字符改造后tokens[s]是token比较时不再用e而是用tokens[s].type 0。这一步工作量不大但它让词法层和语法层终于串成了一条真正的编译前端流水线。建议写一个match(TokenType expected)工具函数做token消费和错误定位统一管理读到期望的token才前进否则报错的流程。第三步增加完整的错误处理。词法层补回2A检测和非法字符输出语法层加错误恢复——失败时往后找 FOLLOW 集中的同步token对E来说同步token是end、#跳过一段输入继续分析这样一次运行能报出多处错误。验证方法我一般会固定两组用例一组合法串eaeaa、ebacbdeaa确认通过一组非法串eaa、2A、空串确认报错且不崩溃每次做完修改先把这两组回归一遍避免改一处坏二处。这份报告里最有价值的地方恰恰是它那份不够完美没有判空、界符合并、错误检测形同虚设每一个缺陷都是逼着你亲手修一遍的好老师。从那以后我每拿到一份课程实验参考代码都会先按输入边界→编译通过→错误路径的顺序跑一遍踩坑清单而不是直接看主流程。希望帮到你。本文还有配套的精品资源点击获取