简介面向北京邮电大学编译原理课程学习者专为正在完成词法分析器实验、希望参考完整实现思路的学生准备。压缩包共4个文件整体约10KB包含2个txt文件、1个h头文件和1个cpp源文件txt中提供实验说明与测试样例h文件声明词法接口cpp文件实现Lexer核心逻辑代码量精简但结构完整适合对照课程要求研读。资源已有999人学习下载在校内编译原理实验环节中形成了一定参考积累。通过阅读头文件与实现可依次把握词法规则定义、源程序字符流读取、词语切分与符号生成、异常字符处理等关键步骤配合测试样例还能快速验证分词结果。对于想从零搭建词法分析器或想排查自身实现问题的人来说这份小体积代码包是直观且可运行的参考资料也能为后续语法分析、语义分析实验奠定基础。 刚开始拿到编译原理课程实验一词法分析器这个题目的时候我其实没太当回事。不就是把字符流切成单词嘛写个循环挨个判断就完事了。直到验收时被老师连环追问你的空白符怎么处理遇到非法字符怎么恢复关键字和标识符怎么区分才发现这个看起来人畜无害的实验其实是编译原理第一道真正的坎。这篇就把我完成这个实验的全过程、设计思路和踩过的坑完整拆开讲给正要动手写词法分析器的同学一个可参考的路径。1. 词法分析器到底在解决什么问题很多同学做这个实验时有个误区觉得词法分析就是把代码里认识的单词挑出来。这个理解太浅了。编译器的前端是一个流水线词法分析是第一个环节它的输入是纯粹的字符流输出是一串带有类型标识的单词符号也就是Token流。后续的语法分析器只会依赖这串Token流不会再回头去看原始字符所以词法分析器的输出质量直接决定整个编译器前端的稳定性。从编译原理的理论角度这一步的理论基础是正规式和有限自动机。所有能被词法分析器识别的单词结构都对应某个正规式正规式又能等价转化为NFA、DFA。实验通常要求能识别这几类单词关键字如if、else、while、return、int注意关键字是语言的保留字不能作为变量名标识符以字母或下划线开头后跟字母、数字、下划线整型、浮点型常量如123、3.14有的实验还要求识别科学计数法运算符和界符 - * /、 ! 、( ) { } ; ,等特殊Token行注释//和块注释/* */一般会被过滤掉如果你想真正理解这个实验的价值不要只盯着能用这个最低标准。老师后面会追问的、也可能是期末试题里反复出现的是这几个问题正规式怎么合并、NFA如何确定化为DFA、DFA如何最小化、词法分析器由哪些表驱动。这些才是实验背后真正要训练的东西。我当时给自己的目标是不靠一堆 if-else 硬写出一个能跑的千行代码而是设计一个用状态转换表驱动的词法分析器。这样不仅交实验时经得起问后面做语法分析、语义分析实验时这套设计思路也能直接迁移。2. 从正规式到DFA先画图再写代码我见过不少同学的代码逻辑大概是读到字符a判断是不是字母是的话继续读读到非字母为止再和关键字表比对。这种方式不是不行但如果遇到需要区分和这种最长匹配的场景代码会越写越乱补丁摞补丁。正确的做法是先做DFA设计让每个状态和每条边都明明白白再照着状态转换图写代码这样逻辑清晰又不容易漏边界。2.1 先确定你要识别的单词集合假设实验要求的语言是类C语法我把单词分成几大类每一类写出正规式单词大类正规式示例关键字固定字符串如if、else、while、for、return、int、float、voidif、while标识符[A-Za-z_][A-Za-z0-9_]*count、_temp、main整数[0-9]42、0浮点数[0-9].[0-9]有的还要求指数部分3.14、2.0e10运算符 - * / %、 ! 界符( ) { } [ ] ; ,(、;注释//[^\n]*、/([^][^/])/写好正规式之后把每个正规式对应的NFA画出来再把它们合并成一个大的NFA。这里有个实操技巧可以为每个种别设置一个独立的起始状态比如从状态0进入标识符子图从状态1进入整数子图之后做确定化时这些子图会自动合并。确定化的过程可以手算也可以用子集构造法在纸上推演一遍哪怕最终代码不是用表驱动而是硬编码这个推演过程也能帮你把边界状态全部理清。2.2 DFA状态转换表的设计我在实验中直接采用了表驱动的方式。先把所有状态编上号然后根据状态转换图写出一个二维数组。每一行是一个状态每一列是字符类别数字、字母、运算符、界符、空白符、其他单元格里存放的是跳转到的下一个状态编号。这个表写完之后词法分析器的核心循环就变成一个极简的查表过程。以一小段示例说明状态0初态数字 - 状态1字母/下划线 - 状态2 - 状态3其他 - 状态4 状态1整数中间态数字 - 状态1其他 - 结束 状态2标识符中间态字母/数字/下划线 - 状态2其他 - 结束 状态3可能为 - 状态5返回 其他 - 回退返回 这样设计的好处是以后想扩展一个token类型只需要加状态、改表核心循环代码完全不用动。我第一次做完就体会到编译原理课上学的那套形式化方法不是为了考试是真能在工程里省心。3. 核心实现Token结构、查表循环与关键字表有了状态转换表代码的主干就非常清晰了。我用C实现了整个分析器关键代码大概分三部分下面拆开细说。3.1 Token的数据结构每个Token至少需要几个字段单词种别枚举类型、单词文本本身、行号。列号通常按需添加但我建议加上因为后面做语法分析报错时列号能帮你精确指出错误位置。enum TokenType { TK_IDENT, TK_INT, TK_FLOAT, TK_IF, TK_ELSE, TK_WHILE, TK_RETURN, TK_INT_KW, TK_FLOAT_KW, TK_VOID_KW, TK_PLUS, TK_MINUS, TK_STAR, TK_SLASH, TK_ASSIGN, TK_EQ, ... TK_EOF, TK_ERROR }; struct Token { TokenType type; string text; int line; };这里有个经验点关键字的类型和标识符类型要分开定义但词法分析时可以先统一当作标识符识别出来再通过查关键字表来确认它到底是关键字还是普通标识符。这样状态转换图可以少画很多分支。3.2 字符分类与查表循环核心循环需要不断读取下一个字符根据当前状态和字符类别查表。首先把字符划分成几类比如数字、字母、下划线、运算符、界符、空白符等然后用一个分类函数返回类别编号。int charClass(char c) { if (isdigit(c)) return CC_DIGIT; if (isalpha(c) || c _) return CC_LETTER; if (c || c \t || c \n) return CC_BLANK; if (strchr(-*/%!|, c)) return CC_OPERATOR; if (strchr((){}[];,, c)) return CC_DELIM; return CC_UNKNOWN; }主循环的伪逻辑是读取一个字符查状态表到下一个状态如果到达终态就停下来整理Token。如果是非终态但是遇到了无法跳转的字符就回退一个字符按最短匹配或最长匹配规则决定怎么输出。while (true) { char c getNextChar(); int cls charClass(c); int nextState transTable[curState][cls]; if (nextState STATE_ERROR) { // 回退按终态输出 rollBack(); Token token makeToken(curState); emit(token); // 重置到初态继续 curState STATE_START; } else { curState nextState; buffer c; } }这里有个极其关键的细节也是我第一次实现时踩坑最深的地方回退。词法分析器的一次扫描可能读入多个字符才能确定一个Token的边界比如分析读到了时并不会立刻知道是还是必须再多读一个字符如果不是就要把多读的那个字符还回去让它参与下一个Token的识别。所以在实现里我维护了一个字符缓冲区用下标记录当前位置回退时就减下标这样比用ungetc更灵活也方便我随时检查已扫描的字符。3.3 关键字表与标识符识别标识符类Token识别到之后先按类型TK_IDENT存起来然后去查关键字表。这个表用unordered_map存最方便const unordered_mapstring, TokenType keywordTable { {if, TK_IF}, {else, TK_ELSE}, {while, TK_WHILE}, {return, TK_RETURN}, {int, TK_INT_KW}, {float, TK_FLOAT_KW}, {void, TK_VOID_KW} }; TokenType checkKeyword(const string word) { auto it keywordTable.find(word); return (it ! keywordTable.end()) ? it-second : TK_IDENT; }把关键字识别放在标识符识别之后这是符合编译原理教材经典做法的。如果你非要看到左字母就先去比对该不该是关键字遇到ifx这种变量就会出问题。先收集完整的字母数字串再整体查表逻辑最简单也最不容易出错。4. 最容易翻车的四个细节缓冲区、注释、最长匹配与行号理论和代码框架讲完说点实操层面的东西。这些细节单看都很小但任何一个处理不好轻则评测扣分重则验收时演示程序当场崩掉。4.1 缓冲区读取不要逐字符走文件I/O我第一版实现图省事用ifstream.get()一个字符一个字符地读文件结果在自己机器上跑着还行一换到评测机上速度就明显拉胯。后来改成一次读入整个文件到一个string里然后用下标遍历这既避免了频繁的I/O系统调用也方便做回退操作。如果实验限制了文件大小这种做法完全可行。string code; copy(istreambuf_iteratorchar(fin), istreambuf_iteratorchar(), back_inserter(code)); int pos 0; char getNextChar() { return (pos code.size()) ? code[pos] : EOF; } void rollBack() { if (pos 0) pos--; }如果代码量特别大一次全读入内存可能有压力那可以用分段缓冲的方式。但课程实验级别的代码量完全不需要考虑这种优化我实测读一个几MB的源文件这种方案都是毫秒级完成完全够用。4.2 多行注释的状态处理注释看起来是跳过但在状态机里它必须是一组完整的状态。我最初是判断到/就看下一个字符如果是*就进入注释循环一直读到*/。问题出在注释里出现*但后面不是/的情况比如/* a * b */。如果处理不好会在a *那里提前退出注释状态。这个问题的标准解法是进入块注释状态后遇到*就进入可能结束的子状态再读一个字符如果是/才真正结束注释如果字符是*就继续留在可能结束状态其他情况则回到普通注释状态。这其实就是DFA里最典型的最长匹配场景画个三状态图就一目了然。另外注释内部的换行要正常处理行号要持续递增很多同学在注释里忘了更新行号导致后续所有报错行号全部错位。4.3 运算符的最长匹配和、和、和这类运算符的识别核心是先读取后回退。拿举例读到后进入状态A再读一个字符如果是就返回TK_LE否则回退一个字符返回TK_LT。这里容易忽略的是多个运算符同时出现在连续代码里的情况比如abc。只要你把回退机制写对了这个问题就不存在。我见过有些同学的实现是单独抓和然后通过下一个字符是不是某个字符这种硬判断这种写法在单个场景下能用但组合复杂之后很容易出bug。状态机天然处理了这些排列组合。4.4 行号和列号不只是填个数字很多实验模板要求输出Token时带行号有的还要求列号。行号和列号的维护看似简单实际等于在你所有读取字符的地方插入了一个追踪器。我实现时在getNextChar()里统一维护读到\n行号加一、列号归零其他字符列号加一。这样无论注释、字符串还是普通代码行号都不会记错。如果老师要求错误恢复后继续分析行号列号的精度就非常关键因为你报错信息里的一行一列是同学唯一能用来定位问题的线索。还有一个隐藏要求我是在验收时才注意到的有的评测程序不是看你的输出Token流而是看你的二进制token种别编码顺序。比如关键字、标识符、整数、浮点数、运算符、界符的编码值必须按实验文档里的注释顺序来定义否则即使分析正确自动评分器也会判错。我建议在写枚举定义时严格参考实验文档列出的单词种别顺序。5. 测试用例怎么设计从正常到极端实验报告和验收时测试用例的设计也是重要一环。与其随手写个test.c文件跑一下就说程序能运行不如系统地设计一批覆盖各种情况的用例。这样既是对自己程序的检验也能在验收时展示思路老师会觉得你确实把边界情况都考虑清楚了。5.1 功能覆盖型用例第一步保证每一类token至少出现一次。写一个综合测试文件包含变量声明、赋值、算术运算、比较运算、函数调用、注释等多类语法。然后是每种运算符的单独测试特别是容易出问题的双目运算符如、!、、、、||确保它们不会被拆成两个单字符token。5.2 边界异常型用例边界情况是我这次收获最大的一部分我列一下我实际跑过的异常输入及预期结果输入期望行为说明空文件直接输出EOF Token不能崩只有空白符和换行输出EOF Token空白符应被忽略连续多个空格和Tab正常切分Token空白符不产生Token未闭合的块注释报错并记录行号提示未闭合注释非法字符如、#、$报错指出行号列号分析器需要错误恢复超长标识符100个字符以上可以正常识别并输出不要出现缓冲区溢出整数后面紧跟字母如123abc有的实验要求报错有的允许识别为数字后接标识符结合实验文档要求处理十六进制数字0x1F如果文档没要求按0和x1F两个token或报错关注实验规格这些用例跑完后我建议把输出结果和预期做成对照表放在实验报告里。老师看一眼就知道你程序的处理逻辑清晰而不是只能跑通常规情况。5.3 自动对比测试的小技巧手动看输出太累了而且容易看漏。我自己写了一个简单的Python脚本自动编译并运行词法分析器把输出token流保存下来再和标准输出做diff。以后每改一次程序的逻辑就重跑一遍全部测试用例确保没有引入回归问题。这个习惯帮我挡掉了好几处后来改动时的低级错误。#!/bin/bash # 简单回归测试脚本 for f in tests/*.c; do ./lexer $f out/$(basename $f).out diff out/$(basename $f).out expect/$(basename $f).out \ echo $f PASS || echo $f FAIL done这个脚本看起来简单但整个实验过程中帮我节省了大量重复劳动。特别是到后期修改状态表、调整Token类型定义时每次跑一遍全量测试不超过十秒钟但能保证任何一处小改动都不会导致之前已经正确的功能退化。最后再分享一个实验之外的小收获。做完这个实验后我回去翻了一下之前写的一些小型脚本发现自己对字符串处理和文本解析的敏感度明显提高了。比如写配置文件的读取器时我会下意识地考虑注释、空白、转义字符的处理方式不再像以前那样想当然地用split一把梭。这就是编译原理实验的意义它训练的不是某个具体语言或者工具而是一种把字符串处理系统化的思维方式。如果你在实验过程中也遇到那种状态转换表画着想看懂了一写代码还是无从下手的时刻别慌把图画完、把表写出来代码只是把表和循环翻译成语法而已真正的工作在设计阶段已经完成了。本文还有配套的精品资源点击获取 编译原理词法分析器设计与实现：从正规式到DFA的完整指南
简介面向北京邮电大学编译原理课程学习者专为正在完成词法分析器实验、希望参考完整实现思路的学生准备。压缩包共4个文件整体约10KB包含2个txt文件、1个h头文件和1个cpp源文件txt中提供实验说明与测试样例h文件声明词法接口cpp文件实现Lexer核心逻辑代码量精简但结构完整适合对照课程要求研读。资源已有999人学习下载在校内编译原理实验环节中形成了一定参考积累。通过阅读头文件与实现可依次把握词法规则定义、源程序字符流读取、词语切分与符号生成、异常字符处理等关键步骤配合测试样例还能快速验证分词结果。对于想从零搭建词法分析器或想排查自身实现问题的人来说这份小体积代码包是直观且可运行的参考资料也能为后续语法分析、语义分析实验奠定基础。 刚开始拿到编译原理课程实验一词法分析器这个题目的时候我其实没太当回事。不就是把字符流切成单词嘛写个循环挨个判断就完事了。直到验收时被老师连环追问你的空白符怎么处理遇到非法字符怎么恢复关键字和标识符怎么区分才发现这个看起来人畜无害的实验其实是编译原理第一道真正的坎。这篇就把我完成这个实验的全过程、设计思路和踩过的坑完整拆开讲给正要动手写词法分析器的同学一个可参考的路径。1. 词法分析器到底在解决什么问题很多同学做这个实验时有个误区觉得词法分析就是把代码里认识的单词挑出来。这个理解太浅了。编译器的前端是一个流水线词法分析是第一个环节它的输入是纯粹的字符流输出是一串带有类型标识的单词符号也就是Token流。后续的语法分析器只会依赖这串Token流不会再回头去看原始字符所以词法分析器的输出质量直接决定整个编译器前端的稳定性。从编译原理的理论角度这一步的理论基础是正规式和有限自动机。所有能被词法分析器识别的单词结构都对应某个正规式正规式又能等价转化为NFA、DFA。实验通常要求能识别这几类单词关键字如if、else、while、return、int注意关键字是语言的保留字不能作为变量名标识符以字母或下划线开头后跟字母、数字、下划线整型、浮点型常量如123、3.14有的实验还要求识别科学计数法运算符和界符 - * /、 ! 、( ) { } ; ,等特殊Token行注释//和块注释/* */一般会被过滤掉如果你想真正理解这个实验的价值不要只盯着能用这个最低标准。老师后面会追问的、也可能是期末试题里反复出现的是这几个问题正规式怎么合并、NFA如何确定化为DFA、DFA如何最小化、词法分析器由哪些表驱动。这些才是实验背后真正要训练的东西。我当时给自己的目标是不靠一堆 if-else 硬写出一个能跑的千行代码而是设计一个用状态转换表驱动的词法分析器。这样不仅交实验时经得起问后面做语法分析、语义分析实验时这套设计思路也能直接迁移。2. 从正规式到DFA先画图再写代码我见过不少同学的代码逻辑大概是读到字符a判断是不是字母是的话继续读读到非字母为止再和关键字表比对。这种方式不是不行但如果遇到需要区分和这种最长匹配的场景代码会越写越乱补丁摞补丁。正确的做法是先做DFA设计让每个状态和每条边都明明白白再照着状态转换图写代码这样逻辑清晰又不容易漏边界。2.1 先确定你要识别的单词集合假设实验要求的语言是类C语法我把单词分成几大类每一类写出正规式单词大类正规式示例关键字固定字符串如if、else、while、for、return、int、float、voidif、while标识符[A-Za-z_][A-Za-z0-9_]*count、_temp、main整数[0-9]42、0浮点数[0-9].[0-9]有的还要求指数部分3.14、2.0e10运算符 - * / %、 ! 界符( ) { } [ ] ; ,(、;注释//[^\n]*、/([^][^/])/写好正规式之后把每个正规式对应的NFA画出来再把它们合并成一个大的NFA。这里有个实操技巧可以为每个种别设置一个独立的起始状态比如从状态0进入标识符子图从状态1进入整数子图之后做确定化时这些子图会自动合并。确定化的过程可以手算也可以用子集构造法在纸上推演一遍哪怕最终代码不是用表驱动而是硬编码这个推演过程也能帮你把边界状态全部理清。2.2 DFA状态转换表的设计我在实验中直接采用了表驱动的方式。先把所有状态编上号然后根据状态转换图写出一个二维数组。每一行是一个状态每一列是字符类别数字、字母、运算符、界符、空白符、其他单元格里存放的是跳转到的下一个状态编号。这个表写完之后词法分析器的核心循环就变成一个极简的查表过程。以一小段示例说明状态0初态数字 - 状态1字母/下划线 - 状态2 - 状态3其他 - 状态4 状态1整数中间态数字 - 状态1其他 - 结束 状态2标识符中间态字母/数字/下划线 - 状态2其他 - 结束 状态3可能为 - 状态5返回 其他 - 回退返回 这样设计的好处是以后想扩展一个token类型只需要加状态、改表核心循环代码完全不用动。我第一次做完就体会到编译原理课上学的那套形式化方法不是为了考试是真能在工程里省心。3. 核心实现Token结构、查表循环与关键字表有了状态转换表代码的主干就非常清晰了。我用C实现了整个分析器关键代码大概分三部分下面拆开细说。3.1 Token的数据结构每个Token至少需要几个字段单词种别枚举类型、单词文本本身、行号。列号通常按需添加但我建议加上因为后面做语法分析报错时列号能帮你精确指出错误位置。enum TokenType { TK_IDENT, TK_INT, TK_FLOAT, TK_IF, TK_ELSE, TK_WHILE, TK_RETURN, TK_INT_KW, TK_FLOAT_KW, TK_VOID_KW, TK_PLUS, TK_MINUS, TK_STAR, TK_SLASH, TK_ASSIGN, TK_EQ, ... TK_EOF, TK_ERROR }; struct Token { TokenType type; string text; int line; };这里有个经验点关键字的类型和标识符类型要分开定义但词法分析时可以先统一当作标识符识别出来再通过查关键字表来确认它到底是关键字还是普通标识符。这样状态转换图可以少画很多分支。3.2 字符分类与查表循环核心循环需要不断读取下一个字符根据当前状态和字符类别查表。首先把字符划分成几类比如数字、字母、下划线、运算符、界符、空白符等然后用一个分类函数返回类别编号。int charClass(char c) { if (isdigit(c)) return CC_DIGIT; if (isalpha(c) || c _) return CC_LETTER; if (c || c \t || c \n) return CC_BLANK; if (strchr(-*/%!|, c)) return CC_OPERATOR; if (strchr((){}[];,, c)) return CC_DELIM; return CC_UNKNOWN; }主循环的伪逻辑是读取一个字符查状态表到下一个状态如果到达终态就停下来整理Token。如果是非终态但是遇到了无法跳转的字符就回退一个字符按最短匹配或最长匹配规则决定怎么输出。while (true) { char c getNextChar(); int cls charClass(c); int nextState transTable[curState][cls]; if (nextState STATE_ERROR) { // 回退按终态输出 rollBack(); Token token makeToken(curState); emit(token); // 重置到初态继续 curState STATE_START; } else { curState nextState; buffer c; } }这里有个极其关键的细节也是我第一次实现时踩坑最深的地方回退。词法分析器的一次扫描可能读入多个字符才能确定一个Token的边界比如分析读到了时并不会立刻知道是还是必须再多读一个字符如果不是就要把多读的那个字符还回去让它参与下一个Token的识别。所以在实现里我维护了一个字符缓冲区用下标记录当前位置回退时就减下标这样比用ungetc更灵活也方便我随时检查已扫描的字符。3.3 关键字表与标识符识别标识符类Token识别到之后先按类型TK_IDENT存起来然后去查关键字表。这个表用unordered_map存最方便const unordered_mapstring, TokenType keywordTable { {if, TK_IF}, {else, TK_ELSE}, {while, TK_WHILE}, {return, TK_RETURN}, {int, TK_INT_KW}, {float, TK_FLOAT_KW}, {void, TK_VOID_KW} }; TokenType checkKeyword(const string word) { auto it keywordTable.find(word); return (it ! keywordTable.end()) ? it-second : TK_IDENT; }把关键字识别放在标识符识别之后这是符合编译原理教材经典做法的。如果你非要看到左字母就先去比对该不该是关键字遇到ifx这种变量就会出问题。先收集完整的字母数字串再整体查表逻辑最简单也最不容易出错。4. 最容易翻车的四个细节缓冲区、注释、最长匹配与行号理论和代码框架讲完说点实操层面的东西。这些细节单看都很小但任何一个处理不好轻则评测扣分重则验收时演示程序当场崩掉。4.1 缓冲区读取不要逐字符走文件I/O我第一版实现图省事用ifstream.get()一个字符一个字符地读文件结果在自己机器上跑着还行一换到评测机上速度就明显拉胯。后来改成一次读入整个文件到一个string里然后用下标遍历这既避免了频繁的I/O系统调用也方便做回退操作。如果实验限制了文件大小这种做法完全可行。string code; copy(istreambuf_iteratorchar(fin), istreambuf_iteratorchar(), back_inserter(code)); int pos 0; char getNextChar() { return (pos code.size()) ? code[pos] : EOF; } void rollBack() { if (pos 0) pos--; }如果代码量特别大一次全读入内存可能有压力那可以用分段缓冲的方式。但课程实验级别的代码量完全不需要考虑这种优化我实测读一个几MB的源文件这种方案都是毫秒级完成完全够用。4.2 多行注释的状态处理注释看起来是跳过但在状态机里它必须是一组完整的状态。我最初是判断到/就看下一个字符如果是*就进入注释循环一直读到*/。问题出在注释里出现*但后面不是/的情况比如/* a * b */。如果处理不好会在a *那里提前退出注释状态。这个问题的标准解法是进入块注释状态后遇到*就进入可能结束的子状态再读一个字符如果是/才真正结束注释如果字符是*就继续留在可能结束状态其他情况则回到普通注释状态。这其实就是DFA里最典型的最长匹配场景画个三状态图就一目了然。另外注释内部的换行要正常处理行号要持续递增很多同学在注释里忘了更新行号导致后续所有报错行号全部错位。4.3 运算符的最长匹配和、和、和这类运算符的识别核心是先读取后回退。拿举例读到后进入状态A再读一个字符如果是就返回TK_LE否则回退一个字符返回TK_LT。这里容易忽略的是多个运算符同时出现在连续代码里的情况比如abc。只要你把回退机制写对了这个问题就不存在。我见过有些同学的实现是单独抓和然后通过下一个字符是不是某个字符这种硬判断这种写法在单个场景下能用但组合复杂之后很容易出bug。状态机天然处理了这些排列组合。4.4 行号和列号不只是填个数字很多实验模板要求输出Token时带行号有的还要求列号。行号和列号的维护看似简单实际等于在你所有读取字符的地方插入了一个追踪器。我实现时在getNextChar()里统一维护读到\n行号加一、列号归零其他字符列号加一。这样无论注释、字符串还是普通代码行号都不会记错。如果老师要求错误恢复后继续分析行号列号的精度就非常关键因为你报错信息里的一行一列是同学唯一能用来定位问题的线索。还有一个隐藏要求我是在验收时才注意到的有的评测程序不是看你的输出Token流而是看你的二进制token种别编码顺序。比如关键字、标识符、整数、浮点数、运算符、界符的编码值必须按实验文档里的注释顺序来定义否则即使分析正确自动评分器也会判错。我建议在写枚举定义时严格参考实验文档列出的单词种别顺序。5. 测试用例怎么设计从正常到极端实验报告和验收时测试用例的设计也是重要一环。与其随手写个test.c文件跑一下就说程序能运行不如系统地设计一批覆盖各种情况的用例。这样既是对自己程序的检验也能在验收时展示思路老师会觉得你确实把边界情况都考虑清楚了。5.1 功能覆盖型用例第一步保证每一类token至少出现一次。写一个综合测试文件包含变量声明、赋值、算术运算、比较运算、函数调用、注释等多类语法。然后是每种运算符的单独测试特别是容易出问题的双目运算符如、!、、、、||确保它们不会被拆成两个单字符token。5.2 边界异常型用例边界情况是我这次收获最大的一部分我列一下我实际跑过的异常输入及预期结果输入期望行为说明空文件直接输出EOF Token不能崩只有空白符和换行输出EOF Token空白符应被忽略连续多个空格和Tab正常切分Token空白符不产生Token未闭合的块注释报错并记录行号提示未闭合注释非法字符如、#、$报错指出行号列号分析器需要错误恢复超长标识符100个字符以上可以正常识别并输出不要出现缓冲区溢出整数后面紧跟字母如123abc有的实验要求报错有的允许识别为数字后接标识符结合实验文档要求处理十六进制数字0x1F如果文档没要求按0和x1F两个token或报错关注实验规格这些用例跑完后我建议把输出结果和预期做成对照表放在实验报告里。老师看一眼就知道你程序的处理逻辑清晰而不是只能跑通常规情况。5.3 自动对比测试的小技巧手动看输出太累了而且容易看漏。我自己写了一个简单的Python脚本自动编译并运行词法分析器把输出token流保存下来再和标准输出做diff。以后每改一次程序的逻辑就重跑一遍全部测试用例确保没有引入回归问题。这个习惯帮我挡掉了好几处后来改动时的低级错误。#!/bin/bash # 简单回归测试脚本 for f in tests/*.c; do ./lexer $f out/$(basename $f).out diff out/$(basename $f).out expect/$(basename $f).out \ echo $f PASS || echo $f FAIL done这个脚本看起来简单但整个实验过程中帮我节省了大量重复劳动。特别是到后期修改状态表、调整Token类型定义时每次跑一遍全量测试不超过十秒钟但能保证任何一处小改动都不会导致之前已经正确的功能退化。最后再分享一个实验之外的小收获。做完这个实验后我回去翻了一下之前写的一些小型脚本发现自己对字符串处理和文本解析的敏感度明显提高了。比如写配置文件的读取器时我会下意识地考虑注释、空白、转义字符的处理方式不再像以前那样想当然地用split一把梭。这就是编译原理实验的意义它训练的不是某个具体语言或者工具而是一种把字符串处理系统化的思维方式。如果你在实验过程中也遇到那种状态转换表画着想看懂了一写代码还是无从下手的时刻别慌把图画完、把表写出来代码只是把表和循环翻译成语法而已真正的工作在设计阶段已经完成了。本文还有配套的精品资源点击获取