简介面向东北大学秦皇岛分校计算机与通信工程学院编译原理课程的学习者这份实验报告对应实验2「词法分析程序的设计与实现」围绕PL/0语言展开帮助理解词法分析原理并完成课程实验。压缩包内仅1个doc文档大小约122KB内容以文字与代码为主包含实验目的、实验内容、Windows PC下C实现的环境说明、完整源代码及实验流程与总结。文档中的源代码给出isLetter、isDigit、isP、isJ、isBlank等字符分类函数以及基于关键词表ktt匹配、输出单词类别二元组、识别2A等非法串的主程序结构可直接对照理解词法分析器的构建思路。目前已有98人学习适合需要参考实验报告写法、梳理PL/0词法分析步骤或补齐错误检测思路的学生使用。1. 交实验报告那天最容易被问住的不是代码能不能跑交编译原理实验报告那天最容易被问住的不是代码能不能跑通而是「你怎么证明 2A 是错的」。多数人把两份实验——一个 PL/0 词法分析器、一个递归子程序语法分析器——当成两道互不相干的编程题代码贴进报告就算交差可一旦随机敲一个CONST A10; 2B进去程序要么默默把 2B 拆成2和B两个合法单词要么干脆卡在 while 里出不来。这套实验真正要交付的东西是把「字符怎么分类、单词怎么成对、句子怎么判定、错误怎么定位」四件事串成一条可复现的链路让任何一个输入串都得到二选一的结论和一句能指到位置的说明。下面按这条路把两个实验合成一份可以直接照搬的方案来讲。2. 需求拆解与总体设计两个实验、三层结构、一张 48 项类别表2.1 把实验要求翻译成六个可验收的功能点实验指导书上的文字往往是「设计并调试一个词法分析程序加深对原理的理解」这种描述没法直接验收。我一般会把它翻译成六个能当场演示的动作写进报告的第一节答辩时照着逐条过第一能从文件读入一段 PL/0 源程序不是靠手敲字符串第二能把源程序切成一串单词每个单词输出成单词类别码二元组第三关键字、标识符、无符号数、运算符、界符这五类必须能区分开不能混成一种第四能识别出2A、2B这类以数字开头却混了字母的非法串并且报出位置第五语法分析部分要针对给定文法 G[E] 判断任意符号串是不是该文法的句子第六判定结果要有明确的「正确 / 失败」输出失败时能说出停在第几个字符。这六条里前四条属于实验二后两条属于实验四。把它们分开写报告的骨架自然就出来了——不是「实验二」「实验四」两坨代码堆在一起而是「输入层、切分层、判定层」三段递进。很多人报告写不下去根本原因是没做这一步翻译导致后面每一节都在重复「本程序实现了词法分析功能」这种空转。提示功能点一定要写成「能演示的动作」不要写成「理解了 XX 原理」。前者答辩时能当场跑后者只能靠嘴说。2.2 三层结构的划分与各自的职责边界整体拆成三层每层只干一件事层与层之间只通过一个明确的接口传递数据层次职责输入输出对应代码字符底座层判断单个字符属于哪一类一个 charbool 或类别标记isLetter / isDigit / isSingleOp / isDelim / isBlank词法扫描层按类别把字符拼成单词并编号源程序字符串单词类别码序列 错误表scanWord / 主扫描循环语法判定层按文法规则递归匹配符号串符号串正确 / 失败 出错位置E / A / B / C 四个递归函数这样分层的好处很实际字符底座层是纯函数输入输出都只有一两个参数写错了单测一跑就知道词法扫描层不关心文法长什么样语法判定层也不关心字符怎么分类两边可以并行调试。原始代码把三层揉在一个main里出问题时你根本分不清是字符判断写错了还是循环推进写错了。我一般会强调一个边界词法层不负责判断语法对不对。BEGIN BEGIN END在词法上完全合法两个关键字加一个关键字类别码分别是 1、1、6能不能构成句子是语法层的事。反过来语法层拿到的应该是已经切好的符号序列而不是自己去抠字符。这条边界一旦糊掉后面所有的错误定位都会失效。2.3 类别表的设计为什么是 48 项而不是随便编号词法分析的核心数据结构是一张类别表本质是把「单词长什么样」和「它是第几类」做成一张查找表。按实验给的表48 项分成三段// 类别表下标即类别码前 21 项为关键字21/22 为标识符与无符号数23 起为界符与运算符 const 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 界符与运算符 };这张表有三个设计点值得写进报告。其一是编号即下标类别码不用另外定义常量直接用数组下标查找和输出共用一份数据改一个关键字只改一行。其二是分段的连续性0 到 20 是关键字判断标识符是不是关键字只需要在这个闭区间里做一次线性比较34 到 37 是单字符运算符判断运算符也只需要扫这 4 个位置。区间边界本身就是语义。其三是双字符运算符放在尾部、、、:这四个必须优先于单字符匹配否则会把的第一个字符吃掉。这里有个容易被忽略的细节如果把类别码当作魔法数字散落在代码里比如ste |22那么一旦表结构调整所有硬编码全废。我在写的时候会把 21、22 提成具名常量ID_CODE 21、NUM_CODE 22报告里也能体现出对可维护性的考虑——这一点在评分表里往往占分。3. 词法分析器落地从字符分类到单词类别二元组3.1 五个分类函数和它们的边界条件字符分类函数看着最简单实际上是最容易埋雷的地方。原始写法是五个独立函数各自用 if 判断区间// 字符底座层只回答这个字符属于哪一类不涉及任何扫描逻辑 bool isLetter(char ch) { return (ch A ch Z) || (ch a ch z); } bool isDigit(char ch) { return ch 0 ch 9; } bool isBlank(char ch) { return ch || ch \t; } // 运算符只保留单字符的四个双字符交给扫描层二次判断避免把 吞成一串 bool isSingleOp(char ch) { return ch || ch - || ch * || ch /; } // 界符包含单字符与 ## 在这里同时充当输入结束标记 bool isDelim(char ch) { return ch , || ch ; || ch : || ch . || ch ( || ch ) || ch [ || ch ] || ch { || ch } || ch #; }对照原始代码isP和isJ的划分其实是有问题的。isP把 - * /单独拎出来是对的但isJ把、、、:全都算成界符之后扫描层又用while (isJ(ch))一路吞下去结果是::这种串会被整体拼成一个 lexeme 再去表里查查不到就没有任何输出。表面上看程序没崩实际上单词被静默丢掉了。我的做法是把「单字符确定类」和「可能构成双字符」分开单字符界符直接查表出码、、:这三个进门之后再看一眼下一个字符能不能组成、、:、。还有一个边界值得单独说字母和数字的判断只覆盖 ASCII如果源程序里混进中文字符或者全角标点所有isXxx都会返回 false。这不是 bug但主循环必须有兜底分支否则就会出现下一章要讲的死循环。报告里写一句「分类函数覆盖的字符集为可打印 ASCII超出范围的字符由主循环统一按非法字符处理」比闷头不管要专业得多。3.2 关键字匹配与二元组的拼装方式关键字识别用的是最朴素的线性比较扫完一个标识符形状的单词后拿它和类别表前 21 项逐个strcmp命中就取下标当类别码全不中就是 21标识符。这种写法在 21 个关键字的规模下完全够用没必要上哈希表但实现上有两个坑要绕开。第一个坑是字符串缓冲区。原始代码里char str[20]是在 while 循环体开头声明的看起来每轮都重新分配但str[i] \0之前如果 i 没被赋值或者上一轮残留的内容比这一轮长strcmp就会拿脏数据去比。稳妥的写法是每轮开头显式清空或者干脆改用std::string// 从 pos 开始扫一个标识符命中关键字返回其类别码否则返回 ID_CODE int scanIdent(const std::string src, int pos, std::string lexeme) { int start pos; while (pos (int)src.size() (isLetter(src[pos]) || isDigit(src[pos]))) pos; lexeme src.substr(start, pos - start); // 直接截取不手工维护缓冲区 for (int k 0; k 21; k) { // 只在关键字区间内比较 if (lexeme ktt[k]) return k; } return ID_CODE; // 21普通标识符 }第二个坑是二元组的拼装。原始代码用stringstream ss; ss ste; ss ste;绕了一圈才把数字拼上去这段逻辑等价于ste std::to_string(code)但流对象的状态会互相污染读多写少的时候特别容易出现输出粘连或者丢字符。改成字符串直接拼接一行顶十行输出格式还稳定// 每识别出一个单词就往当前行的二元组串上追加一段 |类别码 out ( lexeme , std::to_string(code) ) ;报告里可以给出一段实际输出的样子比如CONST A10;跑出来是(CONST,2) (A,21) (,38) (10,22) (;,24)。这里要注意的类别码取决于你把它归在 38 还是别的段位只要和类别表一致就行别在正文和表格里写两个不同的数——这是评审最容易抓的自相矛盾。3.3 主扫描循环的状态推进规则词法分析器的骨架就是一个 while 循环加一个位置指针所有 bug 都出在「指针什么时候往前走」这一件事上。我一般定三条规则写进注释第一每个分支退出前pos 必须停在新单词的第一个字符上而不是停在已消费字符的最后一个。第二任何分支都不允许「既不消费字符也不推进分支」这是死循环的唯一来源。第三换行符单独处理它不产生单词只负责把当前累积的二元组串输出成一行并清空。// 主扫描循环按字符类别分派每个分支负责把 pos 推进到下一个未处理字符 while (pos (int)src.size()) { char ch src[pos]; if (ch \n) { // 换行输出本行结果并复位 std::cout out std::endl; out.clear(); pos; } else if (isBlank(ch)) { // 空白跳过不产生单词 pos; } else if (isDigit(ch)) { // 数字可能是无符号数也可能是 2A 这类混写 pos scanNumber(src, pos, lexeme, errPos); } else if (isLetter(ch)) { // 字母标识符或关键字 out ( lexeme , std::to_string(scanIdent(src, pos, lexeme)) ) ; } else if (isSingleOp(ch) || isDelim(ch)) { pos scanOperator(src, pos, lexeme); } else { // 兜底表外字符报错并强制推进防止死循环 errList.push_back({pos, std::string(非法字符 ) ch}); pos; } }那个else兜底分支是整个循环的安全阀。原始代码里if (ch ! \n)后面跟了一串else if但没有最终的else一旦遇到$、、中文这类表外字符所有分支都不命中ch不推进while 就永远转下去了。这个 bug 在测试用例里不一定暴露因为给的pl0.txt里恰好没有非法字符但答辩时随手敲一个特殊符号就会当场卡死。留着这个兜底分支等于给程序买了份后悔药。3.4 错误检测2A 到底应该在哪一步被拦住实验要求里明确写了「有一定检查错误的能力例如发现 2A 这类不能作为单词的字符串」。但很多人交上来的程序跑2B输出的是(2,22) (B,21)——两个合法单词一个错误都没有。原因很直白数字分支的循环条件是isDigit(ch) || ch .读到B就停了停下来之后直接continue没有任何人回头看这个B是不是「紧贴着数字的字母」。正确的做法是在数字扫描结束时做一次后验检查// 扫描无符号数若数字后面紧跟字母判定为非法单词并整体跳过 int scanNumber(const std::string src, int pos, std::string lexeme, int errPos) { int start pos; bool hasDot false; while (pos (int)src.size() (isDigit(src[pos]) || src[pos] .)) { if (src[pos] .) { if (hasDot) break; // 第二个小数点不属于本单词留给界符处理 hasDot true; } pos; } lexeme src.substr(start, pos - start); if (pos (int)src.size() isLetter(src[pos])) { // 关键数字后直接跟字母 while (pos (int)src.size() (isLetter(src[pos]) || isDigit(src[pos]))) pos; errPos start; // 记录起始位置方便定位 lexeme src.substr(start, pos - start); // 整个非法串一起报出来 return -1; // 约定 -1 表示错误单词 } return NUM_CODE; }这里有个抉择点2A是报「非法单词 2A」还是报「2 后面缺少运算符」从词法分析的职责看前者更合适——词法层只知道「这一串字符凑不出一个合法单词」不知道缺什么运算符那是语法层的判断。报告里把这条写清楚反而能体现你理解了两层分析的分工。另外1..2这种写法也要处理第一个点算小数点第二个点如果继续吞就会变成1..2这种既不是数也不是界符的怪物。上面的hasDot标志就是为了这个——遇到第二个点就退出循环让主循环把它当界符..处理。这种边界情况在报告里列一条比写十句「程序具有良好的健壮性」有用。4. 递归子程序分析器为 G[E] 写四个互调函数4.1 先验证 LL(1)为什么这份文法不需要回溯实验给的是文法 G[E]E → eBaA A → a | bAcB B → dEd | aC C → e | dC拿到文法先别急着写代码第一步是算每个非终结符各候选式的首符集FIRST 集看它们两两有没有交集非终结符候选式FIRST 集是否冲突EeBaA{e}单候选无冲突Aa / bAcB{a} / {b}不相交BdEd / aC{d} / {a}不相交Ce / dC{e} / {d}不相交四个非终结符的候选首符集全部两两不相交而且没有任何候选式能推出空串ε所以这份文法是 LL(1) 的。这个结论非常关键它直接决定了实现方式不需要回溯读错一个字符就说明这条产生式不成立直接返回失败即可。如果首符集有交集你就得保存当前位置、试一条路、失败再退回来试另一条代码复杂度翻三倍还得处理左递归。顺便验证一下左递归A → bAcB里 A 出现在 b 之后C → dC里 C 出现在 d 之后都不在产生式最左端所以没有直接左递归递归下降不会无限套娃。这两条检查写进报告的方法论一节比单纯贴代码更能说明你懂为什么这么写。4.2 E/A/B/C 四个子程序的骨架与调用关系递归下降的写法是「一个非终结符一个函数」函数成功返回 true 并推进位置指针失败返回 false 且不推进或者推进到出错点。四个函数互相调用调用关系完全照抄产生式右部的顺序// 匹配一个终结符成功则消费并推进 pos失败不推进 bool match(const std::string s, int pos, char c) { if (pos (int)s.size() s[pos] c) { pos; return true; } return false; } // C → e | dC bool parseC(const std::string s, int pos) { if (match(s, pos, e)) return true; // 候选一 if (match(s, pos, d)) return parseC(s, pos); // 候选二吃掉 d 后递归 return false; } // B → dEd | aC bool parseB(const std::string s, int pos) { if (match(s, pos, d)) { if (!parseE(s, pos)) return false; // 中间夹一个 E return match(s, pos, d); // 尾部还要一个 d } if (match(s, pos, a)) return parseC(s, pos); return false; } // A → a | bAcB bool parseA(const std::string s, int pos) { if (match(s, pos, a)) return true; if (match(s, pos, b)) { if (!parseA(s, pos)) return false; // 中间递归 A if (!match(s, pos, c)) return false; return parseB(s, pos); // 尾部接 B } return false; } // E → eBaA bool parseE(const std::string s, int pos) { if (!match(s, pos, e)) return false; if (!parseB(s, pos)) return false; if (!match(s, pos, a)) return false; return parseA(s, pos); }代码短得有点反直觉但每一行都能对应到产生式的一个符号。parseB里先match(d)再parseE再match(d)就是把dEd三个符号按顺序消费掉。因为首符集不相交match(d)失败时可以直接断定「这条候选式不适用」转去试aC不需要回到函数开头重置指针——这是 4.1 节那个验证带来的直接收益。调用入口只需要判断两件事parseE返回 true并且位置指针恰好走到串尾。少判断任何一个都会出问题——只判返回值的话eaeaaXXX这种「前缀合法、后面拖尾巴」的串会被误判为正确。4.3 位置指针、结束符与缓冲区大小原始实现里有几个必须改掉的地方每一个都会导致程序跑不出正确结果第一个是While(1)首字母大写。C 关键字区分大小写这一行直接编译不过属于低级但高频的失误。第二个是结束符判断if (a[s] #)而输入用的是scanf(%s, a)用户不主动敲#的话这个条件永远不成立程序永远输出「分析失败」。正确做法是读入之后判断pos s.size()或者在读入时把结束符补上再统一处理。第三个是char a[10]的缓冲区大小随便一个嵌套两层的串就超过 10 个字符栈溢出会让程序直接崩报告里也解释不清是逻辑错还是内存错。// 入口读入整行去掉空白后交给 parseE成功条件是返回 true 且指针走到末尾 int main() { std::string line; while (std::getline(std::cin, line)) { std::string s; for (char c : line) if (!isspace((unsigned char)c)) s c; // 忽略空白 if (s.empty()) continue; int pos 0; bool ok parseE(s, pos) pos (int)s.size(); if (ok) std::cout 句子结构正确 std::endl; else std::cout 分析失败停在第 pos 1 个字符 std::endl; } return 0; }用std::string替代定长数组长度问题一次性解决用getline替代scanf(%s)空白和换行不会被当成串的一部分把「成功」定义成parseE pos size()尾巴多余的字符也能被抓出来。这三处改动都不大但它们决定了程序是「能跑」还是「能验收」。4.4 从二元结论到可定位的错误信息只输出「正确 / 失败」在答辩时是撑不住的导师一定会问「错在哪」。递归下降的好处是位置指针天然就是错误位置稍微改一下函数签名就能把出错点带出来。最简单的办法是加一个全局的lastError变量在每个return false之前记下当前 pos 和期望的字符// 带定位信息的匹配失败时记录期望字符与实际字符供调用方输出 bool matchEx(const std::string s, int pos, char expect, std::string err) { if (pos (int)s.size() s[pos] expect) { pos; return true; } err 位置 std::to_string(pos) 期望 expect ; if (pos (int)s.size()) err 实际 std::string(1, s[pos]) ; else err 但输入已结束; return false; }这样跑eadaa会输出「位置 3 期望 e 或 d实际 a」比一句「分析失败」有用得多。报告里配一组测试用例表把输入串、期望结果、实际输出三列并排放评审一眼就能看出你的程序覆盖了正确串、边界串和错误串。我一般准备这么几组eaeaa正确E 推导出 eaeaa、eaeaaX尾部多余字符、eB 缺失、adaa开头不是 e、空串边界。5. 常见问题与排查这类实验最容易翻车的五处5.1 词法侧的三处高发问题现象一输入2A不报错反而输出(2,22) (A,21)两个合法单词。原因是数字分支扫到非数字字符就停停下来之后没有回头检查紧邻的字符是不是字母直接继续下一轮循环。解决方式是在数字扫描结束后加一次后验判断若下一个字符是字母就把整段「数字 字母」当成一个非法单词整体报出来并记录起始位置。这条不改实验要求里那句「发现 2A 这类不能作为单词的字符串」就是空话。现象二程序在某些输入下卡死不动任务管理器里 CPU 占满。原因是主循环只有if (ch ! \n)和一串else if遇到$、、英文引号这类表外字符时所有分支都不命中位置指针不推进while 条件永远为真。解决方式是补一个最终的else统一按非法字符处理并强制pos。这条兜底分支在正常测试用例里根本走不到所以特别容易漏建议在报告里专门写一段「非法字符的兜底处理」主动暴露你考虑过这个问题。现象三关键字偶尔识别不出来同一个BEGIN有时是 1 有时是 21。原因是char str[20]复用同一个栈上缓冲区某一轮扫出的单词比较短str[i] \0之后剩下的旧内容还在strcmp比较时可能读到残留字节。解决方式有两个每轮开头memset(str, 0, sizeof(str))或者干脆改用std::string做 substring彻底不碰定长缓冲区。后者的代码也更短src.substr(start, len)一行就完事。5.2 语法侧的两处高发问题现象四程序编译报错提示While不是标识符。这是把关键字首字母大写了While(1)应为while (1)。同类问题还有中文分号、全角括号从文档里复制代码时特别容易带进来。解决方式是在提交前用编译器的-Wall选项过一遍把警告也当错误看很多隐性问题未初始化变量、隐式类型转换在编译期就能揪出来。现象五不管输入什么串都输出「分析失败」。最常见的原因是结束符判断和输入方式不匹配——scanf(%s, a)读进来的串里根本没有#而代码里判断的却是a[s] #条件恒假。另一个原因是位置指针在主函数和子函数之间没有正确传递子函数里改的是局部副本回到主函数指针还是 0。解决方式是统一用std::string加引用传参成功条件改成「parseE返回 true 且pos size()」去掉所有对#的隐式依赖。6. 验收与答辩按六个检查点走一遍再交实验报告交上去之前我会拿下面这张表逐项过一遍每一项都要能当场演示不能只是「我觉得应该没问题」检查点怎么验合格标准常见扣分文件读入换一个源文件路径再跑能正常读入并回显内容路径写死换机器就跑不了五类单词覆盖构造含关键字、标识符、数、运算符、界符的串五类类别码各不相同运算符和界符混为一类二元组格式检查输出是否形如(单词,类别码)格式统一类别码与表一致正文数字和代码数字对不上非法单词检测输入2A、1..2、$三种都能报出位置只报错不报位置语法判定准备正确串、拖尾串、缺符号串各一条三条结论各不相同且合理只测正确串错误定位故意在中间插错字符输出停在第几个字符只说「失败」不说位置答辩环节有个很实用的技巧准备三组输入现场按顺序跑。第一组是标准正确串证明主流程通第二组是边界串比如空串、只有一个字符的串、恰好卡在缓冲区边界的长串证明你没把长度写死第三组是错误串2A和语法上缺符号的串各来一条证明你的错误检测不是摆设。三组跑完大概两分钟比讲十分钟原理有说服力。还有一个容易被忽略的点报告里的实验环境和代码要能对上。写着「Windows PC 机C 语言」代码里就不该出现只有某个特定编译器才认的头文件写着用文件输入就别在演示时改用手敲。这些细节不影响程序正确性但会影响评审对你「有没有真跑过」的判断。我自己吃过一次亏代码在自己机器上跑得好好的换到实验室机器上因为源文件用了相对路径直接读不到当场重编译改路径场面很难看。从那以后我每次交实验报告前都会把整个工程拷到一个干净目录里从零编译一遍、跑一遍三组输入确认路径、编码、编译器版本都不依赖本机环境才敢点提交。这套习惯后来做课程设计和毕设也没改过省下的返工时间远比那十分钟多。希望帮到你。本文还有配套的精品资源点击获取