简介围绕PL/0语言词法分析程序的设计与实现这份实验报告面向高校编译原理课程学习者尤其适合东北大学秦皇岛分校计算机相关专业学生对照课程要求完成实验、撰写报告。文档完整记录实验目的、实验内容、实验环境与提交要求并给出基于C的词法分析器源码通过isLetter、isDigit、isP、isJ、isBlank等函数完成字符分类读取pl0.txt源程序后逐字符扫描将标识符、无符号数与关键字表ktt比对输出由单词和类别组成的二元组序列同时具备识别“2A”这类非法单词的检错能力可作为理解词法分析流程、梳理代码结构的参考。资源包共1个doc文件约122KB体量轻便便于直接查阅与二次整理。已有102人学习适合需要可对照的实验范例、排错思路与报告框架的读者。1. 编译原理实验报告真正丢分的地方往往不是算法编译原理实验报告的翻车点很少出在算法本身上。PL/0 词法分析的代码能跑通递归子程序也能打印出「句子结构正确」可一旦被问到类别编码为什么这么排、2A凭什么算非法、文法里的ε产生式该怎么处理人就卡住了。这次要拆的方案覆盖两个经典实验实验 2 的 PL/0 词法分析器把源程序字符串切成单词类别二元组实验 4 的递归子程序分析器对文法 G[E] 判定任意符号串是否为合法句子。这套结构适合正在做编译原理课设、要交实验报告并参加答辩的读者也适合想把「代码能跑」升级成「讲得清、测得出、改得动」的人。2. 需求与技术选型两个实验的输入输出契约与 C 落地取舍动手写代码之前得先把两个实验的边界划清楚。很多人一上来就照着课本伪代码抄抄完发现不知道输出该长什么样也不知道怎么判断对错最后只能靠自己肉眼比对控制台实验报告里的「实验结果」截图也就成了摆设。真正省时间的做法是把输入输出契约先钉死在纸上再决定用什么语言、用什么分析方法。2.1 先把输入输出契约钉死字符串进、二元组出实验 2 的要求写得很直白输入是待分析的源程序字符串输出是由「单词、类别」组成的二元组序列并且要有一定的错误检查能力。这三句话看着简单落地时要补的细节不少。第一类别怎么表示。业界习惯用整数编码而不是字符串名字因为后续语法分析要拿这个整数做 switch 分派。这套编码通常按含义分段关键字占一段、标识符一个码、无符号数一个码、运算符和界符占最后一段。分段的好处是判断「这是不是一个运算符」只需要一次区间比较不用遍历整张表。第二二元组怎么输出。控制台上最直观的形式是(const, 2)、(A, 21)、(10, 22)、(;, 24)这种一行一个同时也把单词原文打出来方便对照源程序。如果实验报告里要贴结果建议再额外输出一列行号出错时好定位。第三错误怎么体现。宽松一点的做法是打一行Error at line 3: illegal token 2A严格一点的做法是记录错误数量并在末尾汇总。无论哪种都不能静默跳过——这是后面验收环节最能拉开差距的地方。一次完整的词法分析输入输出大致是这个形态源程序片段输出二元组说明CONST A10;(const,2) (A,21) (,38) (10,22) (;,24)关键字、标识符、赋值号、无符号数、分号2BError: illegal token 2B数字开头后接字母不属于任何合法单词WHILE X0 DO(while,19) (X,21) (,39) (0,22) (do,4)关系运算符单独成词注意最后一行和0之间即使没有空格也必须切成两个单词。词法分析器的切分依据是字符类别不是空格空格只是分隔符之一。这一点在报告里写清楚答辩时基本不会被追问。2.2 为什么选 C 而不是用现成的 lex字符级控制的必要性实验环境给的是 Windows C这个选择其实挺合适。词法分析的本质是「一个字符一个字符地啃」需要频繁做单字符判断、指针前移、缓冲区拼接C 的char处理和std::string拼接在这里刚好够用又不像脚本语言那样容易把字符和字符串混为一谈。更关键的是教学目的。用lex或flex写规则三十行就能生成一个词法分析器但你不会知道yytext内部是怎么做最长匹配的也不知道回溯点在哪里。实验报告要的是「设计、编制、调试一个具体的词法分析程序」重点在「具体」两个字。手写扫描器虽然啰嗦但每一行都能在报告里对应上一句设计说明。落地上有几个取舍值得在报告里交代一句。字符串拼接用std::string而不是char[]避免缓冲区溢出文件读取用ifstream逐字符get()而不是一次性read到定长数组避免大文件截断类别表用二维char数组或者std::vectorstd::string前者省事后者安全教学场景下前者更贴近课本风格。这几点写进「实验环境与工具」那一节比单纯罗列「Windows PC 机C 语言」有内容得多。字符判定函数是整个扫描器的地基通常拆成这么几个// 字符类别判定所有扫描逻辑都建立在这几个函数之上 bool isLetter(char ch) { return (ch A ch Z) || (ch a ch z); } bool isDigit(char ch) { return ch 0 ch 9; } // 算术运算符 - * /对应类别码 34~37 bool isOperator(char ch) { return ch || ch - || ch * || ch /; } // 界符单个符号和复合符号的首字符都在这里 bool isDelimiter(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 || ch \r; }这几个函数看着平淡但它们是后面所有分支的判据。参数是单个char返回值是布尔不做任何状态维护——状态全交给主循环里的位置指针。把「判定」和「推进」分开是这个扫描器能讲清楚的根本原因。如果让判定函数自己去改指针逻辑立刻纠缠成一团调试时就只能靠打印了。2.3 递归子程序法能不能覆盖这份文法LL(1) 判定与适用边界实验 4 给的文法是这样的G[E]: E → eBaA A → a | bAcB B → dEd | aC C → e | dC拿到文法第一件事不是写代码是判断它属于哪一类。逐个产生式看右部首符号E 只有e一个候选A 是a或b两个候选首符不同B 是d或a也不冲突C 是e或d同样不冲突。四个非终结符都没有左递归也没有公共左因子更没有ε产生式所以这是一个标准的 LL(1) 文法直接写递归下降就行不需要做消除左递归和提取左公因子这两步改写。这一步判断在报告里必须写出来而且要写出 FIRST 集和 FOLLOW 集非终结符FIRST 集FOLLOW 集候选产生式首符E{ e }{ #, d }eA{ a, b }{ # }a / bB{ d, a }{ a, # }d / aC{ e, d }{ d, # }e / dFOLLOW 集是这么推的E 是开始符号FOLLOW(E) 含#B → dEd 里 E 后面跟d所以 FOLLOW(E) 再加d。E → eBaA 里 B 后面跟aFOLLOW(A) 就是 FOLLOW(E) 也就是#。B 出现在 E → eBaA 的倒数第二个位置后面是 A而 A 不能推出空串所以 FOLLOW(B) FIRST(A) { a }再加上 A 后面可能没有东西的情况也就继承了 FOLLOW(E) 的#。C 出现在 B → aC 的末尾FOLLOW(C) FOLLOW(B) { a, # }但 C 的两个候选首符是e和d与 FOLLOW 集没有交集所以不存在「该选哪个产生式」的歧义。判断结论是 LL(1)意味着可以用一个字符的前瞻lookahead决定分支这也解释了为什么后面的递归子程序只需要看a[s]一个字符就能往下走。如果文法里带左递归比如A → Aa | b直接写成函数就会无限递归栈溢出那种情况下必须先改写成右递归形式。这份文法不用改是它友善的地方也是报告里可以点一句「本文法无需预处理」的地方。3. 词法分析器总体设计类别表、扫描主循环与错误捕获结构上一个能拿得出手的词法分析器由三块拼成一张类别编码表、一个不断前移的扫描主循环、一个出错时不会静默吞掉的错误捕获分支。三块各自的职责非常清楚混在一起写就会变成那种「能跑但没人敢改」的代码。3.1 48 项类别编码表的分段设计整张表 48 项按含义分四段编码区间内容数量设计意图0 ~ 20PL/0 全部关键字按字母序排列21顺序即编码查表时用下标直接当类别码21标识符1单独占一个码语法分析阶段用它区分变量名22无符号数1同上常量声明和表达式里都要用23 ~ 47界符、算术运算符、关系运算符、赋值号25按「单字符在前、复合在后」的次序排关键字按字母序排是为了查表时可以用二分也可以直接把下标当编码用省掉一次映射。这一点在报告里值得写一句编码顺序不是随便定的字母序让「关键字表的下标 类别码」这个巧合成立代码里就少了一次查表转换。23 到 47 这一段又细分成三小组23~33是纯界符包含,;:.()[]以及..--这几个复合符号34~37是四个算术运算符 - * /单独成组是因为它们有优先级语义语法分析时要单独判断38~47是关系运算符、赋值号和花括号、井号包括 : { } #。复合符号的存在是这张表最容易埋雷的地方。和都以开头扫描时必须先看下一个字符是就吞两个字符匹配否则只匹配。..和.同理。这种「最长匹配」原则是词法分析的基本规则报告里写一句「采用最长匹配策略」比不写要好。3.2 扫描主循环吃字符、拼单词、查表三步走主循环的骨架非常固定跳过空白 → 看当前字符属于哪类 → 按类吞掉一串字符拼成单词 → 拿单词去表里查类别 → 输出二元组 → 指针前移。四类分支数字、字母、算术运算符、界符各自独立互不干扰。// 词法分析主循环pos 是全局位置指针src 末尾已补 # void scan(const std::string src) { size_t pos 0; while (pos src.size() src[pos] ! #) { char ch src[pos]; // 1) 空白直接跳过不产生单词 if (isBlank(ch)) { pos; continue; } std::string token; // 2) 数字开头吞掉连续数字允许中间出现一个小数点 if (isDigit(ch)) { while (pos src.size() (isDigit(src[pos]) || src[pos] .)) token src[pos]; // 数字后面紧跟字母说明是 2A 这类非法串 if (pos src.size() isLetter(src[pos])) { while (pos src.size() isLetter(src[pos])) token src[pos]; reportError(token, pos); continue; } emit(token, 22); // 22 无符号数 continue; } // 3) 字母开头吞掉字母数字串再查关键字表 if (isLetter(ch)) { while (pos src.size() (isLetter(src[pos]) || isDigit(src[pos]))) token src[pos]; int code lookupKeyword(token); // 命中返回 0~20否则返回 -1 emit(token, code 0 ? code : 21); // 21 标识符 continue; } // 4) 其余交给符号识别内部再分算术运算符和界符 if (isOperator(ch) || isDelimiter(ch)) { int code scanSymbol(src, pos, token); if (code 0) emit(token, code); else reportError(token, pos); continue; } // 5) 谁都不认识报错并前进一格避免死循环 reportError(std::string(1, ch), pos); pos; } }这段代码有三个地方值得在报告里点名。emit(token, code)负责输出参数是单词原文和类别码内部做格式化可以同时往控制台和结果文件里写。把输出抽成函数是为了将来换格式比如改成 CSV 给报告当数据时只改一处。lookupKeyword只处理 0 到 20 那一段返回-1表示不是关键字。这样标识符的判定就变成了「查不到关键字的一律是标识符」逻辑上少一个分支。最后的兜底reportError加pos是防死循环的关键。如果遇到一个既不是字母数字、也不是运算符界符、还不是空白的字符比如某些全角符号或者乱码不前进指针就会原地打转程序直接挂住。这类死循环在实际调试里非常常见报错反而好定位。3.3 非法串检测2A、2B、2E 到底是哪一步没兜住实验要求原文写着「有一定检查错误的能力例如发现 2A 这类不能作为单词的字符串」。这句话的落脚点在「例如」两个字上——不是只查2A而是查所有「以数字开头、后面跟字母」的组合。测试用的源程序里恰好埋了三处2B、2E还有一处藏在2BPROCEDURE这种紧贴写法里。一个合格的扫描器应当在读到2之后继续往后看发现紧跟的是字母就把2B整串当成非法单词报出来而不是拆成(2, 22)和(B, 21)两个合法二元组。代码里的做法是数字分支吞完数字后多做一次「下一个字符是不是字母」的判断。如果是就把后面的字母也一起吞进来凑成一个完整的非法串再报错这样错误信息里能给出2BPROCEDURE这样的原文而不是孤零零一个2排查时价值大得多。// 错误上报记录行号和原文方便在报告里贴出错误列表 void reportError(const std::string token, size_t pos) { errorCount; std::cout Error: illegal token \ token \ at offset pos std::endl; }参数pos是出错位置在源串里的偏移量转成行号只需要在扫描过程中维护一个行计数器每读到一个\n就加一。这个计数器在报告里可以体现为「错误定位能力」比单纯打印「分析失败」有说服力。还有一类错误不该被忽略注释或字符串没有闭合。这份 PL/0 子集没有字符串字面量但花括号{ }常被用作注释定界如果只见到{没见到}也应该报一次错。这类「配对未闭合」的问题跟着扫描主循环一起写几行代码的事写进报告就是一个独立的错误处理小节。4. 递归子程序分析器实现把文法 G[E] 拆成四个函数词法分析输出的是二元组序列语法分析要判断的是「这个序列能不能由文法推导出来」。递归子程序法的思路极其直白一个非终结符对应一个函数函数内部按产生式右部的顺序遇到终结符就比对并前移遇到非终结符就调用对应的函数。整个分析过程就是一次深度优先的推导模拟。4.1 文法预处理消除左递归、提取左公因子后的形态前面已经判定 G[E] 是 LL(1)理论上不需要改写。但报告里最好还是把「如果不改写会怎样」写一句显示你判断过而不是抄的。假设文法里出现A → Aa | b这种形式函数A()的第一件事就是调用A()无限递归程序在第一个输入字符上就栈溢出。消除左递归的标准做法是引入新非终结符A改写成A → bA、A → aA | ε这样函数A()先比对b再调用A()指针始终在前进递归深度受输入长度约束。提取左公因子同理。如果两个产生式都以同一个符号开头比如B → aC | aD光看首字符a无法决定走哪条路就得改写成B → aB、B → C | D把判断推迟到a之后再做一个字符的前瞻。G[E] 的四个非终结符都没有这两个问题所以函数结构可以直接照产生式一一对应不需要引入额外的中间非终结符。这一点在报告的「文法分析」小节写清楚配上前面的 FIRST/FOLLOW 表逻辑就闭环了。4.2 E/A/B/C 四段子程序的骨架与调用顺序四个函数的结构完全一致进入函数根据当前字符决定走哪个分支分支内部按右部符号序列依次处理。终结符直接比对并前移非终结符则递归调用。// 全局输入缓冲 buf位置指针 sp错误标志 err void E() { if (buf[sp] e) { // E → eBaA sp; // 吃掉终结符 e B(); // 非终结符 B if (buf[sp] a) sp; // 吃掉终结符 a else { err true; return; } A(); // 非终结符 A } else { err true; // 首符不是 e直接判错 } } void A() { if (buf[sp] a) { // A → a sp; } else if (buf[sp] b) { // A → bAcB sp; A(); if (buf[sp] c) sp; else { err true; return; } B(); } else { err true; } } void B() { if (buf[sp] d) { // B → dEd sp; E(); if (buf[sp] d) sp; else { err true; return; } } else if (buf[sp] a) { // B → aC sp; C(); } else { err true; } } void C() { if (buf[sp] d) { // C → dC右递归 sp; C(); } else if (buf[sp] e) { // C → e sp; } else { err true; } }四个函数的参数表都是空的状态全放在全局变量里。这在教学代码里可以接受但要清楚代价不可重入、不好并发、调试时得盯着全局状态。如果想让代码更「工程」一点可以把buf、sp、err打包成一个struct Context以引用形式传进去改动量很小报告里也能多写一句「状态封装」。C()是唯一的右递归函数C → dC意味着输入里连续出现多少个d就会递归多少层。输入长度如果不设上限理论上存在栈溢出的风险实际测试串只有几个字符问题不大。这个细节提一句能体现你考虑过边界。每个分支末尾的else { err true; }是错误处理的入口。原版代码里很多分支是「匹配不上就什么都不做直接返回」导致上层无法区分「正常结束」和「中途失败」最后只能靠检查指针是否停在#上兜底。显式设置错误标志可以把出错位置一层层往上带甚至记录下「在哪个非终结符上失败的」报告里的错误信息就能写得具体。4.3 输入缓冲与结束符scanf 之后为什么必须补主程序负责三件事读输入、调用开始符号对应的函数、判断结果。读输入这里有个坑。用scanf(%s, buf)读进来的是一个以\0结尾的字符串但递归子程序判断结束的依据通常是「当前字符是不是#」。如果用户输入时不带#指针会一直走到\0之后读到缓冲区外的内容结果随机——有时候碰巧判对有时候判错换台机器又不一样非常玄学。稳妥的做法有两个一是要求输入必须以#结尾并在读入后校验二是读入后主动在末尾补一个#。第二种对用户更友好代码也就两行。int main() { char buf[256]; while (true) { std::cout 请输入符号串直接回车退出; if (scanf(%255s, buf) ! 1) break; size_t len strlen(buf); if (len 0) break; if (buf[len - 1] ! #) { // 末尾补结束符避免越界读 buf[len] #; buf[len 1] \0; } sp 0; err false; E(); // 从开始符号 E 推导 if (!err buf[sp] #) std::cout 句子结构正确 std::endl; else std::cout 分析失败出错位置 sp std::endl; } return 0; }缓冲区别用char a[10]这种定长小数组输入稍微长一点就溢出而且是那种「不报错但结果乱掉」的溢出调试起来能耗掉一晚上。256 字节对教学用例绰绰有余真要做大一点就换成std::string加getline。判定成功的条件是两个err为假且指针停在#上。少一个都不行。只查err会漏掉「输入前缀合法但后面还有多余字符」的情况比如eae#可能中途就把e a推完了剩下的e#没人管只查指针位置又会漏掉「中途出错但指针恰好在末尾」的情况。两个条件一起查才算真的验证完。5. 踩坑与排查五类最容易在答辩现场暴露的问题代码跑通和代码正确之间隔着一整个调试周期。下面这五类问题基本每一个手写词法/语法分析器的人都会撞上一两次提前知道能省不少时间。5.1 现象二元组少了一截控制台却没有任何报错原因界符扫描用了while (isDelimiter(ch))连续吞字符遇到);这种相邻的两个界符会拼成);整串去查表表里当然没有这一项查表循环走完没break于是既不输出也不报错直接continue。源程序里READ(X);这种写法到处都是问题会成片出现。解决界符扫描不能无脑循环。要么改成「先看两个字符能否组成复合符号、:、..能就吞两个否则只吞一个」要么在查表失败时立刻报错而不是静默跳过。前一种更符合最长匹配原则也是我一般会选的写法// 先尝试两字符复合符号失败再退回单字符 int scanSymbol(const std::string src, size_t pos, std::string token) { if (pos 1 src.size()) { std::string two src.substr(pos, 2); int code lookupSymbol(two); // 查 : .. -- 等 if (code 0) { token two; pos 2; return code; } } std::string one src.substr(pos, 1); int code lookupSymbol(one); if (code 0) { token one; pos 1; return code; } return -1; // 交给上层报错 }5.2 现象2A被切成两个合法单词错误检查形同虚设原因数字分支只吞数字遇到字母就停于是2变成无符号数A变成标识符两个二元组都合法错误一个都没报。测试源文件里埋的2B、2E全部漏网报告里写着「具备错误检查能力」实际跑出来一个错都没有。解决数字吞完之后补一次前瞻判断下一个字符是字母就把整串吞完并报错见 3.3 的代码。另外建议在测试用例里专门放三到五个非法串跑完统计错误条数和预期条数对上才算过。5.3 现象词法分析跑得好好的换一个源文件就卡死原因主循环里出现了「既不匹配任何分支、指针也不前进」的字符典型的是全角标点、制表符之外的不可见字符或者文件末尾的\0。由于循环条件只判断「当前字符不是#」指针不动就永远循环。解决主循环末尾无条件加一个兜底分支既不是空白也不是任何合法字符时打印字符的 ASCII 码并pos。把「未知字符」当成错误而不是异常程序就永远有出路。另外文件读入时最好用二进制模式避免换行符被做平台相关的转换。5.4 现象语法分析对任何输入都说「结构正确」原因子程序里匹配不上就直接return没有任何错误标记上层完全不知道下层失败了。主程序又只用「指针是否停在#」做判断如果失败发生在最后几个字符上指针恰好也停在#就误判为正确。解决每个函数的所有分支都必须有明确的失败出口统一设置一个全局err标志主程序同时检查「标志为假」和「指针停在#」两个条件。更进一步可以用一个errorPos记录第一次失败的偏移量报错时打印出来比自己猜快得多。5.5 现象输入稍长就崩溃或者结果里混进乱码原因char a[10]这种缓冲区长度超过 9 的输入直接越界写写坏了栈上的其他变量表现出来可能是结果错乱、可能是段错误、也可能什么都没发生——这类问题最容易被误判成「编译器有问题」。解决缓冲区改大到 256 以上scanf加宽度限定符%255s或者干脆用std::string配合getline读整行。判定函数里凡是访问buf[sp]之前先确认sp没有越过字符串长度越界读在 C 里是未定义行为不崩不代表没问题。6. 验收与答辩用一张测试用例表把「能跑」变成「可证明」到了交报告这一步很多人贴一张「句子结构正确」的截图就完事。截图证明不了任何东西因为读者不知道你输了什么、为什么这个东西应该被判对。真正省事的做法是提前做一张测试用例表正例、反例、边界例各来几条每条写清楚输入、预期输出、实际输出。答辩的时候导师随手挑一条问「为什么这个应该失败」你能立刻指着表说出理由。实验 2 的用例表可以这么组织序号输入片段预期结果考察点1CONST A10;5 个合法二元组关键字、标识符、赋值号、常量、分号22A1 条非法单词错误数字后接字母3X03 个二元组为一个整体复合符号最长匹配4{ 注释 }不产生二元组注释跳过51 条未知字符错误兜底分支实验 4 的用例设计原则不一样语法分析关心的是「能不能被文法推导出来」所以正例要覆盖每一条产生式反例要卡在每条产生式的首符判断上序号输入串预期推导依据1eea#正确E → eBaAB → aCC → e2ebacd#正确A → bAcB 分支被覆盖到3eded#正确B → dEd 与 C → dC 同时触发4ea#失败A 的首符要求 a 或 b此处缺失5ebac#失败A → bAcB 缺少结尾的 B6e#失败B 无法推出空串第 5 条和第 6 条是最容易被漏掉的。很多人只测「明显不合法」的输入比如xyz那当然失败真正检验代码质量的是「几乎合法但差一点」的输入这类用例能逼出错误标志有没有正确传递。答辩还有一个高频问题为什么这里的指针要前进那里不用答案只有一个——终结符必须前进非终结符由它内部的第一条产生式决定。把这句话练熟配合文法表指给对方看比背概念管用。从那以后我每次交这类实验报告都会强制走一遍「用例表 → 跑一遍 → 把实际输出贴回表里」的流程哪怕时间再紧也不省这一步。因为代码是自己写的看哪儿都觉得对只有拿一张事先定好的表去撞才能撞出那几个藏在边角里的错。这份方案里的类别表、扫描主循环、四个子程序和用例表都是可以直接照着改的东西把源程序换成你自己的测试集就能跑起来。希望帮到你。本文还有配套的精品资源点击获取