TINY语言手工词法分析器：DFA、最长匹配与错误恢复

简介这份压缩包面向编译原理课程学习者与需要完成词法分析实验的C/C开发者围绕手工构造TINY语言词法分析器展开可用于理解扫描器如何把源码切分为关键字、标识符、常量与运算符等记号并借助确定有限状态自动机完成状态转移设计。包内共10个文件约779KB以cpp源代码、tny测试样例、docx实验报告及工程配置和可执行文件为主分别对应核心实现、输入验证、过程记录与运行环境便于对照调试。已有1333人学习。读者可从中获得一套较完整的手工实现思路C词法分析函数与状态机组织方式、记号类型枚举与记号结构体的数据设计、测试样例的预期输出以及实验报告中对DFA设计、关键代码解释和问题处理过程的整理适合课程实验复现与逐项核对。1. 手工词法分析器TINY 这种小语言反而更适合看清 DFA 的边界先把一个反直觉结论放这TINY 语言只有 if、then、else、end、repeat、until、read、write 这些关键字加上标识符、整数、:、、、和注释看起来用正则表达式一把梭就完了但真正用 C/C 手工构造 TINY 语言词法分析器时难点不在“认出单词”而在“什么时候该多看一个字符、什么时候该退回、错误发生时还能不能给出准确行列号”。生成器把这些问题藏进黑匣子手写 DFA 则把它们摊在状态转移和 Token 结构里。TINY 小到可以整个装进脑子又足够暴露最长匹配、关键字表和错误恢复的取舍所以它很适合用来建立词法分析器的底层认知。2. 从字符流到 Token 流TINY 词法分析器的状态机骨架词法分析器的输入是字符流输出是 Token 流。听起来只是“把字符串切开”但真正写起来最先撞上的问题是看到时你不能立刻决定它是、还是看到i时你也不能立刻决定它是标识符还是关键字if。所以扫描器必须有“看一个字符但不消费”的能力也就是 lookahead。TINY 的状态少适合把整个扫描过程写成一个带peek/advance/mark/reset的小型状态机而不是边读边切、切完再猜。2.1 输入缓冲与 lookahead为什么不是“读一个字符就立刻切 token”最直觉的写法是getchar()拿到一个字符就进switch但这条路很快会翻车。比如读到后如果下一个字符是当前 Token 应该是如果是应该是否则才是。这意味着扫描器至少要能向前看一个字符并且在不匹配双字符运算符时能够“退回”到单字符接受状态。C 标准库的ungetc只保证一个字符的回退遇到更复杂的回退就会变得不可靠所以手写扫描器更常见的做法是把源文件整体读进一个std::string用下标pos表示当前读到哪里用mark()记录 Token 起点用reset()回退到起点。struct SourcePos { int index; // 在源串中的字节下标 int line; // 从 1 开始 int column; // 从 1 开始按字符计数 }; class Scanner { public: explicit Scanner(const std::string source) : src(source) {} // 不消费字符k0 表示当前字符k1 表示下一个字符 char peek(size_t k 0) const { return pos k src.size() ? src[pos k] : \0; } // 所有消费字符的路径都走这里保证行列号同步更新 char advance() { char c src[pos]; if (c \n) { line; column 1; } else { column; } return c; } SourcePos mark() const { return { static_castint(pos), line, column }; } void reset(SourcePos m) { pos m.index; line m.line; column m.column; } private: const std::string src; size_t pos 0; int line 1; int column 1; };这段代码的核心是三个动作peek(k)只观察不消费advance()消费并维护位置mark/reset保存和恢复扫描起点。k是向前看的偏移量TINY 里最多用到 1因为双字符运算符只有:、、、这几种。advance()里把\n单独处理是为了让行号在跳过空白、注释和普通 Token 时都不会漏掉。reset()的存在让“最长匹配失败后回退”变成一次 O(1) 的位置恢复而不是依赖输入流的回退函数。提示peek()在文件末尾返回\0是一种哨兵写法简单好用如果源文件本身可能包含 NUL 字节这种写法会误判 EOF生产实现里应改成pos src.size()判断。2.2 DFA 状态转移表为什么比一长串 if-else 更稳手写词法分析器的本质是把一个 DFA 写在代码里。TINY 的状态可以粗略分成起始状态、标识符状态、数字状态、运算符状态、注释状态、错误状态。每个状态遇到一类字符就转移到下一个状态并在接受状态产出 Token。真正稳的写法不是把所有判断堆在一个巨大的if-else里而是先想清楚“当前状态 输入类别 → 下一状态 动作”再用switch或表驱动实现。表驱动的好处是状态和动作分离补一条边、加一个关键字、改一个错误分支都不容易碰坏别的路径手写switch的好处是读起来直接适合 TINY 这种状态数很少的语言。enum class TokenType { IF, THEN, ELSE, END, REPEAT, UNTIL, READ, WRITE, ID, NUM, ASSIGN, PLUS, MINUS, STAR, SLASH, EQ, LT, GT, LE, GE, NE, LPAREN, RPAREN, SEMI, COMMA, END_OF_FILE, ERROR }; struct Token { TokenType type; std::string lexeme; // 原始拼写保留大小写和数字文本 int line; // Token 起始行 int column; // Token 起始列 };TokenType把“词法类别”固定成枚举避免用字符串比较来判断 Token 类型lexeme保留原始拼写是因为关键字和标识符共享同一条扫描路径符号表后面需要原始名字数字也需要原始文本才能决定怎么转成整数line/column记录的是 Token 起始位置不是结束位置这样报错时指向的是“这个单词从哪开始”比指向结尾更有用。END_OF_FILE和ERROR是控制 Token不参与语法规则但能让上层知道“输入结束了”和“这里有一个词法问题”。2.3 Token 结构与词法单元的边界词法分析器最容易混淆的边界是“什么算一个 Token”。在 TINY 里if和ifif都是字母序列但前者是关键字后者是标识符123是数字123abc不是“数字 标识符”而是一个词法错误是一个 Token不能拆成和。这些边界不是靠“看到什么就返回什么”决定的而是靠最长匹配规则扫描器一直吃到“再吃一个字符就不再属于当前 Token”为止然后回退到最近一个接受状态。关键字识别通常不单独做一条 DFA 分支而是先按标识符规则读完整串再去关键字表里查。这样关键字集合就是一张可配置的表而不是散落在状态转移里的硬编码。词法单元边界还影响错误定位。比如这种非法字符扫描器不能直接崩溃也不能无限循环它应该产出一个ERRORToken记录行列号然后至少前进一个字符保证扫描过程继续往前走。注释和空白不产出 Token但它们的字符仍然要经过advance()否则后面的行号会整体偏移。TINY 的注释用{ ... }包起来注释内部可以换行所以跳过注释时行号维护和普通代码完全一样不能图省事用pos直接跳。3. 最长匹配与回退标识符、关键字和数字是怎么被切开的最长匹配是词法分析器的第一原则在当前位置选择能匹配的最长词素。比长所以优先if和ifif都以if开头但ifif更长所以整个ifif是一个标识符不能切成ifif。手写扫描器实现最长匹配的常用套路是“先贪婪地吃吃到不能再吃再回退到最近接受状态”。TINY 的运算符最多两个字符所以回退距离很短标识符和数字则是一次读到底不需要频繁回退但错误恢复时要知道自己吃掉了多少字符。3.1 标识符与保留字先当标识符读再查关键字表标识符的规则通常是字母或下划线开头后面接字母、数字或下划线。TINY 原始定义里标识符可能只允许字母开头这里按常见扩展允许下划线如果严格照原始语法把_的判断去掉即可。扫描时先按标识符规则一直读到非标识符字符然后用读到的完整字符串去关键字表里查。查到了就返回对应的关键字 Token查不到才返回ID。这种“先统一读、后查表”的做法比在 DFA 里为每个关键字单独开分支更稳因为关键字表可以随时增删扫描循环不用改。Token Scanner::scanIdentifierOrKeyword() { SourcePos start mark(); while (std::isalpha(static_castunsigned char(peek())) || peek() _) { advance(); } std::string lexeme src.substr(start.index, pos - start.index); auto it keywords.find(lexeme); if (it ! keywords.end()) { return Token{it-second, lexeme, start.line, start.column}; } return Token{TokenType::ID, lexeme, start.line, start.column}; }这段代码先记录起点然后循环消费字母和下划线最后用substr截出完整词素。keywords是std::unordered_mapstd::string, TokenType初始化时把if、then、else、end、repeat、until、read、write映射到对应枚举。std::isalpha的参数先转成unsigned char是因为 C/C 的字符分类函数对负值字符有未定义行为处理非 ASCII 输入时这个细节很容易埋雷。关键字表只存小写形式扫描器保持大小写敏感TINY 的关键字都是小写这样IF会被当成普通标识符符合语言定义。提示关键字表用哈希表不是为了性能而是让“关键字集合”变成数据。以后要加for、while只改初始化表不用动扫描循环。3.2 数字常量为什么不能在第一个非数字处直接报错数字扫描看起来最简单一直吃数字遇到非数字就停。但123abc这种输入会暴露问题。如果扫描器在1、2、3之后看到a就返回NUM(123)下一个 Token 会变成ID(abc)语法分析器看到的 Token 流是“数字后面跟着标识符”报错位置可能飘到下一行真正的原因却被掩盖了。更合理的做法是数字读完后如果紧接着是字母或下划线就把连续字母数字一起吞掉产出一个ERRORToken词素保留123abc错误消息写“数字常量后不能紧跟字母或下划线”。这样错误定位在数字开头语法分析也能明确知道这里有一个词法错误。Token Scanner::scanNumber() { SourcePos start mark(); while (std::isdigit(static_castunsigned char(peek()))) { advance(); } // 数字后面紧跟字母/下划线说明整个词素非法不能切成 NUM ID if (std::isalpha(static_castunsigned char(peek())) || peek() _) { while (std::isalnum(static_castunsigned char(peek())) || peek() _) { advance(); } return makeError(start, src.substr(start.index, pos - start.index), 数字常量后不能紧跟字母或下划线); } return Token{TokenType::NUM, src.substr(start.index, pos - start.index), start.line, start.column}; }这段代码的关键在第二个while它把非法后缀一起吃掉保证123abc只产出一个ERROR而不是NUM加ID。makeError会把错误消息和行列号存进扫描器的错误列表同时返回ERRORToken。数字的数值转换没有放在这里是因为词法层只负责“是不是合法数字常量”整数溢出、范围检查可以放到语义分析阶段如果要在词法层转至少要用带溢出检查的转换函数不能直接std::stoi了事。3.3 回退的边界unget 一个字符够不够TINY 的运算符最长匹配只需要向前看一个字符:后面是不是后面是不是或后面是不是。所以手写扫描器里常见的做法是“先读第一个字符再看peek()能组成双字符就再advance()一次”。这种写法没有真正回退而是把回退变成了“少读一个字符”的分支判断。真要用ungetcC 标准只保证一个字符的回退连续回退两次在部分实现上会失败这也是为什么更稳的方案是mark/reset。Token Scanner::scanOperator() { SourcePos start mark(); char c advance(); switch (c) { case :: if (peek() ) { advance(); return makeToken(TokenType::ASSIGN, start); } return makeError(start, :, 单独的 : 不是合法运算符); case : if (peek() ) { advance(); return makeToken(TokenType::LE, start); } if (peek() ) { advance(); return makeToken(TokenType::NE, start); } return makeToken(TokenType::LT, start); case : if (peek() ) { advance(); return makeToken(TokenType::GE, start); } return makeToken(TokenType::GT, start); case : return makeToken(TokenType::EQ, start); case : return makeToken(TokenType::PLUS, start); case -: return makeToken(TokenType::MINUS, start); case *: return makeToken(TokenType::STAR, start); case /: return makeToken(TokenType::SLASH, start); case (: return makeToken(TokenType::LPAREN, start); case ): return makeToken(TokenType::RPAREN, start); case ;: return makeToken(TokenType::SEMI, start); case ,: return makeToken(TokenType::COMMA, start); default: return makeError(start, std::string(1, c), 无法识别的运算符); } }scanOperator()先消费第一个字符再根据peek()决定是否消费第二个字符。每个分支最多多看一个字符所以不会出现“回退多个字符”的问题makeToken用起点到当前pos截取词素保证:、、、的lexeme是完整双字符。下面的表把 TINY 里的多字符运算符和单字符运算符放在一起对比能看出最长匹配为什么要优先双字符。输入Token 类型说明:ASSIGN赋值号必须先于单独的:判断LE小于等于必须先于判断GE大于等于必须先于判断NE不等于必须先于判断:ERROR单独冒号不是合法运算符LT没有配成双字符时回落到单字符4. 注释、空白与错误恢复词法分析器的黑匣子怎么定位问题词法分析器经常被当成“黑匣子”上层只看到 Token 流出了错却不知道是哪个字符引起的。TINY 这种小语言里错误定位的差距主要来自三个地方跳过空白时有没有维护行号注释未闭合时有没有留下错误记录非法字符有没有保证扫描继续前进。把这三件事处理好词法层就不再是只会说“语法错误”的黑匣子而是能明确指出“第几行第几列、哪个词素、什么原因”。4.1 空白和换行行号列号不是装饰空白字符不产出 Token但它们必须被消费而且消费路径必须和普通字符一样经过advance()。如果跳过空格时直接pos行号不会变列号也不会变后面的 Token 位置就会整体偏移。换行更特殊\n要把行号加一、列号重置为 1\r\n这种换行如果按两个字符处理\r不应该额外增加行号否则 Windows 风格的源文件会把行号多算一行。TINY 的样例通常很简单但手写扫描器一旦把位置维护写散后面查错就会变成血泪经验。void Scanner::skipWhitespaceAndComments() { for (;;) { while (std::isspace(static_castunsigned char(peek()))) { advance(); } if (peek() {) { SourcePos start mark(); advance(); // 吃掉 { while (peek() ! } peek() ! \0) { advance(); } if (peek() \0) { errors.push_back({start.line, start.column, 注释未闭合直到文件结尾}); return; } advance(); // 吃掉 } continue; } break; } }这段代码先循环吃掉所有空白再检查是不是注释开头。注释内部一直advance()到}或文件末尾这样注释里的换行也会正确增加行号。start保存注释起点未闭合时把错误定位到{所在行列而不是文件末尾返回前不再继续循环避免在 EOF 上打转。std本文还有配套的精品资源点击获取