TINY语言词法分析器：DFA最长匹配与Token设计-北京尧图网络

简介面向编译原理课程学习与课程设计场景这份资料围绕手工构造TINY语言词法分析器展开适合具备C/C基础、正在理解扫描器与确定有限状态自动机DFA的本科生或自学者用于完成从词法规则梳理到标记识别的实验任务。压缩包共10个文件、约779KB包含C源代码、TINY测试用例、可执行与工程配置文件以及一份实验报告文档基本覆盖编写、编译运行、样例验证和实验总结环节。已有1333人学习说明其在同类课程实验中具有一定参考价值。读者可据此对照DFA状态转移设计、关键字与标识符等token划分、枚举与结构体等数据组织方式并结合测试用例和报告中的验证思路排查扫描结果快速搭建可运行的词法分析器小工程。1. 词法分析器难点不在认词而在于何时停止读取很多人对 TINY 语言词法分析器的第一印象是写一个很大的 if-else 按字符分类。真正动手才会发现难以处理的是“在哪里停止读取”读到:时下一个字符可能是读到时下一个字符可能是或读到123后面紧跟一个字母又该怎么算。手工构造的 C/C 词法分析器的技巧几乎全部集中在最长匹配、超前读一个字符、读多之后怎么退回去这三件事上。把这三件事理顺DFA、状态机、符号表这些名词才会从玄学变成可以推导的工程。2. Token 的约定词法分析器应当返回什么2.1 返回值不能只用一个字符串第一版 getToken 返回char *是最常见的做法也是最容易返工的做法。语法分析器每判断一次都要拿这个字符串跟八个保留字逐一比对更要紧的是类型信息丢了——“if” 到底是保留字还是用户定义的标识符只有词法分析器知道因为只有它在读源码的那一刻知道这个词有没有提前登记、有没有落在保留字表里。把定性判断推给语法分析器等于让下游重复做一遍上游已经做过的事。合理的做法是词法分析器对外只返回结构化的 token 记录类型在离开getToken()之前就确定下来下游只做 switch 分派不再做字符串比较。/* TINY 的 token 类型一个不多一个不少 */ typedef enum { ENDFILE, ERROR, /* 两个哨兵 */ IF, THEN, ELSE, END, REPEAT, UNTIL, READ, WRITE, /* 8 个保留字 */ ID, NUM, /* 标识符、整数常量 */ ASSIGN, EQ, LT, GT, /* : */ PLUS, MINUS, TIMES, OVER, /* - * / */ LPAREN, RPAREN, SEMI, COMMA /* ( ) ; , */ } TokenType; #define MAXTOKENLEN 64 typedef struct { TokenType tokenType; /* 定性结果下游只看这个字段 */ char lexeme[MAXTOKENLEN 1];/* 原始词素报错和调试时才用 */ int lineNo; /* token 的**起始**行不是结束行 */ int numValue; /* 仅 NUM 有效避免下游重复 atoi */ } Token;MAXTOKENLEN是硬性上限不是建议手工词法分析器被超长输入打穿几乎都是漏了这个边界。numValue这个字段属于可选项有些实现选择在语法分析阶段再做atoi好处是 token 结构更小坏处是同一个数字要扫两遍。我一般倾向于在词法层算掉因为此时字符串还在缓存里顺手的成本几乎为零。2.2 行号为什么必须在这一层记整条编译流水线上只有词法分析器逐字符看到过\n。语法分析器拿到的 token 只知道自己是第几个不知道在第几行语义分析阶段想报“第 12 行的变量未声明”这个 12 只能由前端传下来。一旦词法层没记后面任何阶段都补不回来——这是不可逆的信息丢失。真正容易出错的是取值时机。如果在外层循环开头就把tk.lineNo lineNo快照下来那么跳过大段空白或跨行注释之后这个快照指向的就是上一个 token 的结束位置报错会整体偏移。稳妥的做法是等第一个真正进入词素的字符出现时再快照这也是后面 getToken 里if (len 0) tk.lineNo lineNo;那一行的全部意义。2.3 一个最小完备的 token 集合token 集合的设计标准只有一条语法分析器做一次分派时需要的区分度一个不能少一个也不多加。TINY 的和:必须分成两个类型因为它们在语法上处于完全不同的位置而和-如果语义完全对称硬拆成两个类型也不会带来额外信息。类别取值说明保留字if then else end repeat until read write不可作为标识符标识符ID首次出现时登记进符号表常量NUM只支持十进制非负整数运算符:-*/最长匹配优先分隔符();,单字符无需前瞻哨兵ENDFILE ERROR控制流与错误通道ERROR作为合法枚举值存在而不是抛异常是个容易被忽略的设计词法错误不该让整次编译立刻终止。把错误字符包成一个 ERROR token 返回让上层决定是跳过、恢复还是中断一次编译就能报出尽可能多的错。反过来如果遇到非法字符就exit(1)用户改一个错、重编一次、再看到下一个错体验会急剧变差。3. DFA 与最长匹配状态机怎么把字符流切成 token3.1 五个状态够不够TINY 的词法用五个工作状态加一个终止状态就能覆盖START是每次切词的起点INNUM累积数字INID累积标识符INCOMMENT吞掉花括号注释INASSIGN处理冒号后可能跟等号的两字符运算符DONE表示这个词已经切完。INASSIGN单独存在的唯一理由就是最长匹配。读到:时并不能确定这个 token 是:还是一个孤立的冒号必须再读一个字符才能定读进来的如果不是这个字符属于下一个 token得还回去。所以这个状态的存在本质上是在说“我还没有足够的证据下结论”。3.2 从状态转换图到表必须补一张 consume 表教科书上的状态转换图画得很干净圆是状态箭头是字符。但图里从来不标一件事——这条边上读到的字符到底算不算当前 token 的一部分。人看图时会自动补上这个判断写成代码时如果还用一张二维表这个信息就丢了。这是手工写词法分析器最常见的翻车点表填得漂漂亮亮跑起来:被切成:和123abc被当成一个非法整体。补一张与状态表同形的 consume 表问题一次解决。/* 把 256 种字符压成 8 类状态表只需要 8 列 */ enum CharClass { CC_WS, CC_DIGIT, CC_ALPHA, CC_COLON, CC_EQ, CC_LBRACE, CC_RBRACE, CC_OTHER, CC_NUM }; /* 六种状态与 CharClass 的列一一对应 */ typedef enum { START, INASSIGN, INCOMMENT, INNUM, INID, DONE, ST_NUM } StateType; static const StateType nextState[ST_NUM][CC_NUM] { /* WS DIGIT ALPHA COLON EQ LBRACE RBRACE OTHER */ /* START */ { START, INNUM, INID, INASSIGN, DONE, INCOMMENT, DONE, DONE }, /* INASSIGN */ { DONE, DONE, DONE, DONE, DONE, DONE, DONE, DONE }, /* INCOMMENT*/ { INCOMMENT, INCOMMENT, INCOMMENT, INCOMMENT, INCOMMENT, INCOMMENT, START, INCOMMENT }, /* INNUM */ { DONE, INNUM, DONE, DONE, DONE, DONE, DONE, DONE }, /* INID */ { DONE, INID, INID, DONE, DONE, DONE, DONE, DONE }, /* DONE */ { DONE, DONE, DONE, DONE, DONE, DONE, DONE, DONE } }; /* 1 这个字符属于当前 token吃掉0 属于下一个 token必须回退 */ static const int consumeTable[ST_NUM][CC_NUM] { /* WS DIGIT ALPHA COLON EQ LBRACE RBRACE OTHER */ /* START */ { 1, 1, 1, 1, 1, 1, 1, 1 }, /* INASSIGN */ { 0, 0, 0, 0, 1, 0, 0, 0 }, /* INCOMMENT*/ { 1, 1, 1, 1, 1, 1, 1, 1 }, /* INNUM */ { 0, 1, 0, 0, 0, 0, 0, 0 }, /* INID */ { 0, 1, 1, 0, 0, 0, 0, 0 }, /* DONE */ { 0, 0, 0, 0, 0, 0, 0, 0 } };对照着看会发现几件事。INASSIGN那一行只有一个 1落在 EQ 列——只有紧跟等号才消耗字符其余一律回退这就是:与:的全部区别。INNUM行的 ALPHA 列是 0意味着123abc会被切成123和abc两个 token而不是一个非法整体这个选择并非唯一正确但它的好处是错误定位精确到第二个 token 的起始列。INCOMMENT整行都是 1注释内容全部吃掉且不保存只有}那一列把状态拉回START。START行的 LBRACE 走INCOMMENT这一步的 consume 也是 1但后面的 save 逻辑会把它排除在词素之外——注释起始符不该出现在任何 token 里。3.3 ungetNextChar唯一可用的回退机制回退这件事看起来很复杂实际只需要一格缓存。最长匹配需要的前瞻永远只有一个字符判断:要不要多读一位判断标识符到没到结尾都是一位就够。TINY 没有字符串字面量、没有浮点数所以不存在“要连读三位才知道是什么”的场景。static FILE *source; static int lastChar; /* 最近一次真正从文件读到的字符 */ static int pushedBack; /* 1 表示 lastChar 待重新取用 */ static int lineNo 1; static int getNextChar(void) { if (pushedBack) { pushedBack 0; return lastChar; } /* 先还债 */ lastChar fgetc(source); return lastChar; } static void ungetNextChar(void) { if (pushedBack) { /* 连续回退两次状态机写错了别静默吞掉 */ fprintf(stderr, line %d: pushback overflow\n, lineNo); exit(1); } pushedBack 1; }这个实现成立的前提是一条不变量ungetNextChar()只能紧跟在一次getNextChar()之后调用。因为回退靠的是lastChar这个单槽缓存如果中间又读了一次lastChar已经被覆盖还回去的就是错误的字符。把这条不变量写成断言比事后靠打印排查要省事得多。注意if (pushedBack) { ... exit(1); }这一段。很多实现把它写成静默覆盖于是字符悄悄丢失表现出来是“某些行莫名少一个符号”排查成本极高。让它直接崩比让它带病运行好。3.4 getToken 主循环DONE 是怎么收敛的外层是一个无限循环负责跳过空白和注释后重开一轮内层是一个while (state ! DONE)每轮读一个字符、查两张表、决定存不存、决定还不还。Token getToken(void) { Token tk; for (;;) { /* 跳过空白/注释后重新开始切一个 token */ StateType state START; int len 0, hitEOF 0, badComment 0; tk.lexeme[0] \0; tk.numValue 0; while (state ! DONE) { int c getNextChar(); int cls, consume, save; StateType next; if (c EOF) { hitEOF 1; if (state INCOMMENT) badComment 1; break; /* 不吃字符、不回退直接收尾 */ } cls charClass(c); consume consumeTable[state][cls]; next nextState[state][cls]; /* 保存条件token 的第一个字符或标识符/数字的后续字符 */ save (state START next ! START next ! INCOMMENT) || (state INASSIGN consume) || ((state INNUM || state INID) consume); if (save) { if (len 0) tk.lineNo lineNo; /* 起始行此刻快照 */ if (len MAXTOKENLEN) tk.lexeme[len] (char)c; tk.lexeme[len] \0; } if (!consume) ungetNextChar(); if (c \n consume) lineNo; /* 只有吃掉的换行才算行 */ state next; } if (badComment) { reportError(tk.lineNo, unterminated comment); return makeToken(ERROR, , tk.lineNo); } if (len 0) { if (hitEOF) return makeToken(ENDFILE, , lineNo); continue; /* 纯空白或一段注释 */ } tk.tokenType classify(tk); if (tk.tokenType ERROR) reportError(tk.lineNo, tk.lexeme); return tk; } }几个细节值得逐个拆开看。if (c EOF) break;的位置在内层循环最前面且不同步执行ungetNextChar——把 EOF 推回缓冲区会导致getToken永远返回同一个 EOF形成死循环。if (len 0) continue;负责把“只吃到了空白或一整段注释”的情况丢弃重新开一轮而不是返回一个空 token 让上层去判断。if (c \n consume) lineNo;里的consume判断很关键INNUM读到换行是要回退的如果这时候也自增行号下一次读到这个换行时会再加一次行号就整体漂移了。classify负责最后的定性按首字符分三条支路static TokenType classify(Token *tk) { char *s tk-lexeme; if (isalpha((unsigned char)s[0])) { /* 字母开头标识符或保留字 */ Bucket *b st_lookup(s); if (b) return b-type; /* 已经在表里直接给类型 */ st_insert(s, ID, tk-lineNo); /* 第一次见登记 */ return ID; } if (isdigit((unsigned char)s[0])) { /* 数字开头常量 */ tk-numValue atoi(s); return NUM; } return symbolLookup(s); /* 运算符/分隔符查不到即 ERROR */ }isalpha那一支是整个设计里最省事的一处它不区分“这是不是保留字”只查一次符号表查到就返回表里存的类型。保留字和标识符共用同一条代码路径后面第 4 章会把这个设计彻底展开。4. 符号表保留字和标识符共用同一张表的原因4.1 线性链表够不够用TINY 程序里标识符通常只有几十个用一条链表从头找到尾平均比较次数不过二三十性能上毫无问题。真正决定实现的不是性能而是接口形式符号表要在词法阶段被高频调用还要被后续的语法分析、语义检查继续使用所以它的查询接口必须能同时回答两个问题——“这个词在不在表里”和“在表里的话它是什么类型”。如果st_lookup只返回一个 bool调用方还得再查一次才能拿到类型等于把一次查找拆成两次。返回指向桶的指针则一次到位。4.2 把八个保留字预先塞进去保留字和标识符的字符构成完全一样都是字母开头、字母数字混排。如果分开处理classify里就得先跑一遍八个strcmp全都失败才当标识符——八个比较每个 token 都做一遍。换个思路初始化时把八个保留字当作“已经登记过的标识符”插进符号表只是把 type 字段填成IF、THEN这些而不是ID。此后任何字母开头的词无论是不是保留字走的都是同一次哈希查找命中什么类型就是什么类型。typedef struct Bucket { char name[MAXTOKENLEN 1]; TokenType type; /* ID或 IF/THEN/ELSE/... 之一 */ int memloc; /* 留给后续阶段词法阶段不用 */ struct Bucket *next; } Bucket; #define BUCKETS 211 static Bucket *table[BUCKETS]; static unsigned hash(const char *s) { unsigned h 0; while (*s) h h * 31u (unsigned char)*s; /* 31 是廉价且分布尚可的乘子 */ return h % BUCKETS; } Bucket *st_lookup(const char *name) { for (Bucket *b table[hash(name)]; b; b b-next) if (strcmp(b-name, name) 0) return b; return NULL; /* 未登记 */ } Bucket *st_insert(const char *name, TokenType type, int lineNo) { unsigned h hash(name); Bucket *b malloc(sizeof *b); strncpy(b-name, name, MAXTOKENLEN); b-name[MAXTOKENLEN] \0; /* strncpy 不保证终止符 */ b-type type; b-memloc -1; b-next table[h]; /* 头插插入 O(1) */ table[h] b; return b; } void st_init(void) { static const struct { const char *s; TokenType t; } kw[] { {if, IF}, {then, THEN}, {else, ELSE}, {end, END}, {repeat, REPEAT}, {until, UNTIL}, {read, READ}, {write, WRITE} }; for (size_t i 0; i sizeof kw / sizeof kw[0]; i) st_insert(kw[i].s, kw[i].t, 0); /* 0 表示不是用户写的 */ }这段代码里最值得看的是st_init。它把“哪些词是保留字”这件事收敛到一张静态表里词法分析的主循环因此完全不需要知道 TINY 有哪些关键字——classify里连一个strcmp都没有。将来语言扩充加关键字只改这张表主循环一行不动。memloc字段在词法阶段用不上留着是为了解释执行阶段等语义分析走完每个标识符要分配一个运行时的槽位那时再回头填这个字段比重新建一张表省事。这是典型的“结构先留出字段等后续阶段再填值”代价是每个桶多 4 字节。strncpy之后手动补终止符那一行是本文还有配套的精品资源点击获取

TINY语言词法分析器：DFA最长匹配与Token设计

相关推荐

排序算法详解：从基础到实战应用

jnetpcap源码编译指南：JDK8+GCC4.8+libpcap1.10全链路构建

专业医疗PPT设计指南与免费模板资源

更多资讯

代码覆盖率工具：提升软件质量的关键指标与实践

Harness工程实战：从套壳到骨架，构建高可靠LLM Agent

ISWC 2026：语义网与知识图谱技术前沿与投稿指南

2026届AI科研平台实测与选型指南

WeKnora 深度解析：Go 语言打造的企业知识管理框架，从部署到选型

XAMPP中MySQL报InnoDB存储引擎错误：日志定位与分场景修复

今日更新

PLFM_RADAR：从被动告警到主动感知的微服务健康监控系统

SPI隔离设计实战：MAX14431BAEE+与STM32F407工业级应用

数字隔离器如何根治SPI通信地环路干扰：MAX14431与TM4C129实战

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？