简介本资源是面向编译原理初学者与高校课程实践者的TINY语言词法分析器完整实现工程聚焦C/C手写DFA状态机的核心教学场景解决词法分析阶段从理论到代码落地的关键难点。压缩包共10个文件含3个TINY源程序t1.tny–t3.tny用于测试、核心C实现文件tinyscan.cpp、可执行程序tinyscan.exe、编译配置Makefile.win、开发环境配置tinyscan.dev、词法分析器布局定义tinyscan.layout、目标文件tinyscan.o及实验报告.docx覆盖编码、构建、测试、验证全流程。资源大小779KB轻量易部署适配Windows开发环境。已有1330人学习下载提供可直接运行的完整工程、清晰的状态转移逻辑实现、配套实验报告详解DFA设计思路与标记分类规则如TK_ID、TK_INT等枚举定义以及典型测试用例输出分析助力读者深入理解词法分析器构造本质与C工程化实践。1. 为什么写死正则还跑不出TINY的token——手工词法分析器不是“抄完regex就完事”的玄学工程你手头刚 unzip 出编译原理手工构造TINY语言的词法分析器.zip打开 README 看到“基于《编译原理》清华第三版第二章要求实现”心里一松“不就是写几个正则匹配关键字、标识符、数字嘛”——结果一跑if被切成了i和f123abc被当成一个 token 而不是报错/* comment */直接卡死在状态机里……这不是语法错误是词法层就崩了。TINY 语言虽小仅 15 个关键字、3 类字面量、4 种运算符但它的词法规则暗藏三重陷阱最长匹配原则被手动状态机误判、注释嵌套边界未显式建模、空格/换行/制表符的跳过时机错位。这不是 Pythonre.findall能兜住的场景而是必须用确定性有限自动机DFA思维在字符流上做不可回溯的单次扫描。本文带你从零手撸一个可调试、可断点、可输出 token 序列的 TINY 词法分析器——不依赖 Lex/Yacc不调用任何 parser generator只用 C 或 Python 原生控制流把教材第二章的“状态转换图”真正焊进内存。适合正在做编译原理实验课作业、想搞懂词法分析底层逻辑、或准备面试编译器岗的工程师。如果你的 zip 包里只有.c或.py源码没注释或者跑起来报Unexpected character at line 3 col 7却找不到哪一行——这篇就是你的后悔药。2. 从状态图到代码TINY 词法分析器的手工落地路径TINY 语言的词法规则严格定义在《编译原理》清华大学出版社第三版第二章附录中它支持if,then,else,while,do,end,repeat,until,read,write,integer,boolean,true,false,not共 15 个保留字标识符以字母开头、后接字母或数字长度不限整数为无符号十进制数字串布尔字面量仅true/false运算符包括,-,*,/,,!,,,,,:分隔符有;,,,(,),[,]还有单行//和多行/* ... */注释。这些规则不能靠re.compile(r\b(if|then|else)\b)简单覆盖——因为:必须优先于:和单独匹配必须优先于和而123abc中的123是合法整数但abc不是独立标识符整个字符串应报错。手工实现的本质是把教材图 2-6 的状态转换图State Transition Diagram翻译成可执行的状态机。我们不生成代码我们亲手写状态跳转逻辑。2.1 状态机设计为什么必须用 while switch 而不是 if-elif 链TINY 词法分析器最常被新手误用的写法是用一长串if token.startswith(if)... elif token.startswith(while)...——这根本不是词法分析这是“猜 token”。真正的手工 DFA 必须逐字符读取输入流每读一个字符就决定下一个状态直到进入接受态accept state或失败态error state。例如识别标识符初始态S0→ 读到字母 → 进入S1标识符中间态S1→ 读到字母/数字 → 保持S1S1→ 读到空白/运算符/分隔符 →回退一个字符输出当前已读字符串为IDtokenS1→ 读到 EOF → 直接接受输出ID注意“回退一个字符”这个动作它意味着你不能用for c in line这种不可回溯的遍历而必须用索引i或iter()send()控制读取位置。Python 中推荐用itertools.chain拼接所有行字符并带位置信息C 中则用fgetc()ungetc()组合。状态变量不能是布尔值必须是枚举型如enum { START, IN_ID, IN_NUM, IN_COMMENT, IN_ASSIGN }每个状态对应一组转移规则。# Python 手工 DFA 核心骨架非完整仅示意状态流转逻辑 def tokenize_tiny(source: str) - List[Tuple[str, str, int, int]]: tokens [] i 0 line, col 1, 1 while i len(source): c source[i] if c or c \t: col 1 i 1 continue elif c \n: line 1 col 1 i 1 continue elif c.isalpha(): # 进入标识符识别状态 start_i i while i len(source) and (source[i].isalnum() or source[i] _): i 1 ident source[start_i:i] # 关键查保留字表区分 ID 和 KW if ident in KEYWORDS: tokens.append((KEYWORD, ident, line, col)) else: tokens.append((ID, ident, line, col)) col len(ident) elif c.isdigit(): start_i i while i len(source) and source[i].isdigit(): i 1 num source[start_i:i] tokens.append((NUM, num, line, col)) col len(num) # 后续处理 :, /*, // 等需多字符前瞻的状态... else: # 单字符运算符和分隔符 if c in SINGLE_CHAR_TOKENS: tokens.append((SINGLE_CHAR_TOKENS[c], c, line, col)) col 1 i 1 else: raise SyntaxError(fUnexpected character {c} at line {line}, col {col}) return tokens提示这段代码只是骨架它尚未处理:,,!,/*,//等需要“读两个字符再决策”的情况。真实实现中elif c.isdigit()后必须插入对c /的分支并在其内判断下一个字符是否为*或/——这就是状态机的“前瞻一字符”逻辑也是手工实现区别于正则的关键。2.2 关键 token 的手工识别逻辑:、、/*怎么不冲突TINY 的运算符设计刻意制造了歧义:单独出现是语法错误但:是赋值单独是小于是小于等于是不等于教材中写作!但原始 TINY 定义用。这意味着你不能先匹配:再看下一个是而必须在读到:时立即进入新状态等待下一个字符确认。同理/可能是除号也可能是注释开始。标准做法是当读到/时不立即输出/token而是 peek 下一个字符若为*→ 进入IN_BLOCK_COMMENT状态直到匹配*/若为/→ 进入IN_LINE_COMMENT状态直到换行否则 → 输出DIVtoken且i 不加 1因为/已消费但下一个字符未读elif c /: if i 1 len(source): next_c source[i 1] if next_c *: # 进入块注释状态 i 2 # 跳过 /* start_line, start_col line, col while i len(source): if source[i] * and i 1 len(source) and source[i 1] /: i 2 # 跳过 */ break elif source[i] \n: line 1 col 1 else: col 1 i 1 else: raise SyntaxError(fUnterminated block comment starting at line {start_line}, col {start_col}) continue elif next_c /: # 进入行注释跳到换行或 EOF i 2 while i len(source) and source[i] ! \n: i 1 continue # 如果没有 next_c 或 next_c 不是 * 或 /则它是 DIV tokens.append((DIV, /, line, col)) col 1 i 1这段逻辑体现了手工词法分析器的“状态保持”本质/*的识别不是靠正则r/\*.*?\*/会贪婪匹配、无法定位错误位置而是用循环手动推进指针每一步都可打印调试信息。当你遇到/* comment */ nested /*这种非法嵌套时上述代码会在第一个/*开始后、遇到第二个/*时仍处于IN_BLOCK_COMMENT状态从而自然报错——而正则引擎根本不会告诉你嵌套在哪一层出问题。2.3 保留字与标识符的分离为什么不能用 dict 查表就完事很多初学者把KEYWORDS {if: IF, then: THEN, ...}当作最终方案然后if word in KEYWORDS: yield KEYWORDS[word]。这看似正确但忽略了 TINY 的一个硬性约束保留字必须是完整单词不能是标识符的前缀。例如integer是保留字但integer_part是合法标识符repeat是保留字但repeated不是。如果只做字符串包含判断integer_part.startswith(integer)会误判。正确做法是在识别出候选字符串后比如读到integer_part先检查它是否精确等于某个保留字只有完全相等才标记为 KW否则才是 ID。# ✅ 正确精确匹配 if ident if: tokens.append((IF, if, line, col)) elif ident then: tokens.append((THEN, then, line, col)) # ... 或更简洁地用 dict但 key 必须是完整字符串 elif ident in KEYWORDS_MAP: # KEYWORDS_MAP {if: IF, then: THEN, ...} tokens.append((KEYWORDS_MAP[ident], ident, line, col)) else: tokens.append((ID, ident, line, col))注意KEYWORDS_MAP的 keys 必须是小写字符串TINY 保留字全小写且不能有子串关系。教材明确列出 15 个不要自行添加and/or它们不是 TINY 关键字。这个 check 必须在标识符识别完成之后、输出 token 之前执行——早了没意义晚了就污染 token 流。3. 避坑手工实现 TINY 词法分析器的 4 个血泪经验手工词法分析器最大的陷阱是把“能跑通测试样例”当成“正确”。TINY 的测试集往往只覆盖 happy path而真实编译器要处理各种边界。以下是我在山科大编译原理实验课带学生 debug 时高频出现的 4 类翻车现场每一条都来自真实提交记录。3.1 现象123abc被识别为NUMID但教材要求报错原因在识别数字时代码写成while i len(source) and source[i].isdigit(): i 1然后直接切片source[start_i:i]作为 NUM。但123abc中123后是a它不是数字所以循环停止i指向a123被输出为 NUM后续a又被当作 ID 开头。这违反了 TINY 规则——数字字面量必须是纯数字序列后面紧跟非数字字符空格、运算符等才算合法。123abc是非法词法单元应报错。解决数字识别后检查下一个字符source[i]是否属于分隔符或运算符即in WHITESPACE OPERATORS DELIMITERS。如果不是则抛出LexicalError(Invalid number literal)。注意EOF 也算合法结束。3.2 现象a:b中的:被识别为ASSIGN但a b中的被识别为EQ而a b中间有空格却报错为UNEXPECTED 原因的识别逻辑写成 “如果当前是且下一个不是则输出EQ”。但a b中第一个后是空格满足条件输出EQ第二个前是空格也被当作独立EQ。问题在于本身不是运算符才是但 TINY 没有教材中是赋值!是不等于单独出现是语法错误。TINY 的只允许出现在:中单独是 lexical error。解决删除所有对单个的 accept 分支。必须和前面的:组成:或和前面的!组成!。单独直接报错。同理单独合法小于但单独也合法大于后跟是GE但后跟其他字符如字母是 error。3.3 现象多行注释/* line1\nline2 */被识别为两行但line2的列号从 1 开始计算导致后续 token 位置错乱原因在IN_BLOCK_COMMENT状态中遇到\n时只做了line 1但没重置col 1。结果line2的col延续了line1的末尾值比如 20导致*/的位置报告为line2, col20而非line2, col1。解决在IN_BLOCK_COMMENT循环内每次遇到\n必须同时执行line 1和col 1。更稳妥的做法是注释内的所有字符都不计入 token 位置计数只更新行号。因此col在注释内应始终设为 0 或忽略直到退出注释状态才恢复。3.4 现象输入文件末尾无换行符时最后一行 token 的列号比实际少 1原因代码中col的更新逻辑是 “每读一个非换行字符col 1”但文件末尾的最后一个字符后没有\n导致col停在len(last_line)而实际编辑器显示列号是从 1 开始len(abc)是 3但c在第 3 列没错。问题出在当i指向最后一个字符时col已加 1但循环结束后i已越界col多加了一次。解决将col更新移到字符消费之后。即先c source[i]再根据c类型决定是否col 1最后i 1。对于换行符col应置为 1新行开始而不是加 1。4. 输入预处理与错误定位让 lexer 不再是黑匣子一个工业级的词法分析器绝不只是返回[(type, value)]元组列表。它必须提供可复现的错误位置、可跳转的源码上下文、可配置的警告级别。TINY 实验虽然简单但养成这个习惯能让你在后续写 parser 时少 debug 80% 的问题。4.1 行列号的精确维护为什么line, col比offset更重要TINY 测试用例通常给出类似test.tny的文件并要求报错格式为Error at line 5, column 12: Unexpected character x。这意味着你的 lexer 必须在每个 token 输出时携带其起始行列号在报错时携带错误字符的行列号。offset字符偏移虽然精确但人类无法直观定位——没人能一眼看出 offset 127 对应第几行第几列。而line, col是编辑器原生坐标可直接 CtrlG 跳转。维护方法很简单初始化line 1, col 1每读一个字符若c \nline 1; col 1否则col 1但注意空格、制表符、换行符本身也要参与col计数因为它们占据源码位置。例如int a;中a的列号是 5i1,n2,t3, 4,a5而不是跳过空格后的 2。教材示例错误信息都带列号必须严格对齐。4.2 错误恢复策略报错后是 abort 还是 skip to next lineTINY 实验通常不要求错误恢复recover但为了调试方便建议实现最小 recover当遇到非法字符如,$输出ERRORtoken 并跳过该字符继续扫描。这样你能看到后续所有错误而不是扫到第一个就 halt。else: # 非法字符 tokens.append((ERROR, fUnexpected character {c}, line, col)) col 1 i 1注意ERRORtoken 不应进入 parser但 lexer 层要把它吐出来方便你验证 lexer 是否覆盖所有 case。真正的 parser 会忽略ERROR或报 fatal error。4.3 测试驱动开发用 TINY 官方测试集验证 lexerTINY 语言有配套的参考编译器tiny compiler其 test 目录下有factorial.tny,fibonacci.tny等样例。你可以用 diff 工具对比你的 lexer 输出和参考 lexer 的 token 序列# 假设你的 lexer 输出为 token.txt参考输出为 ref_tokens.txt python lexer.py tests/factorial.tny token.txt diff token.txt tests/ref/factorial.tokens关键不是完全一致token type 名称可能不同而是token 数量相同每个 token 的value和位置(line, col)一致错误 token 的位置和 message 一致我一般会写一个assert_token_stream()函数把预期 token 序列 hardcode 成 list of tuple然后逐个 assertdef test_factorial(): with open(tests/factorial.tny) as f: src f.read() tokens tokenize_tiny(src) expected [ (KEYWORD, program, 1, 1), (ID, factorial, 1, 9), (SEMI, ;, 1, 19), # ... ] assert len(tokens) len(expected) for i, (t, exp) in enumerate(zip(tokens, expected)): assert t[0] exp[0], fToken {i} type mismatch: got {t[0]}, expected {exp[0]} assert t[1] exp[1], fToken {i} value mismatch assert t[2:] exp[2:], fToken {i} position mismatch这种测试能立刻暴露行列号计算错误、保留字漏判、注释吞掉换行等问题。5. 进阶技巧用 lexer 生成 AST 节点不先让它能被 parser 无缝消费很多人做完 lexer 就停了觉得“token 流有了parser 自然就能写了”。但现实是parser 的健壮性一半取决于 lexer 输出的 token 质量。一个设计不良的 lexer 会让 parser 写得极其痛苦。这里分享三个让 lexer 和 parser 无缝衔接的实战技巧。5.1 Token 类型的命名规范为什么ASSIGN比COLON_EQ更好TINY 的:是赋值运算符语义是“把右边的值存到左边的变量”。在 parser 中你最终要生成AssignNode(left, right)。如果 lexer 输出(COLON_EQ, :)parser 就得额外映射if token.type COLON_EQ: node AssignNode(...). 而如果 lexer 直接输出(ASSIGN, :)parser 就能直呼其名。命名应反映语义而非字面形状。同理!→NEnot equal不是BANG_EQ→LEless than or equal不是LT_EQ/*→ 不输出 token只跳过//同理这样 parser 的match(ASSIGN)就非常自然不用查表转换。5.2 位置信息的结构化封装别传四个参数用 dataclass把line, col作为四个独立参数传给 parser很快就会混乱。Python 中用dataclass封装位置from dataclasses import dataclass dataclass class Position: line: int col: int dataclass class Token: type: str value: str pos: Position # lexer 返回 [Token(...), ...] # parser 拿到 token.pos.line 就能打印错误C 中可用 structtypedef struct { int line; int col; } Position; typedef struct { char *type; char *value; Position pos; } Token;这样 parser 的错误报告函数可以统一写成fprintf(stderr, Error at %d:%d: %s\n, tok.pos.line, tok.pos.col, msg);无需每次 unpack。5.3 EOF 的显式 token 化为什么None比while not eof更安全很多 lexer 实现用while i len(source)控制循环结束时隐式 EOF。但 parser 需要明确知道“输入结束了”。更好的做法是lexer 最后主动 append 一个(EOF, , pos)token。这样 parser 的主循环可以写成while token.type ! EOF: # parse one construct token next_token()而不是用try/except或 flag 变量。EOFtoken 还能携带结束位置最后一行的col1用于报告 “unexpected end of file”。我的习惯是lexer 的入口函数永远返回List[Token]且保证最后一个 token 是EOF。哪怕输入为空也返回[Token(EOF, , Position(1,1))]。这让我在写 parser 时从不担心边界条件——因为EOF是一个 first-class citizen不是异常。手工构造 TINY 词法分析器不是为了替代 Lex而是为了亲手触摸编译器的第一道门槛。当你在 gdb 里 step into 每一个字符的判断看着i指针在:上停顿、在/*里深入、在123abc前戛然而止报错——那一刻编译原理不再是书上的状态图而是你键盘敲出的每一行 if 和 while。这门课的价值从来不在写出完美代码而在亲手把抽象规则焊进具体字节流的过程里。希望帮到你。本文还有配套的精品资源点击获取