手写词法分析器实战：从课程实验到可扩展扫描器

简介这份资源是北京邮电大学编译原理课程实验一的词法分析器实现包面向正在学习编译原理、需要动手完成扫描器设计的高校学生与自学者帮助解决从词法规则定义到分词逻辑落地的实践问题。压缩包共4个文件约10KB以cpp源代码与h头文件为核心辅以txt说明与测试用例分别承担词法分析算法实现、词素类型声明、实验说明与输入样例验证等用途体量轻便、结构紧凑。目前已有1002人学习下载具备一定的参考热度。读者可从中获得一套可编译运行的词法分析器参考实现理解正则表达式或EBNF描述词法规则、字符流读取与特殊情况处理、词素识别与符号栈管理、非法输入的错误报告与恢复等关键环节并借助测试样例对照调试为后续语法分析与语义分析打下基础。1. 从一份课程实验压缩包说起词法分析器到底在做什么打开这份压缩包第一眼看到的是几个源文件和一份实验说明名字很朴素叫“词法分析器”。很多同学第一次接触编译原理会觉得词法分析只是把字符流切成一个个单词没什么技术含量真正难的是语法分析和代码生成。但真动手写一遍就会发现词法分析器是整个编译前端的第一道关卡它决定了后续语法分析器能不能拿到干净、准确、带位置信息的 token 序列。这份课程实验资源来自某高校编译原理课程的实验一目标很明确给定一段类 C 语言的源程序输出每个单词的类别、内容和行号遇到非法字符要报错。它适合正在上编译原理课、需要交实验报告的同学也适合想从零理解编译器前端链路的开发者拿来练手。整个项目不依赖大型框架核心就是一个手写的扫描器配合状态机思路代码量不大但把正则表达式、有限自动机、符号表这些概念落到了实处。下面我按“先跑起来、再看结构、最后改得动”的顺序把这份实验拆开讲清楚。2. 项目结构与技术选型一个手写扫描器的骨架2.1 目录里有什么每个文件管什么解压后典型的目录结构大致如下不同年份的实验模板可能略有差异但核心文件跑不出这几类lexer-lab/ ├── src/ │ ├── main.c # 程序入口读文件、调扫描器、打印结果 │ ├── scanner.c # 词法扫描核心实现 │ ├── scanner.h # token 类型定义与函数声明 │ └── symtab.c # 关键字表 / 符号表管理 ├── test/ │ ├── sample1.c # 正常源程序样例 │ └── sample2.c # 含非法字符的测试样例 ├── Makefile # 编译脚本 └── README.md # 实验说明与运行方式这个结构是课程实验里最常见的 C 语言工程组织方式入口、核心逻辑、头文件、辅助模块分离。scanner.h里一般会定义 token 的枚举类型比如ID、NUM、KEYWORD、OPERATOR、DELIMITER、ERROR以及一个结构体用来承载每次扫描的结果。symtab.c负责关键字识别常见做法是用一个字符串数组存if、else、while、int这些保留字扫描到标识符后先查表命中就归为关键字否则归为普通标识符。这种“先按标识符规则扫再查关键字表”的顺序是词法分析器的标准套路避免了为每个关键字单独写一条匹配规则。技术选型上这份实验用的是纯 C 语言没有引入 lex/flex 这类自动生成工具。这一点很关键用 flex 生成词法分析器当然快但课程实验的目的就是让你手写状态机理解“正则表达式到有限自动机”的转换过程。所以代码里能看到大量switch、if-else和字符判断而不是一张规则表。对于想二次开发的人来说手写扫描器的好处是逻辑透明改一个 token 规则只需要动对应的分支不用重新生成代码。2.2 核心数据结构token 长什么样在动手看扫描逻辑之前先搞清楚 token 的数据结构。scanner.h里通常会有类似这样的定义typedef enum { TOKEN_ID, // 标识符 TOKEN_NUM, // 数字常量 TOKEN_KEYWORD, // 关键字 TOKEN_OP, // 运算符 TOKEN_DELIM, // 分隔符 TOKEN_ERROR, // 非法字符 TOKEN_EOF // 文件结束 } TokenType; typedef struct { TokenType type; // 单词类别 char lexeme[64]; // 单词原文 int line; // 所在行号 int col; // 所在列号 } Token;这个结构体是后续所有模块的契约。type决定语法分析器怎么处理lexeme保留原始文本用于报错和语义分析line和col是错误定位的关键。很多同学写实验时只存类别不存位置结果报错信息只能写“某处有错”实验验收时被追问就说不清了。我一般建议一开始就把行列号带上扫描器每读一个字符就维护当前行列换行时行号加一、列号归零。这个习惯在后续做语法分析、语义分析时都会受益因为错误恢复和调试都依赖精确位置。2.3 扫描主循环一个字符一个字符地推进词法分析器的核心是一个循环不断从输入流取字符根据当前字符决定进入哪个分支匹配完一个 token 后回退多余字符然后继续。scanner.c里的主函数通常长这样Token next_token(FILE *fp) { Token tok; int ch; skip_whitespace(fp); // 跳过空格、制表、换行 ch fgetc(fp); if (ch EOF) { tok.type TOKEN_EOF; return tok; } if (isalpha(ch) || ch _) { // 标识符或关键字 return scan_identifier(fp, ch); } if (isdigit(ch)) { // 数字常量 return scan_number(fp, ch); } if (is_operator(ch)) { // 运算符可能双字符 return scan_operator(fp, ch); } if (is_delimiter(ch)) { // 分隔符 tok.type TOKEN_DELIM; tok.lexeme[0] ch; tok.lexeme[1] \0; return tok; } tok.type TOKEN_ERROR; // 其他一律报错 tok.lexeme[0] ch; tok.lexeme[1] \0; return tok; }这段代码的逻辑很直白先跳过空白再看首字符属于哪一类。scan_identifier会继续读后续的字母、数字、下划线直到遇到非标识符字符然后用ungetc把多读的那个字符退回输入流。scan_number类似但要注意处理小数点、科学计数法这些边界情况课程实验里一般只要求整数但如果你要扩展这里就是入口。scan_operator需要处理、!、、、、||这类双字符运算符常见做法是读到第一个运算符后再预读一个字符如果组合合法就吞掉否则退回。这个“预读加回退”的模式是手写扫描器的经典手法理解它之后后面加新运算符就是照葫芦画瓢。参数说明fp是已打开的源文件指针函数每次调用返回一个 token调用方循环调用直到TOKEN_EOF。这种“拉模式”比一次性扫描全部 token 存进数组更省内存也方便和语法分析器做流式对接。如果你的实验要求先输出完整 token 表那就在main.c里循环调用next_token并打印即可。3. 跑起来编译、测试与结果验证3.1 编译命令与 Makefile 怎么用这份实验的编译方式很标准进入项目根目录执行make即可。如果目录里没有 Makefile手动编译也不复杂gcc -Wall -g -o lexer src/main.c src/scanner.c src/symtab.c-Wall打开所有警告-g保留调试符号。我强烈建议加上-Wall因为手写扫描器里常见的“忘记处理某个分支”“变量未初始化”这类问题编译器警告能提前拦住一大半。编译成功后生成lexer可执行文件运行方式一般是./lexer test/sample1.c程序会读取指定源文件逐行输出 token 的类别、原文和行号。有些实验模板要求从标准输入读取那就用./lexer test/sample1.c。具体看main.c里是fopen(argv[1])还是stdin改起来也就一行的事。3.2 用样例文件验证输出拿一个最小样例来验证比如test/sample1.c里写int main() { int a 10; if (a 5) return a; return 0; }期望输出大致是int识别为关键字main识别为标识符(){}识别为分隔符识别为运算符1050识别为数字常量。跑完之后逐行对照重点看三件事关键字有没有被误判成标识符、双字符运算符有没有被拆成两个单字符、行号有没有在换行后正确递增。这三项是实验验收的高频检查点也是手写扫描器最容易翻车的地方。如果输出里出现TOKEN_ERROR先别急着改代码把出错字符和行号打出来对照源文件看是不是样例里本来就有非法字符。test/sample2.c通常就是故意放了一些、$之类的符号来测试错误处理能正确报错反而是加分项。3.3 常见运行失败与排查顺序跑不起来的时候按这个顺序排查效率最高先看编译有没有报错链接错误多半是scanner.c或symtab.c没加进编译命令再看运行时有没有段错误常见原因是lexeme数组越界标识符太长或者没加字符串结束符最后看输出是否符合预期如果所有 token 都是ERROR检查fgetc的返回值有没有被存成char导致 EOF 判断失效。这个排查顺序是我踩过几次坑之后固定下来的从编译到运行再到逻辑逐层收窄比一上来就盯着扫描函数看要快得多。4. 核心模块拆解标识符、数字与运算符的识别细节4.1 标识符与关键字先扫再查表标识符的识别规则是“字母或下划线开头后跟零个或多个字母、数字、下划线”。代码实现上scan_identifier通常这样写Token scan_identifier(FILE *fp, int first) { Token tok; int i 0; int ch first; while (isalnum(ch) || ch _) { if (i 63) tok.lexeme[i] (char)ch; ch fgetc(fp); } tok.lexeme[i] \0; ungetc(ch, fp); // 多读的字符退回 if (is_keyword(tok.lexeme)) { // 查关键字表 tok.type TOKEN_KEYWORD; } else { tok.type TOKEN_ID; } return tok; }这里有两个细节值得说。第一i 63的边界判断不能省虽然课程样例里标识符不会太长但一旦输入超长标识符没有边界检查就是缓冲区溢出运行时直接崩溃调试起来很费时间。第二ungetc只能保证退回一个字符所以循环里每次只多读一个这个约束决定了扫描器的写法不能一次性读一大段再处理。is_keyword的实现就是遍历关键字数组做字符串比较关键字数量少的时候线性查找完全够用不需要上哈希表。4.2 数字常量整数、小数与边界数字识别比标识符多一层考虑要不要支持小数和科学计数法。课程实验一一般只要求无符号整数但代码里留好扩展点没坏处Token scan_number(FILE *fp, int first) { Token tok; int i 0; int ch first; while (isdigit(ch)) { tok.lexeme[i] (char)ch; ch fgetc(fp); } if (ch .) { // 小数部分按需启用 tok.lexeme[i] (char)ch; ch fgetc(fp); while (isdigit(ch)) { tok.lexeme[i] (char)ch; ch fgetc(fp); } } tok.lexeme[i] \0; ungetc(ch, fp); tok.type TOKEN_NUM; return tok; }如果实验只要求整数把if (ch .)那段删掉即可。要注意的是数字后面紧跟字母的情况比如123abc严格来说应该报错因为这不是合法的 token。常见做法是在数字扫描结束后检查下一个字符如果是字母或下划线就标记为TOKEN_ERROR。这个边界处理很多同学会漏验收时拿一个123abc一测就露馅了。4.3 运算符与分隔符双字符运算符的预读回退运算符识别是手写扫描器里最需要小心的地方因为和、和、和都是前缀关系。处理方式统一为“读一个预读一个能组合就组合不能就退回”Token scan_operator(FILE *fp, int first) { Token tok; int next fgetc(fp); tok.lexeme[0] (char)first; tok.lexeme[1] \0; tok.type TOKEN_OP; if ((first next ) || (first ! next ) || (first next ) || (first next ) || (first next ) || (first | next |)) { tok.lexeme[1] (char)next; tok.lexeme[2] \0; } else { ungetc(next, fp); // 不是双字符退回 } return tok; }这段代码把双字符运算符的组合规则集中在一个if里加新运算符就是往条件里加一行维护成本低。分隔符如(、)、{、}、;、,都是单字符直接返回即可不需要预读。这里有个容易忽略的点和|单独出现时在 C 语言里也是合法运算符按位与、按位或所以不能因为没匹配到就报错退回后按单字符运算符处理才是对的。4.4 错误处理与行号维护别让报错信息变成黑匣子错误处理的质量直接决定实验报告好不好写。扫描器遇到非法字符时除了返回TOKEN_ERROR还应该把行号、列号和字符本身带出去让main.c能打印出“第 5 行第 12 列出现非法字符 ”这样的信息。行号维护的常见做法是在skip_whitespace里检测换行void skip_whitespace(FILE *fp) { int ch; while ((ch fgetc(fp)) ! EOF) { if (ch \n) { current_line; current_col 0; } else if (ch || ch \t || ch \r) { current_col; } else { ungetc(ch, fp); break; } } }current_line和current_col用全局变量或扫描器上下文结构体维护都行课程实验规模小全局变量更省事。但要注意ungetc退回的字符不会影响行列计数因为计数是在读取时递增的退回后下次重新读到会再计一次逻辑上保持一致。如果发现行号总是差一检查一下是不是在next_token开头就把行号加了或者在换行判断上用了\r\n只处理了\n。5. 避坑与排查手写扫描器最容易翻车的五个地方5.1 现象所有 token 都变成 ERROR程序像没读文件原因通常是fgetc的返回值被存进了char类型。fgetc返回intEOF 是-1如果存成char在某些平台上-1会变成255导致 EOF 判断永远不成立或者字符比较全部错位。解决方法是所有接收fgetc返回值的变量都声明为int包括next_token里的ch和各个scan_*函数里的临时变量。这个坑很隐蔽因为编译不一定报错运行时表现却是“读不到文件”或者“全是乱码”。5.2 现象双字符运算符被拆成两个单字符比如输出成两个输出成和。原因多半是scan_operator里预读逻辑写反了或者ungetc调用位置不对。检查两点预读的字符在组合成功时有没有写进lexeme组合失败时有没有退回。另外如果next_token在调用scan_operator之前已经把第二个字符读走了也会导致组合失败确保运算符分支里只传首字符进去。5.3 现象关键字被识别成普通标识符比如int输出为TOKEN_ID。先检查is_keyword的关键字表里有没有这个词再检查查表时机是不是在lexeme拼接完成之后。常见错误是在循环里边读边查此时lexeme还不完整自然查不到。正确顺序是先把整个标识符扫完、补上\0再查表。如果关键字表用的是二维数组注意字符串比较用strcmp而不是。5.4 现象超长标识符导致程序崩溃或输出截断lexeme数组开得太小或者循环里没做边界判断。课程样例一般不会触发但验收时老师随手敲一长串字符就可能崩。解决方法是给lexeme一个明确上限比如 64 或 128循环里加i MAX_LEN - 1的判断超出部分可以选择截断并报错或者继续消费字符但不存储。我一般选择后者保证 token 流不被打断同时在报告里说明超长标识符的处理策略。5.5 现象行号在跨行注释或字符串里错乱如果实验要求支持注释和字符串常量行号维护就不能只在skip_whitespace里做。注释和字符串内部也可能有换行扫描这些结构时要同步更新current_line。常见做法是把行号更新封装成一个advance_char函数所有读字符的地方都走它避免漏更新。这个坑在只做基础词法的实验里不一定遇到但一旦扩展功能就会冒出来提前把结构留好能省不少返工。6. 二次开发把课程实验改成能用的词法分析器6.1 扩展方向一支持注释与字符串常量课程实验一通常不要求注释和字符串但这两项是真实编译器前端的必备能力。改造入口在next_token的分支判断里遇到/时预读下一个字符如果是/就进入单行注释扫描一直读到换行如果是*就进入多行注释扫描直到遇到*/。字符串常量则以开头循环读取直到遇到未转义的中间处理\和\\这类转义序列。改造时注意注释和字符串都不产生 token或者字符串产生一个TOKEN_STRING但行号必须照常维护。我一般会先写一个skip_comment函数在skip_whitespace之后、正式取 token 之前调用这样主循环结构不用大改。6.2 扩展方向二把硬编码规则抽成配置表手写扫描器的规则散落在各个if分支里加一种 token 就要改多处。如果想让这份实验代码具备一点工程性可以把运算符和关键字抽成配置表static const char *keywords[] {if, else, while, for, int, return, NULL}; static const char *two_char_ops[] {, !, , , , ||, NULL};然后在is_keyword和scan_operator里遍历这些表。好处是新增关键字或运算符只改数组不动逻辑。更进一步可以把单字符运算符和分隔符也做成表用查表代替switch。这个改造不复杂但能让代码的可读性和可维护性上一个台阶写进实验报告里也是加分项。6.3 验证方法用对拍和边界用例兜底改完之后怎么确认没改坏我的习惯是准备三组用例正常程序、边界用例、错误用例。正常程序用课程样例边界用例包括最长标识符、连续运算符ab、数字后跟字母123abc、空文件、只有注释的文件错误用例放非法字符和未闭合字符串。每组跑完对照预期输出重点看 token 序列和行号。如果条件允许可以写一个简单的对拍脚本把改造前后的输出 diff 一下确认只有预期内的变化。这个习惯看起来麻烦但比改完直接交要稳得多毕竟词法分析器的 bug 会一路传导到语法分析越晚发现越难查。6.4 一个具体技巧用 token 流做单元测试最后分享一个我在课程实验里常用的小技巧把next_token的输出重定向成一行一个 token 的文本格式比如KEYWORD int 1:1然后用 shell 脚本或 Python 做断言。这样每次改扫描器跑一遍测试脚本就知道有没有回归。相比人工看输出脚本能覆盖更多用例也方便在报告里展示测试覆盖率。具体做法是在main.c里加一个--dump参数走不同的打印分支不影响正常输出。这个技巧不改变核心逻辑但能让二次开发的过程可控很多。从那以后我每次改扫描器规则都强制先跑一遍边界用例再动主逻辑血泪经验是曾经为了加一个运算符把的识别改崩了排查了半天才发现是预读回退的顺序写反了。希望这份拆解能帮你少走同样的弯路把实验跑通、改顺真正理解词法分析这一层的设计取舍。本文还有配套的精品资源点击获取