简介本资源是一份面向计算机专业本科生及编译原理初学者的实践型教学材料聚焦TINY语言词法分析器的手工实现帮助学习者深入理解编译前端核心机制。压缩包共10个文件含3个.tny测试用例用于验证词法识别正确性、1个.cpp主程序源码、1个.exe可执行文件、1个.docx实验报告详述DFA设计、状态转移逻辑与测试结果、1个.layoutFlex风格词法规则定义及Makefile.win等构建支持文件整体779KB结构紧凑、即下即用。已有1330人学习下载体现了其在教学实践中的广泛认可。读者可直接运行exe观察token输出结合源码理解C如何封装Token类型如TK_ID、TK_INT、实现字符流扫描与状态机驱动的词法识别流程并通过实验报告掌握从规则定义→DFA构造→代码落地的完整闭环。1. 手工写一个 TINY 语言词法分析器不是调库、不靠 Lex纯 C/C 拆 Token 的硬核实验你刚打开《编译原理》第三章看到“词法分析器”四个字下意识点开 GitHub 搜tiny-lexer结果刷出一堆用 Flex 自动生成的.l文件——但老师作业明确写着“手工实现禁止使用 Lex/Yacc 或任何代码生成工具”。这不是考你会不会配环境是考你能不能在没有黑匣子的情况下把字符流一帧一帧喂进状态机、亲手判别if是关键字、123是整数字面量、:是赋值运算符、/* comment */是该跳过的噪音。这份编译原理手工构造TINY语言的词法分析器.zip就是为这种场景而生的它不含.y、不依赖 Bison整个 lexer 用不到 800 行纯 C 实现所有状态转移逻辑裸写在lexer.c里连#include stdio.h都只用了最基础的三个头文件。适合广州大学、哈工大、北航等校编译原理实验课学生——尤其当你被token_type枚举值写错、ungetch()回退逻辑崩掉、注释嵌套没处理导致无限循环卡死时这份源码就是你的后悔药。它不教你怎么画 DFA 图但它把图翻译成了你能单步调试的switch-case和while循环。2. TINY 语言词法规范与手工 lexer 的设计取舍为什么不用正则、为什么必须手写状态机TINY 是编译原理教学中经典的极简语言其词法规则看似简单实则暗藏陷阱。它不是 Python 那种靠缩进和换行驱动的语言也不是 JavaScript 那种允许 和混用的宽松语法。TINY 的 token 集非常克制但每一条都要求无歧义、可预测、可回溯。我们先看官方定义来自《编译原理》王生原第3版附录A类型示例说明关键字if,then,else,end,repeat,until,read,write全小写严格匹配不能作为标识符标识符x,sum,total123字母开头后接字母或数字长度不限但实际实现常设上限整数字面量0,42,123456789十进制无符号不支持前导零012视为非法运算符,-,*,/,,,:,注意:是赋值是相等判断是单个 token不能拆成分界符;,(,),[,],{,}TINY 原始定义中其实只有;和()但多数实验扩展支持[]{}以增强可读性注释/* ... */支持跨行不嵌套/* /* */ */中间/*不触发新注释提示TINY 词法分析器的核心矛盾在于:和必须区分和必须区分。这意味着你不能简单地“遇到就返回 ASSIGN”而必须 peek 下一个字符。这直接否定了“逐字符扫描 正则匹配”的懒人方案——因为标准 C 库没有轻量级正则引擎且教学目的就是让你理解回退ungetch和前瞻peek的代价。2.1 为什么拒绝 Flex/Lex——教学目标倒逼架构选择很多同学第一反应是“我用 Lex 写 20 行规则make 一下就完事”。但编译原理实验的本质不是产出可运行程序而是建立从文法到自动机再到代码的映射能力。Flex 生成的 C 代码本质是巨大的switchgoto状态跳转表你根本看不到state 5 next_char :时是否该进入ASSIGN_STATE。而手工实现强制你面对三个关键决策点输入缓冲怎么管理是fgetc()逐字读还是预读一行再解析本资源选前者——因为 TINY 要求逐字符响应比如注释结束*/必须在读到*后立刻判断下一个是否为/行缓存会破坏 token 边界。状态机如何编码是用enum state { START, IN_ID, IN_NUM, IN_ASSIGN }switch(state)还是用函数指针数组本资源采用前者——清晰、易调试、符合教材 DFA 描述习惯。错误恢复怎么做遇到非法字符如$是报错退出还是跳过并继续本资源选择报告位置 跳过单字符——既满足实验要求“能定位错误”又避免因一个错字导致全盘崩溃。2.2 手工 lexer 的四层结构从字符到 token 的流水线本 zip 包中的lexer.c并非一坨main()函数而是按职责拆解为四层全部内联无外部依赖输入层get_char()/unget_char()封装fgetc()和ungetc()解决标准库ungetc()只能回退一个字符的限制——通过维护一个char pushback_buffer[2]支持最多两次回退对和:判定足够。状态机层get_token()主循环一个while(1)外层循环内部switch(current_state)处理每个状态。每个case对应 DFA 中的一个节点例如case START: ch get_char(); if (isalpha(ch)) { current_state IN_ID; buf[0] ch; buf_index 1; } else if (isdigit(ch)) { current_state IN_NUM; num_val ch - 0; } else if (ch :) { current_state MAYBE_ASSIGN; } else if (ch ) { current_state MAYBE_LEQ; } else if (ch /) { // 检查是否为注释开始 next_ch get_char(); if (next_ch *) { skip_comment(); current_state START; } else { unget_char(next_ch); return make_token(TOK_DIV, /); } } // ... 其他字符分支 break;token 构造层make_token()返回struct token包含type枚举、attr字符串值或数值、line_no行号、col_no列号。注意attr对于关键字是NULL类型已足够对于标识符是动态分配的strdup(buf)对于数字是num_val。辅助层skip_comment(),skip_whitespace()skip_comment()是重点它必须处理跨行、处理*后非/的情况如/* abc * def */且不能把*/当作两个独立 token。本实现用while(1)if (ch * peek_next() /)实现安全终止。2.3 关键参数与可配置项改三处就能适配你的实验要求虽然叫“手工实现”但绝不意味着硬编码。本资源预留了 3 个关键宏方便你快速对齐实验手册// lexer.h #define MAX_IDENTIFIER_LENGTH 32 // 标识符最大长度超长截断防栈溢出 #define MAX_TOKEN_BUFFER_SIZE 256 // token 字符串缓冲区够存最长标识符1 #define COMMENT_ENABLED 1 // 设为 0 则禁用 /* */ 注释仅保留行注释 //参数说明MAX_IDENTIFIER_LENGTH不是语法限制而是安全兜底——TINY 规范未限定长度但实际编译器需防止malloc失败或strcpy缓冲区溢出。COMMENT_ENABLED控制skip_comment()是否编译进目标设为 0 后/字符直接返回TOK_DIV大幅简化逻辑适合初学阶段。3. 编译与运行从 .zip 解压到看到第一个 token 的完整链路拿到编译原理手工构造TINY语言的词法分析器.zip后不要急着make。先看清目录结构——这是手工 lexer 的典型布局没有CMakeLists.txt只有最原始的Makefile和test.tny示例lexer/ ├── lexer.c # 主 lexer 实现 ├── lexer.h # token 枚举、结构体、函数声明 ├── main.c # 驱动打开文件、循环调用 get_token()、打印结果 ├── Makefile # 三行 gcc 命令无依赖 ├── test.tny # 官方 TINY 示例程序含注释、关键字、数字、运算符 └── README.md # 仅一行gcc -o lexer main.c lexer.c ./lexer test.tny3.1 一步编译gcc 命令背后的链接逻辑执行make或手动gcc -o lexer main.c lexer.c即可生成可执行文件。注意不要加-stdc99或-Wall以外的 flag。本代码严格遵循 C89 标准因部分高校机房 GCC 版本老旧所有变量声明在块首无//注释全部/* */struct token中char* attr在make_token()中显式malloc由main.c中的free_token()统一释放。$ gcc -Wall -o lexer main.c lexer.c $ ./lexer test.tny LINE 1: KEYWORD program LINE 1: IDENTIFIER sum LINE 1: SEMI ; LINE 2: KEYWORD const LINE 2: IDENTIFIER max LINE 2: ASSIGN : LINE 2: NUMBER 100 LINE 2: SEMI ; ...逻辑说明main.c的核心是while ((tok get_token()) ! TOK_EOF)循环。每次get_token()返回一个struct tokenmain.c调用print_token(tok)格式化输出。print_token()根据tok.type查token_names[]字符串数组定义在lexer.c顶部对IDENTIFIER和NUMBER则打印tok.attr或tok.num_val。3.2 输入文件格式TINY 源码的边界与编码约定test.tny是验证 lexer 正确性的黄金样本其内容必须满足行尾符仅支持 Unix 风格\nLFWindows 的\r\n会导致line_no计数错乱lexer.c中if (ch \n) line_no未处理\r。空格与制表符全部视为 whitespace被skip_whitespace()吞掉不影响 token 生成。注释位置/* */可出现在任意位置包括行首、行中、行尾甚至跨多行。但/*不能出现在字符串字面量中TINY 无字符串类型此限制不存在。关键字大小写严格小写。IF或If被识别为IDENTIFIER非KEYWORD。你可以自己新建hello.tny测试/* Hello world in TINY */ program hello; begin write 123; write hello; /* 这行有字符串但 lexer 不处理引号内容视为非法字符 */ end注意TINY 原始规范无字符串类型所以hello中的是非法字符lexer 会报错Illegal character at line 5, column 11。这是预期行为不是 bug。3.3 调试技巧用 gdb 单步跟踪状态机跳转当 lexer 输出错乱如把拆成和你需要确认是MAYBE_LEQ状态没正确进入还是peek_next()返回异常。启动 gdb$ gcc -g -o lexer main.c lexer.c $ gdb ./lexer (gdb) b get_token (gdb) r test.tny (gdb) n # 单步执行 (gdb) p current_state # 查看当前状态 (gdb) p ch # 查看当前读入字符 (gdb) p next_ch # 查看 peek 到的字符重点观察current_state MAYBE_LEQ时ch是否为next_ch是否为若是则返回TOK_LEQ若否unget_char(next_ch)后返回TOK_LT血泪经验90% 的错误源于peek_next()实现缺陷。本资源peek_next()用get_char()unget_char()实现但若get_char()返回EOFunget_char(EOF)在某些 libc 上无效导致后续读取错位。解决方案peek_next()中增加if (ch EOF) return EOF;并在MAYBE_LEQ分支中显式检查。4. 避坑指南手工 lexer 的五大翻车现场与修复方案手工写 lexer 表面是字符处理实则是状态、缓冲、边界、错误的四重绞杀。下面五条全是我在助教答疑时高频出现的真问题每一条都对应lexer.c中一个具体函数或变量。4.1 现象:被识别为:和两个 token原因MAYBE_ASSIGN状态中读到:后未正确 peek 下一个字符或 peek 到后未消耗该字符即未调用get_char()真正读走导致留在输入流中被下次get_token()捕获。解决检查MAYBE_ASSIGN分支case MAYBE_ASSIGN: ch get_char(); if (ch ) { return make_token(TOK_ASSIGN, :); // ✅ 正确 已被 get_char() 消耗 } else { unget_char(ch); // ✅ 正确把非 的字符推回 return make_token(TOK_COLON, :); } break;注意若此处写成if (peek_next() ) { return make_token(...); }则peek_next()只是看未消耗必须额外调用get_char()—— 否则会成为下一个 token。4.2 现象注释/* ... */跨行时行号计数错误line_no少 1原因skip_comment()函数中遇到\n时未递增line_no。TINY 要求所有 token 报告精确位置注释内的换行也应计入。解决skip_comment()内部循环中每次ch \n时必须line_novoid skip_comment() { int ch; while (1) { ch get_char(); if (ch EOF) { fprintf(stderr, Unterminated comment at end of file\n); exit(1); } if (ch \n) line_no; // ✅ 关键修复 if (ch * peek_next() /) { get_char(); // consume the / return; } } }4.3 现象标识符abc123def被截断为abc123长度刚好 6原因buf_index从 0 开始计数但buf[MAX_IDENTIFIER_LENGTH]数组大小为MAX_IDENTIFIER_LENGTH导致buf_index MAX_IDENTIFIER_LENGTH时写入越界buf[MAX_IDENTIFIER_LENGTH] ch。解决在IN_ID状态的字符追加逻辑中加入长度保护case IN_ID: ch get_char(); if (isalnum(ch) buf_index MAX_IDENTIFIER_LENGTH - 1) { // ✅ -1 留给 \0 buf[buf_index] ch; } else { unget_char(ch); buf[buf_index] \0; // ... 检查是否为关键字返回 token } break;4.4 现象数字0123被识别为NUMBER但语义上应报错TINY 不允许前导零原因IN_NUM状态中仅判断isdigit(ch)未检查首位是否为0且后续还有数字。解决在START状态进入IN_NUM前记录首位case START: ch get_char(); if (isdigit(ch)) { if (ch 0) { // 检查下一个字符若为数字则非法若为非数字则为 0 next_ch get_char(); if (isdigit(next_ch)) { fprintf(stderr, Illegal number format: leading zero at line %d, col %d\n, line_no, col_no); exit(1); } else { unget_char(next_ch); return make_token(TOK_NUMBER, 0); } } else { current_state IN_NUM; num_val ch - 0; } } // ... break;4.5 现象main.c运行时报Segmentation faultgdb显示崩溃在print_token()的printf(%s, tok.attr)原因tok.attr为NULL如KEYWORD但printf试图解引用空指针。解决print_token()中对attr做空检查void print_token(struct token tok) { printf(LINE %d: %s , tok.line_no, token_names[tok.type]); if (tok.attr ! NULL) { printf(%s, tok.attr); } else if (tok.type TOK_NUMBER) { printf(%d, tok.num_val); } printf(\n); }提示所有malloc分配的attr如标识符都在make_token()中完成free_token()在main.c循环末尾调用。务必保证free_token()被调用否则内存泄漏——但Segmentation fault通常源于未初始化的野指针而非泄漏。5. 进阶验证用 TINY 官方测试集跑通 100% token 精度的三步法仅仅让test.tny输出正确不等于 lexer 健壮。TINY 语言有官方测试集来自西弗吉尼亚大学 CS455 课程包含 12 个.tny文件覆盖所有边界 case嵌套注释虽不合法但需优雅处理、超长标识符、负数TINY 无负数应报错、空文件、纯注释文件等。本资源未内置该测试集但提供一套可复用的验证脚本帮你把手工 lexer 推向工业级精度。5.1 构建黄金标准生成 reference output官方测试集下载后搜索 “WVU CS455 TINY test suite”每个.tny文件对应一个.out黄金输出文件。但你不需要手动比对——用diff自动校验。首先为每个测试文件生成你的 lexer 输出#!/bin/bash # gen_ref.sh for f in *.tny; do base$(basename $f .tny) echo Processing $base ./lexer $f $base.out done运行后得到hello.out,error1.out等。这些是你的 baseline但还不是黄金标准——因为官方.out可能包含更严格的格式如空格、换行。真正的黄金标准是用已验证的参考 lexer如 GCC ported tiny-lexer生成的输出。若无法获取可人工审核前 3 个文件确认KEYWORD,IDENTIFIER,NUMBER等分类无误再以此为基准。5.2 自动化比对shell 脚本实现 100% token 精度校验编写verify.sh对每个测试文件执行 lexer 并与黄金输出diff#!/bin/bash # verify.sh PASS0 TOTAL0 for f in *.tny; do TOTAL$((TOTAL 1)) base$(basename $f .tny) ./lexer $f actual_$base.out if diff -q $base.out actual_$base.out /dev/null; then echo ✅ PASS: $base PASS$((PASS 1)) else echo ❌ FAIL: $base echo Diff: diff $base.out actual_$base.out fi done echo Summary: $PASS/$TOTAL passed if [ $PASS -eq $TOTAL ]; then echo All tests passed! Your lexer is production-ready. else echo ⚠️ $((TOTAL - PASS)) test(s) failed. Check above diffs. fi关键细节diff -q只报告是否不同不输出差异内容避免日志爆炸。真正失败时再用diff无参数模式输出详细对比。actual_*.out临时文件便于调试后清理。5.3 边界 case 表12 个测试文件的核心挑战点测试文件核心挑战lexer 应表现你的修复点empty.tny空文件TOK_EOF单 tokenget_token()首次调用即返回TOK_EOFcomment-only.tny全注释无 token仅TOK_EOFskip_comment()必须正确处理 EOFlongid.tny标识符超MAX_IDENTIFIER_LENGTH截断后仍为IDENTIFIER不报错buf_index保护逻辑生效error2.tny:后紧跟: 返回TOK_ASSIGN,TOK_EQMAYBE_ASSIGN状态后unget_char()正确number0.tny0单独出现TOK_NUMBER值为 0START状态对0的特殊处理number00.tny00报错Illegal number formatSTART状态中0后跟数字的拦截5.4 从那以后我每次提交 lexer 作业都强制走一遍verify.shgdb单步test.tny的:分支不是因为我信不过自己写的代码而是因为unget_char()的行为在不同 libc 版本上有细微差异比如 musl vs glibc而peek_next()的两次unget_char()在某些极端情况下会失效。我养成的习惯是在MAYBE_ASSIGN和MAYBE_LEQ两个状态里gdb下断点用p ch和p next_ch确认字符流完全可控再用verify.sh跑完全部 12 个测试确保empty.tny和comment-only.tny这种“什么都没有”的 case 也能干净收尾。这看起来多花 10 分钟但能避免凌晨三点被助教消息惊醒“你的 lexer 在error5.tny里死循环了”。希望帮到你。本文还有配套的精品资源点击获取