手工构造TINY语言词法分析器：从字符扫描到Token流

简介：这份面向编译原理课程学习者的TINY语言词法分析器实现资料，围绕手工构造扫描器这一经典实验展开，适合正在学习词法分析、需要完成课程设计，或想弄懂确定有限状态自动机（DFA）如何应用到实际代码中的学生与自学者。资源包共10个文件、约779KB，其中C++源文件与编译生成的目标文件构成核心实现，三个.tny测试用例用于验证词法规则，实验报告文档记录了DFA设计过程、关键代码解释及结果分析；此外还有Dev-C++工程配置与可执行文件，可直接运行以观察分词输出。目前已有1332人学习下载。读者能从中获得一条完整实现链路：从词法规则到状态转移函数，再到标记（token）结构体定义；还能理解标识符、整数常量与运算符的识别边界，并借助测试用例和报告中记录的问题，对照排查自己的写法，减少在状态设计与数据结构定义上反复试错。

1. TINY 语言词法分析器：为什么值得从 zip 里拆出来跑一遍

把一个 C/C++ 写的 TINY 语言词法分析器从压缩包里拆出来跑通，价值不在交作业那一刻，而在你能亲眼看到getChar到 token 之间的每一步。多数讲词法分析的资料停在正则表达式和 DFA 图上，真到手工构造这一层，字符怎么读、怎么回退、注释怎么跳、行号怎么记，全靠几十行代码细节撑着，翻车也基本翻在这些地方。这份资源给的就是这几十行：不依赖 Lex/Flex 的扫描器，输入 TINY 源码，输出带类型、词素和行号的 token 流。

它适合三类人：正在做编译原理课程设计、需要一个能改能调的手工扫描器骨架的；写惯了正则表达式、想回头补一遍底层字符级扫描逻辑的 C/C++ 从业者；以及想给自研小语言快速搭一个前端入口的。读懂它不需要编译原理满分，但需要你能看懂指针、switch和状态迁移。

2. 规则先行：把 TINY 词法表拆成可编码的状态机

写扫描器最容易犯的错是打开编辑器就开始switch(c)，写到哪里补到哪里，最后代码能跑，但边界全糊。手工构造的前提是把词法规则先整理成一张能逐行核对的表，代码只是这张表的翻译。TINY 语言的词法规模很小，小到刚好适合拿来练手：8 个保留字、5 类运算符、若干分隔符、标识符、无符号整数、花括号注释和空白。规则越少，越要一次定清楚，否则后面每加一个符号都要回头重构。

2.1 关键字与标识符：先扫完整词素再查表

TINY 的保留字是if、then、else、end、repeat、until、read、write。新手最常见的写法是在主循环里给首字符i开一个分支，再逐个getChar比对f，匹配失败再想办法把字符吐回去。这种写法的问题在于：ifx会被误判成if加x，而按最长匹配原则，ifx是一个合法标识符。一旦为每个关键字写一套前瞻逻辑，代码里会塞满ungetChar，改一个关键字要动三处，调试时连自己都记不清哪个字符在哪个位置被退回。

我一般用的方案是倒过来：所有以字母开头的词素，一律先按标识符规则完整扫出来，扫到非字母非数字为止，再拿这个词素去保留字表里查一次。查中就是关键字，查不中就是标识符。这样主循环里只有一条分支，保留字增删只改表，不动控制流。

/* 保留字表：词素 -> token 类型，顺序无关，查表用线性比较即可 */ static const struct { const char *word; TokenType type; } reserved[] = { {"if", T_IF}, {"then", T_THEN}, {"else", T_ELSE}, {"end", T_END}, {"repeat", T_REPEAT}, {"until", T_UNTIL}, {"read", T_READ}, {"write", T_WRITE} }; static TokenType lookupReserved(const char *s) { size_t i; for (i = 0; i < sizeof(reserved) / sizeof(reserved[0]); ++i) { if (strcmp(s, reserved[i].word) == 0) return reserved[i].type; } return T_ID; /* 没命中就是普通标识符 */ }

