简介面向编译原理课程设计与实验场景的TINY语言词法分析器手工构造完整工程适合计算机专业本科生及自学编译器基础的学习者。资源基于C与C实现采用确定有限状态自动机识别标识符、整数常量、运算符等各类标记配合枚举与结构体保存标记类型、词法值和源码位置代码结构清晰便于理解词法分析全过程。压缩包共10个文件包含cpp源代码、dev工程、Makefile.win构建脚本、exe可执行程序、o目标文件及实验报告docx另附三个TINY测试样例整体约779KB轻量易用。已有1330人学习下载资源从DFA设计、状态转移函数到测试样例输出均有完整呈现实验报告详述构建步骤与排错思路可直接编译运行验证也可作为编译原理课设或实验报告的参考。1. 手工构造TINY词法分析器一个能让你彻底搞懂编译原理的经典实验很多学编译原理的人第一次直面“编译器到底是怎么读源代码的”这个黑匣子就是从TINY语言词法分析器开始的。TINY语言是教学里常用的一个极简语言没有复杂的类型系统没有函数重载token就那么十几种正好适合手工构造。网上流传的“编译原理手工构造TINY语言的词法分析器.zip”这类资源核心就是让你照着状态转换图用C或Java把扫描器一个一个字符地写出来。这事值得做是因为它能逼你亲手处理注释、空白、标识符与保留字的区分、非法字符报错这些真实问题。适合正在上编译原理课、需要交实验报告的学生也适合想补基础的一线开发。下面我把常见做法和踩过的坑拆开讲。2. 先看懂TINY的token设计词法规则与动手前的地基词法分析器的输入是一串字符输出是一串token。TINY语言的token集合不大但设计上覆盖了编译原理课程要求的几类典型token保留字、标识符、数字、特殊符号、注释和文件结束符。构造分析器之前必须先把token的种类、每个token的lexeme词素边界、以及哪些字符需要跳过一条条列清楚。2.1 TINY语言保留字与特殊符号从实验指导书里抄出token清单虽然网上那个zip包里的具体定义各家略有出入但经典的TINY语言Appel版或实验指导版一般包含这些保留字保留字用途if / then / else / end条件分支repeat / until循环read / write输入输出特殊符号则包括符号含义-*/算术运算符赋值或相等TINY里通常表示相等比较();小于、左右括号、语句结束符:赋值号如果实验要求支持的话初学者最容易犯的错误是漏掉:或者把和:混为一谈。TINY的经典语法里赋值用的是:而只是比较运算。如果实验指导书里没有明确说建议先按“是相等判断:是赋值”来设计否则后面语法分析阶段会吃亏。还有一个关键点注释。TINY语言的注释一般用花括号{ ... }包裹可能跨行。这个必须在词法分析器里处理掉注释不产生token但会占字符流的位置。如果注释里出现了不匹配的右花括号要报错。动手前我一般会先建一个token枚举把每个token的类型码列出来。用C语言的话可以这样定义typedef enum { TOKEN_IF, TOKEN_THEN, TOKEN_ELSE, TOKEN_END, TOKEN_REPEAT, TOKEN_UNTIL, TOKEN_READ, TOKEN_WRITE, TOKEN_ID, TOKEN_NUM, TOKEN_PLUS, TOKEN_MINUS, TOKEN_TIMES, TOKEN_OVER, TOKEN_EQ, TOKEN_LT, TOKEN_LPAREN, TOKEN_RPAREN, TOKEN_SEMI, TOKEN_ASSIGN, TOKEN_EOF, TOKEN_ERROR } TokenType;这段枚举的顺序会影响你后面写保留字查找表时的索引按分组排列调试时一眼能看出token类别。参数上TOKEN_ERROR是必需的不能省很多同学写完才发现无法给“非法字符”一个合理的返回值只能乱填一个数字后面语法分析器根本没法区分。2.2 状态转换图怎么画把“下一个字符”变成可执行的判断token的类型定了接下来要设计每个token的识别过程。手工构造词法分析器本质上就是把状态转换图DFA用if-else或switch-case实现出来。常见的做法是先画出每个token的状态转换图再对着图写代码。以标识符为例状态图是这样一条线第一个字符必须是字母后续字符可以是字母或数字。以数字为例第一个字符是数字后续可以是数字如果后面紧跟字母那按TINY的规则应该报错比如123abc是非法token。特殊符号则是一个字符对应一个终态但:需要两个字符所以:要设计成两个状态读到:时不能直接确定为:必须再看下一个字符。我不建议把整个DFA画在一张大图上而是画成几个小图分别对应“标识符/数字”、“特殊符号”、“注释”。每个小图用伪代码描述再落成代码。比如标识符状态 S0: 若是字母 - S1 S1: 若是字母或数字 - S1 否则 - 回退一个字符返回TOKEN_ID 数字状态 S0: 若是数字 - S1 S1: 若是数字 - S1 若是字母 - 报错 否则 - 回退一个字符返回TOKEN_NUM这里“回退一个字符”是手工构造的关键动作。因为当你读到if的空格时你已经把空格读进来了但这个空格不属于标识符必须把它退回到输入流让下一个token从空格后面开始。在C语言里这对应ungetc函数。很多实验要求不用lex这样的工具就是为了让你亲手写出这个回退逻辑。3. 手工构造词法分析器从状态机到可运行的C代码有了token定义和状态图下一步就是把它变成能跑起来的代码。这一节我给出一个常见做法用C语言实现一个getToken函数配合文件读写接口一次调用返回一个token。3.1 缓冲区与字符读取getChar和回退一个字符的ungetc词法分析器读的是整个源代码文件但没必要一次性把整个文件读进内存。经典做法是每次调用fgetc从文件流里读一个字符需要回退时用ungetc把它退回去。我习惯封装两个函数static int current_char; static FILE *source_file; static int getNextChar() { current_char fgetc(source_file); return current_char; } static void ungetChar() { if (current_char ! EOF) { ungetc(current_char, source_file); } }两个函数的逻辑说明getNextChar把文件流的下一个字符读进current_char变量并返回它。ungetChar则是把当前读进来的字符退回流注意必须判断current_char ! EOF因为EOF不是真正的字符不能退回去如果退回了EOF会导致后续读取错乱。这个边界是初学者最容易踩坑的地方。参数说明current_char用int而不是char是因为fgetc返回的是int目的是为了区分字符和EOFEOF通常是-1。如果你用char保存会把EOF截断成\xff之类的东西导致无法判断文件结束。3.2 核心扫描函数从DFA到switch-case的映射有了字符读取和回退就可以写核心的getToken函数。下面的代码是一个简化的、但能跑的版本识别保留字、标识符、数字、算术符号和注释。TokenType getToken(char *lexeme, int maxLen) { int c; int len 0; // 跳过空白和注释 for (;;) { c getNextChar(); if (c || c \t || c \n) { continue; } else if (c {) { // 注释读到右花括号为止 while ((c getNextChar()) ! } c ! EOF) ; if (c EOF) { strcpy(lexeme, unterminated comment); return TOKEN_ERROR; } continue; } else { break; } } if (c EOF) { strcpy(lexeme, EOF); return TOKEN_EOF; } // 标识符或保留字 if (isalpha(c)) { while (isalnum(c)) { if (len maxLen - 1) { lexeme[len] (char)c; } c getNextChar(); } lexeme[len] \0; ungetChar(); // 把非字母数字的字符退回 // 查保留字表 if (strcmp(lexeme, if) 0) return TOKEN_IF; if (strcmp(lexeme, then) 0) return TOKEN_THEN; // ... 其余保留字类似 return TOKEN_ID; } // 数字 if (isdigit(c)) { while (isdigit(c)) { if (len maxLen - 1) { lexeme[len] (char)c; } c getNextChar(); } if (isalpha(c)) { sprintf(lexeme, invalid number: %c, c); return TOKEN_ERROR; } lexeme[len] \0; ungetChar(); return TOKEN_NUM; } // 特殊符号 switch (c) { case : return TOKEN_PLUS; case -: return TOKEN_MINUS; case *: return TOKEN_TIMES; case /: return TOKEN_OVER; case : return TOKEN_EQ; case : return TOKEN_LT; case (: return TOKEN_LPAREN; case ): return TOKEN_RPAREN; case ;: return TOKEN_SEMI; case :: c getNextChar(); if (c ) { return TOKEN_ASSIGN; } ungetChar(); strcpy(lexeme, unexpected char :); return TOKEN_ERROR; default: sprintf(lexeme, unexpected char %c, c); return TOKEN_ERROR; } }代码逻辑说明这个函数的结构是模拟DFA的“状态”判断先跳过空白和注释进入识别主流程然后根据首字符的类型分三条支路处理标识符、数字、特殊符号。每条支路内部用循环读后续字符直到遇到不属于该token的字符为止再回退。参数说明lexeme是一个输出缓冲区用来存放token的原文词素maxLen是缓冲区大小。我习惯把maxLen设为256足够覆盖标识符长度。如果标识符超长上面代码里只是简单丢弃超出的字符实际实验里应该报错或者截断并提示这里写的是“截断”但更严谨的做法是在len达到maxLen时返回TOKEN_ERROR。建议读者按自己实验要求调整。一个需要特别留意的地方注释处理里如果遇到{后一直到文件结束都没有}代码会返回TOKEN_ERROR但词素里只写了unterminated comment并没有保留具体行号。更完整的做法是记录当前行号把行号也传出去。不过很多实验只要求返回token类型和词素行号是语法分析阶段的事。3.3 生成token流把词素长度和错误处理一起封装上面getToken每次只返回一个token类型但编译器的后续阶段通常还需要知道每个token的词素、所在行号、甚至token在文件中的偏移。所以一般还会做一个Token结构体来承载这些信息typedef struct { TokenType type; char lexeme[256]; int line; } Token; Token nextToken() { Token t; t.type getToken(t.lexeme, sizeof(t.lexeme)); t.line current_line; // 需要在读取字符时维护行号 return t; }维护行号的方法很简单在getNextChar里判断读到的字符是不是\n是则current_line。注释跨行时也要让行号跟着涨。这个细节很实用因为词法分析器的报错如果带行号调试效率会直线上升。封装的时候还要注意getToken内部调用了getNextChar和ungetChar这两个函数依赖全局变量source_file和current_line。更工程化的做法是把这些状态包装进一个结构体Lexer每次调用getToken都传入Lexer*。但很多课程实验为了简化直接用全局变量。我个人的建议是如果是交作业用全局变量没问题如果以后要扩展成多文件编译器最好现在就改成结构体否则后面语法分析器要同时维护文件指针和行号会很难受。4. 驱动测试与调试用最小测试程序验证每个token词法分析器写成后不能直接扔进编译器里必须先单独测试。很多人栽在这里主函数写得不对文件打不开或者token打印不出来。这一节我给一个可复制的最小驱动以及一套验证思路。4.1 构造覆盖性测试用例保留字、标识符、数字和注释一起上测试用例要覆盖所有token类型尤其是边界情况。我常用的一个TINY测试程序是这样的{ This is a comment } if x : 10 then repeat x : x - 1 until x 0 else write x注意这里用了:如果你的实验不支持就改成。另外要加一个非法用例比如123abc和看分析器会不会报错。测试文件里还要故意放一个不闭合的注释{ xxx看是不是返回unterminated comment错误。测试文件不要太大10行以内足够覆盖所有token。重点是要把“两个连续的符号”和“符号与标识符边界”测出来比如if后面直接跟(中间没有空格这时候if(要识别成if和(两个token不能识别成if(。4.2 编一个打印token流的驱动printf是词法分析器最好的朋友驱动主函数非常直白循环调用nextToken把类型和词素打印出来直到遇到TOKEN_EOF或TOKEN_ERROR。int main(int argc, char *argv[]) { if (argc 2) { printf(usage: lexer source-file\n); return 1; } source_file fopen(argv[1], r); if (!source_file) { perror(open source file); return 1; } current_line 1; Token t; do { t nextToken(); printf(%2d: %-12s %s\n, t.line, tokenTypeName(t.type), t.lexeme); } while (t.type ! TOKEN_EOF t.type ! TOKEN_ERROR); fclose(source_file); return 0; }代码逻辑说明tokenTypeName是一个把TokenType枚举转成字符串的函数可以用一个简单的数组或switch实现。打印时先输出行号再输出token类型名最后输出词素。这样每一行输出都是一个token方便和标准答案对比。参数说明argc和argv是命令行参数第一个参数是源码文件路径。我用fopen的r模式打开文本文件这在Windows和Linux下都能工作。如果文件路径里有中文或空格在Windows的cmd下要注意引号否则argv[1]会被截断。运行这个驱动看输出是否符合预期。比如上面的测试程序输出应该是1: ID if 2: ID x 2: ASSIGN : 2: NUM 10 2: THEN then ...这里有个细节注释行{ This is a comment }不输出任何token因为被跳过了。如果输出里出现了注释内容说明你的注释处理有问题。数字10后面跟着换行换行被跳过所以下一个token正常从下一行开始。如果输出中出现了unexpected char 这样的错误说明你测试的非法字符被正确捕获了。这时候再检查一下行号是否正确行号是调试时的关键线索。5. 避坑指南词法分析器实验最常见的5个翻车现场这个实验我见过无数人做也帮同学调过很多次代码。下面这几条坑基本覆盖了90%的翻车现场。每一条都按“现象 → 原因 → 解决”来写。5.1 标识符和保留字判断顺序写反导致if被当成普通ID现象输入if x then输出却是ID(if)而不是IF。原因代码先按标识符识别把所有字母序列都归为ID然后才去查保留字表如果查表逻辑写错了或者查表之前用了strcmp但词素末尾没正确加\0就会匹配失败。解决确认词素缓冲区末尾一定加了\0然后再做strcmp。另外查表应该放在“收集完整个字母数字序列之后”不能一读到i就把if判出来否则会把ifx错误地分成if和x两个token。5.2 回退字符把自己退死ungetc调用不当导致死循环现象程序卡死或者token流里反复出现同一个字符。原因ungetChar函数里没有判断current_char EOF结果把EOF退回了流。下一次fgetc又读回EOF于是进入无限循环。解决严格按我前面写的ungetChar的写法先判EOF再回退。另外如果用了C语言的ungetc同一个字符只能退一次不要连续调用两次ungetc同一个字符行为是未定义的。5.3 注释不跨行遇到换行就把注释结束了现象{ comment\n next line }这种注释只吃掉了第一行第二行变成了代码。原因注释处理的循环条件写成了while ((c getNextChar()) ! } c ! \n)意思是换行也终止注释。解决TINY的注释规则是花括号内任意字符都算注释包括换行。循环条件只判断}和EOF不要判断换行。如果你看到网上有些代码把换行排除在注释外那是别的语言规则不要抄。5.4 数字后跟字母没有报错而是把123abc当成两个token现象123abc输出NUM(123)和ID(abc)但实验要求应该报错。原因数字识别循环结束后没有检查下一个字符是不是字母。解决数字循环结束后如果c是字母或下划线直接生成一个TOKEN_ERROR词素写“invalid number: 123abc”。这里有个原则词法分析器发现非法token时应该尽量多吞几个字符作为错误信息而不是只报1。当然也可以只报错并停止分析但调试时会非常痛苦因为要反复改输入文件才能看到下一个错误。5.5 行号不对报错定位到错误的行现象报错说第5行有非法字符但实际第3行就是空行数下来意见不一致。原因行号递增只在getNextChar里做但注释内部跨行时读到的换行符没有递增行号。解决把行号递增放在getNextChar里统一处理这样任何路径读到换行都会加1。另外注意ungetChar退回的是字符不要退行号。如果退回的是换行符行号不能跟着减回去否则行号会错乱。实际项目里回退换行符的场景极少但如果发生宁可先不退换行符直接把它当成分隔符跳过。6. 进阶验证与收尾用标准输出对比法证明你的分析器是对的写完词法分析器怎么证明它是对的光看几条输出不够我一般用“标准输出对比法”准备一个test.tiny把期望的token输出保存为expected.txt然后运行你的分析器把实际输出重定向到actual.txt用diff对比。期望文件怎么生成如果是课程实验通常有老师给的标准答案如果没有就自己手工写一个。手工写的时候要人工模拟词法分析过程一行一行地数token。这个过程很枯燥但非常有价值相当于你自己当一遍编译器。等你手工写完期望文件你对TINY词法规则的理解会比看十遍理论都深。如果系统是Linux或macOS直接这样./lexer test.tiny actual.txt diff expected.txt actual.txt如果diff没有输出说明你的分析器和期望完全一致。如果输出有差异diff会告诉你每一处不同。我自己的习惯是先不看差异先把整个token流打印到屏幕上人眼扫一遍重点检查EOF是否正确出现在最后一行以及注释是否完全没有泄漏出来。然后再用diff严格比对。Windows下没有diff命令可以用fc代替lexer.exe test.tiny actual.txt fc expected.txt actual.txt还有一个小技巧写一个简单的shell脚本或Python脚本自动跑完所有测试用例并汇总结果。这样当你改了一个bug一键回归测试不会改坏别的地方。比如用一个Python脚本import subprocess cases [test1.tiny, test2_bad.tiny, test3_comment.tiny] for case in cases: subprocess.run([./lexer, case], stdoutopen(case .out, w)) # 然后对比 expected_xxx.txt这个做法比手动一条条敲命令高效得多。我当年做这个实验时就是用这个思路把测试用例从5个扩到了20个包括空文件、只有注释的文件、只有:没有操作数的文件。空文件特别有用它能验证getToken在第一次调用时就返回TOKEN_EOF而不是死循环或者返回一个未初始化的token。最后说一个过来人的教训不要急着把所有功能一次性写完再调试。我最初写这个分析器时先把标识符和数字的识别写好用两个测试用例验证通过再添加保留字逻辑再添加注释每次只改一小块。因为词法分析器的状态交织在一起一旦报错你要同时检查状态转换、回退、缓冲区、行号非常难定位。小步迭代每个版本都能跑、能验证你才能稳定地走到最后。希望这篇笔记帮到你按这个顺序做TINY词法分析器不会成为你编译原理路上的拦路虎。本文还有配套的精品资源点击获取