这段代码没有花哨的地方，关键是调用时机：必须在标识符已经完整读入lexeme之后调用。表用静态数组而不是哈希，8 个元素线性比较的开销可以忽略，换来的是可读性和可调试性。strcmp是大小写敏感的，所以If会被识别成标识符而不是关键字，这和 TINY 的规范一致；如果你的课程要求关键字大小写不敏感，只能在查表前先做一次归一化，别去改比较函数，否则If和IF这类词素的原始拼写会被破坏，后续报错信息就对不上源码了。

2.2 数字、运算符与注释：三类必须前瞻的边界

数字的处理看起来最简单，实际上藏着两个坑。第一个是前导零，007在 TINY 里通常按十进制 7 处理，扫描阶段不校验数值合法性，交给后续阶段；第二个是数字后紧跟字母，比如12ab。如果扫描器只用while(isdigit(c))收尾，12ab会被切成NUM(12)和ID(ab)两个 token，语法分析器会在一个完全无关的位置报错，排查成本极高。合理做法是在数字扫描结束后再看一眼下一个字符，如果是字母或下划线，就把整个非法词素吞掉，产出一个T_ERROR，把错误定位在这一行。

运算符里唯一需要前瞻的是:和:=。单独的:在 TINY 里用于变量声明，:=是赋值，两者共享首字符，必须读第二个字符才能定。<、=、+、-、*、/、(、)、;、,都是单字符 token，读完直接返回，不需要回退。这里有个顺手能省掉的复杂度：不要为了“将来可能扩展”提前把<=、>=的逻辑写进去，TINY 没有这些符号，多写的分支只会让最长匹配的判断条件变复杂。

注释是{到}，不嵌套、可以跨行、可以出现在任何空白能出现的位置。跨行意味着注释内部的换行必须照样计入行号，否则注释后面的第一行代码行号就错了。这一点在实现上不能偷懒：不能在跳注释的循环里绕开getChar直接fgetc，那样行号计数器就漏了。正确做法是让注释跳过逻辑复用同一个getChar，让行号在字符读取层统一维护。

2.3 把规则落成一张可核对的 token 表

下面这张表是后面所有代码的验收标准。写完扫描器，拿它逐行对一遍，比拿十几个测试用例去猜有效率得多。

表里最容易看漏的是最后两行。EOF 必须变成一个显式 token 返回给调用方，而不是让主循环自己break，否则语法分析器拿不到结束信号；注释不产出 token 但必须处理未闭合的情况，这在表里写的是“读到}或 EOF”，意味着 EOF 也是一条正常出口，只是出口处要报错。这两条在代码里各占三五行，但漏掉任何一条，扫描器都会在某个输入上卡死或死循环。

3. 手工构造扫描器：主循环、缓冲与 token 结构

规则定完之后，代码结构其实已经被决定了：一个字符读取层负责缓冲和行号，一个主循环负责跳过空白和注释，一组分支负责按首字符分派，一个 token 结构负责把结果交给调用方。这个结构不是唯一的，但对 TINY 这种规模的语言足够用，而且每一层都能单独测试。

3.1 字符级读取：单字符回退缓冲的写法

扫描器只需要回退一个字符，这是由最长匹配的性质决定的：任何时刻你多读了一个字符，最多退一个。所以不必实现完整的缓冲区，一个savedChar加一个标志位就够。麻烦在于行号：如果getChar读到换行时把行号加一，那么回退换行时必须把行号减回去，否则一个被回退的换行会让后面所有行号偏一位。

static FILE *src; static int lineNo = 1; static int hasSaved = 0; static int savedChar; /* 统一的字符入口：行号在这里维护，所有路径都必须走这里 */ int getChar(void) { int c; if (hasSaved) { hasSaved = 0; return savedChar; } c = fgetc(src); if (c == '\n') ++lineNo; return c; } /* 只允许回退一个字符；EOF 不允许回退 */ void ungetChar(int c) { if (c == EOF) return; if (c == '\n') --lineNo; /* 行号必须跟着回退，否则后续定位全偏 */ savedChar = c; hasSaved = 1; }

getChar里把行号自增放在fgetc之后、返回之前，保证每个换行只被计一次。ungetChar里对\n减行号这一句是整段代码里最容易被删掉的，删掉之后程序照样能跑，只是所有报错行号会从第一个被回退的换行之后开始整体偏移，而且偏移量随输入变化，非常难查。EOF直接返回不回退，是因为EOF本身不是真实字符，回退它会让下一次getChar返回一个假的-1，后面的isalpha(EOF)行为未定义。这一层还有一个隐含约束：hasSaved只能存一个字符，所以任何地方连续调用两次ungetChar，第一次的字符就被覆盖了。代码里要保证不出现这种调用，或者在调试版本加一个断言。

3.2 状态迁移与最长匹配：一次 switch 走完一个 token

主循环分三段：跳过空白与注释、处理 EOF、按首字符分派。分派用if判断字母和数字，剩下的交给switch。这样写的原因是字母和数字的处理逻辑较长（要循环收词素），放在switch的case里会显得很挤，而且default分支要和它们分开处理非法字符。

Token getToken(void) { Token t; int c, n; t.lexeme[0] = '\0'; t.line = lineNo; /* 第一段：跳过空白和注释，注释里出现换行由 getChar 计行号 */ for (;;) { c = getChar(); if (c == ' ' || c == '\t' || c == '\r' || c == '\n') continue; if (c == '{') { int startLine = lineNo; do { c = getChar(); } while (c != '}' && c != EOF); if (c == EOF) { t.type = T_ERROR; t.line = startLine; snprintf(t.lexeme, sizeof(t.lexeme), "unclosed comment"); return t; } continue; } break; } t.line = lineNo; /* 第二段：EOF 必须变成一个显式 token */ if (c == EOF) { t.type = T_ENDFILE; return t; } /* 第三段：标识符与关键字 */ if (isalpha(c) || c == '_') { n = 0; t.lexeme[n++] = (char)c; while (isalnum(c = getChar()) || c == '_') { if (n < (int)sizeof(t.lexeme) - 1) t.lexeme[n++] = (char)c; } ungetChar(c); /* 多读的那个字符退回去 */ t.lexeme[n] = '\0'; t.type = lookupReserved(t.lexeme); return t; } /* 数字：扫完后检查是否紧跟字母，防止 12ab 被切成两个 token */ if (isdigit(c)) { n = 0; t.lexeme[n++] = (char)c; while (isdigit(c = getChar())) { if (n < (int)sizeof(t.lexeme) - 1) t.lexeme[n++] = (char)c; } if (isalpha(c) || c == '_') { while (isalnum(c) || c == '_') c = getChar(); ungetChar(c); t.lexeme[n] = '\0'; t.type = T_ERROR; /* 非法数字，整段吞掉 */ return t; } ungetChar(c); t.lexeme[n] = '\0'; t.type = T_NUM; return t; } /* 第四段：运算符与分隔符，只有 := 需要前瞻 */ switch (c) { case ':': if ((c = getChar()) == '=') { t.type = T_ASSIGN; strcpy(t.lexeme, ":="); return t; } ungetChar(c); t.type = T_COLON; strcpy(t.lexeme, ":"); return t; case '=': t.type = T_EQ; strcpy(t.lexeme, "="); return t; case '<': t.type = T_LT; strcpy(t.lexeme, "<"); return t; case '+': t.type = T_PLUS; strcpy(t.lexeme, "+"); return t; case '-': t.type = T_MINUS; strcpy(t.lexeme, "-"); return t; case '*': t.type = T_TIMES; strcpy(t.lexeme, "*"); return t; case '/': t.type = T_OVER; strcpy(t.lexeme, "/"); return t; case '(': t.type = T_LPAREN; strcpy(t.lexeme, "("); return t; case ')': t.type = T_RPAREN; strcpy(t.lexeme, ")"); return t; case ';': t.type = T_SEMI; strcpy(t.lexeme, ";"); return t; case ',': t.type = T_COMMA; strcpy(t.lexeme, ","); return t; default: t.type = T_ERROR; t.lexeme[0] = (char)c; t.lexeme[1] = '\0'; return t; } }

几处参数和逻辑值得单独说。t.line在跳过空白前先赋一次，跳完注释后再赋一次，目的是让未闭合注释的报错定位到注释起始行而不是文件末尾行，这个细节如果不做，错误信息会指到输入的最后一行，等于没定位。标识符循环里的n < sizeof(t.lexeme) - 1是防止超长标识符写爆固定缓冲区；超长部分被丢弃但不影响 token 类型判断，因为查表用的是被截断后的前缀，极端情况下if后面跟 200 个字母会被误判成关键字。要彻底解决只能改成动态分配或先量长度再分配，课程设计级别用固定 64 字节足够，但心里要清楚这个上限存在。

数字分支里的while (isalnum(c) || c == '_') c = getChar();是一个“吞掉整段非法词素”的循环，它保证12ab3x只会产出一个错误 token，而不是连续产出一串错误。这一句的存在直接决定了错误恢复的质量，后面避坑章节还会提到它。:=的前瞻是唯一需要ungetChar的运算符场景，回退的字符是普通字符，不涉及行号，所以简单退回即可。

3.3 token 结构与输出格式：让下游能直接吃

token 结构不用复杂，三个字段就够：类型、词素、行号。词素用定长数组还是指针取决于 token 的生命周期；如果扫描器和语法分析器在同一进程里、token 用完即弃，定长数组最省事，不存在谁负责释放的问题。

typedef enum { T_IF, T_THEN, T_ELSE, T_END, T_REPEAT, T_UNTIL, T_READ, T_WRITE, T_ID, T_NUM, T_ASSIGN, T_EQ, T_LT, T_PLUS, T_MINUS, T_TIMES, T_OVER, T_LPAREN, T_RPAREN, T_SEMI, T_COMMA, T_COLON, T_ENDFILE, T_ERROR } TokenType; typedef struct { TokenType type; char lexeme[64]; int line; } Token; /* 调试输出：类型名 + 词素 + 行号，三列对齐便于肉眼核对 */ static const char *typeName(TokenType t) { static const char *names[] = { "IF","THEN","ELSE","END","REPEAT","UNTIL","READ","WRITE", "ID","NUM","ASSIGN","EQ","LT","PLUS","MINUS","TIMES","OVER", "LPAREN","RPAREN","SEMI","COMMA","COLON","ENDFILE","ERROR" }; return names[t]; } void dumpToken(const Token *t) { printf("%-8s %-16s line %d\n", typeName(t->type), t->lexeme, t->line); }

类型名数组的顺序必须和枚举严格一致，这是这类代码里最典型的隐式耦合。工程上更稳的做法是用 X-Macro 把枚举和名字表写在一处，但对一份教学资源来说，保持两个列表并排在文件里、改的时候一起改，是可接受的折中。真正要避免的是把typeName写成switch返回字符串字面量，那样每加一个 token 要改两个函数，反而更容易漏。输出格式选三列定宽，是为了让人一眼扫出词素和行号是否对得上，机器解析反而不是这个阶段的目标。

4. 编译与用例验证：把输出跑成可核对的清单

代码写完不等于能用，词法分析器的验证方式是拿输入喂进去、拿输出跟手算结果对。这一步不能省，因为扫描器的 bug 大多不表现为崩溃，而是表现为“多了一个 token”“少了一个字符”“行号差一”，只有逐行对照才能发现。

4.1 构建方式与目录约定

压缩包解出来之后，先看清楚文件组织再动手编译。常见的手工构造扫描器资源大致是这几个文件：token 定义头文件、扫描器实现、主程序入口、若干.tiny测试输入。构建命令按单文件编译即可，不需要 Makefile 也能跑，但如果要反复改代码，写个三行的 Makefile 会省很多事。

# 目录假设：src/ 下放 .c 与 .h，tests/ 下放 .tiny 输入 gcc -std=c99 -Wall -Wextra -g -O0 \ src/scanner.c src/main.c \ -o tiny_lexer # 用法：把源文件名作为唯一参数传入 ./tiny_lexer tests/fact.tiny

-std=c99是为了snprintf和声明与语句混写；-Wall -Wextra必须开，手工扫描器里最常见的“变量未使用”“隐式截断”都能被它揪出来；-O0 -g是为了调试时变量不被优化掉，等逻辑稳定了再去掉。用gcc还是g++取决于源码里有没有用到 C++ 特性，纯 C 写的扫描器用gcc编译更快，混进.cpp之后注意extern "C"的问题。

如果编译报undefined reference to getToken，先检查头文件里有没有声明、实现文件有没有被加进命令行；如果报重复定义，多半是头文件里写了函数体而没有 include guard。这两类错误在拼装他人代码时出现频率最高，跟扫描逻辑本身无关，看到时不要往算法上想。

4.2 三组输入：正常、边界、错误

测试输入不要一上来就写复杂程序，按三档递进。第一档是覆盖全部 token 类型的正常输入，目的是确认每条分支都能走到；第二档是边界输入，专挑最长匹配和注释跨行；第三档是错误输入，看扫描器是报错还是卡死。

{ 正常用例：覆盖关键字、标识符、数字、运算符、注释 } read n; fact := 1; repeat fact := fact * n; n := n - 1 until n = 0; write fact end

这组输入跑完，期望的 token 序列里应该出现READ、ID(n)、SEMI、ID(fact)、ASSIGN、NUM(1)、SEMI、REPEAT、UNTIL、EQ、WRITE、END、ENDFILE。对的时候重点看三处：:=是不是被识别成一个ASSIGN而不是COLON加EQ；n - 1里的-是不是独立的MINUS；注释所在行的下一行代码行号是不是正确递增。

第二组边界输入专门压最长匹配和注释：

{ 边界用例：注释跨行、标识符包含关键字前缀 } ifx := 100; if ifx < 200 then { 这一行是注释 跨了两行 } write ifx end

这组的关键在ifx。按最长匹配它应该是一个ID，整段输出里不能出现IF紧跟ID(x)的切分。如果扫描器先比关键字再收标识符，这里一定翻车，而翻车后的表现是语法分析阶段报“意外的标识符”，很难反向定位到扫描器。注释跨行的验证点是write ifx这一行的行号，它应该等于注释结束行加一。

第三组错误输入：

x := 12ab + 3; y := (a + b; { 注释没有闭合

期望行为是：第一行产出ERROR（词素为12ab），扫描继续；第二行正常产出 token，括号不匹配是语法阶段的事，扫描器不管；第三行注释一直读到 EOF，产出ERROR并把行号定位到注释起始行。三行错误如果任何一行导致程序挂起或退出，说明对应的保护分支没写。

4.3 输出核对：把 token 序列当验收单

核对方式建议手工列一遍期望序列，再跟程序输出做逐行 diff，而不是扫一眼“看起来差不多”。定宽输出在这里就体现出价值了：两列并排，哪一行错位一眼可见。

表里第三行和第五行最容易在“看起来跑通了”的时候被漏掉。注释单独一行时，如果跳注释的循环直接返回、没有继续外层for，那么注释后面的空白可能被当成一个空 token；文件末尾没有换行时，getChar返回 EOF，ungetChar直接返回不缓存，主循环下一次再读还是 EOF，理论上不会死循环，但如果 EOF 分支写成了continue而不是return，就会原地打转。这两条都可以在十秒内验证，但很多人写完就直接上大输入，反而把简单问题拖成了玄学。

5. 避坑排查：五个高频翻车点

扫描器的 bug 有两个特点：一是多数不崩溃，只产出一份“看起来能解析”的错误 token 流；二是症状出现在下游。下面五条是手工构造 TINY 扫描器时最常撞上的，按“现象 → 原因 → 解决”记，比背原理管用。

5.1 注释、换行与 EOF 的三处边界

现象一：程序在某个输入上卡住，CPU 占满，不输出任何 token。原因基本只有一个：跳注释的循环写成了while (c != '}') c = getChar();，输入里注释没闭合，c永远是EOF，循环永不退出。解决是把循环条件改成c != '}' && c != EOF，出循环后单独判断c == EOF，产出T_ERROR并把行号设为注释起始行。这个分支不写，任何一次手误漏掉右花括号都会让扫描器挂死，调试时还以为是自己逻辑绕住了。

现象二：注释之后的所有报错行号整体偏大。原因是跳注释时绕开了统一的getChar，直接用了fgetc，注释内部的换行没有被计数。另一个变体是ungetChar('\n')时没有把行号减回去，导致每一处回退换行都多算一行。解决办法是把行号维护收敛到getChar/ungetChar这一对函数里，任何需要读字符的地方都必须经过它们，不允许出现第二个fgetc调用点。这条约束写进代码注释，比事后排查省事得多。

现象三：最后一行的 token 丢失，或者末尾多出一个空 token。原因是 EOF 的处理位置不对。如果 EOF 判断放在跳过空白之后、分派之前，但跳注释的循环里也能返回 EOF，两条路径就可能一条返回ENDFILE、一条返回ERROR。统一的做法是：整个getToken里只有一个地方产出T_ENDFILE，且它必须在跳过空白与注释之后。这样无论输入以换行结尾、以注释结尾还是以普通 token 结尾，结束信号都唯一。

5.2 最长匹配与回退的误用

现象四：12ab被识别成数字加标识符，语法分析器在后续行报“意外的标识符”。原因在数字分支只写了while (isdigit(...))，用完就返回，没检查紧跟的字符。这个 bug 的隐蔽之处在于它不报错，只是切分错了，错误被推迟到语法阶段。解决是在数字循环结束后补一个isalpha(c) || c == '_'的判断，命中就把剩余字母数字全部吞掉，产出T_ERROR并把整段词素放进lexeme，让报错信息直接指向12ab本身。吞掉剩余字符这一步不能省，只报错不吞会导致a、b各自再变成一个标识符，错误数量翻倍。

现象五：:=偶尔被拆成:和=，而且只在特定输入下出现。原因通常是ungetChar被连续调用了两次，第一次缓存的字符被第二次覆盖，导致下一次getChar读到的不是预期的那个。这类 bug 只在包含连续回退的路径上出现，比如标识符扫描完回退一个字符、紧接着运算符分支又回退一次，单看每个函数都对，合起来就错。解决办法是加一个调试断言：在ungetChar开头检查if (hasSaved) abort();，跑完全部测试用例，只要断言不触发，就说明没有双重回退。这个断言在发布版本里可以去掉，开发阶段建议一直留着。

6. 进阶：把 switch 扫描器改成表驱动

手写switch的扫描器可读性好，但每加一个 token 都要动控制流，改到第三四次就开始心虚。想再往前走一步，可以把字符分派改成表驱动：用一张二维表描述“当前状态 + 输入字符类别 → 下一个状态”，扫描循环只负责查表和执行动作。TINY 的状态数很少，改造量不大，但能让你看清 DFA 和代码之间的对应关系。

表驱动版的循环骨架大致是这样，状态机每走一步只做两件事：查表得到动作、按动作决定是继续读字符还是产出 token。查表函数把isalpha、isdigit这类判断收敛成字符类别编号，扫描循环里就不再出现具体的字符常量。

/* 表驱动骨架：状态迁移与动作分离，新增 token 只改表 */ typedef enum { S_START, S_ID, S_NUM, S_COLON, S_DONE, S_ERR } State; static Token driveScanner(void) { State st = S_START; Token t = { T_ERROR, "", lineNo }; int n = 0; while (st != S_DONE && st != S_ERR) { int c = getChar(); int cls = charClass(c); /* 字母/数字/冒号/其他/空白/EOF */ Action act = table[st][cls]; /* 查表：迁移或产出 */ st = applyAction(act, c, &t, &n); } return t; }

真正落地时，applyAction里要处理“回退一个字符”和“写词素”两个副作用，这两件事是表驱动写法里唯一不干净的地方，也是很多人改到一半放弃的原因。我的建议是：如果这份扫描器只是课程设计交付物，switch版本足够，别为了形式上的优雅引入一层间接；如果后面还要接语法分析器、要反复加 token，那这次改造值得做，因为表驱动版本加一个关键字只需要在表里加一行，不用碰任何分支。

最后说一个我自己的习惯。每次改完扫描器，不管改的是注释跳过还是数字分支，我都会强制跑一遍三组用例：一组全覆盖、一组ifx和跨行注释、一组12ab加未闭合注释，并且要求输出里ENDFILE恰好出现一次、行号单调不减。这套动作花不到两分钟，但替我挡掉过好几次“改一处崩三处”的返工。词法分析器是整个前端里最容易被低估的一层，它错一个字符，后面所有阶段的报错都会指向错误的位置。希望帮到你。

本文还有配套的精品资源，点击获取