编译原理实验：词法分析器设计与实现，从Token到状态图的完整指南

简介面向编译原理课程学习者的北邮词法分析器实验材料围绕词法分析器的设计与实现展开适合正在学习编译器前端、需要完成类似实验或想动手验证词法规则的学生参考。压缩包内共4个文件以C源码、H头文件与TXT文档为主压缩后仅10KB结构紧凑便于快速下载与本地运行。源码部分覆盖了词法规则定义、输入字符流处理、分词逻辑以及错误处理等关键环节配合说明文档和测试样例可帮助读者梳理词法分析器的构建思路理解标识符、关键字、常量、运算符等词素的识别过程并应用到后续语法分析实验的衔接之中为完整编译器前端打下基础。目前已有999人学习下载作为北邮课程的实验成果对编译原理入门者有直接的借鉴价值。1. 实验目标与整体设计思路1.1 词法分析器在编译流程中的位置北邮的编译原理课程实验一要求实现一个词法分析器这几乎是每个计算机专业学生的必修关卡。我当时拿到这个实验的第一反应是这不就是一个“查单词”的程序吗但真正动手之后才发现词法分析器作为编译器前端的第一道工序它的设计质量直接影响后面语法分析、语义分析的实现难度绝不是简单写几个switch-case就能糊弄过去的。词法分析器做的事情用大白话讲就是把源代码这种人类可读的字符流按照语言规则切分成一个个有意义的“单词”——也就是Token。比如你写了一句int a 10;词法分析器需要识别出int是关键字、a是标识符、是赋值运算符、10是整数常量、;是界符然后把它们打包成关键字, int、标识符, a、运算符, 、整数常量, 10、界符, ;这样的二元组序列交给语法分析器去处理。这个实验的完整名称是“北邮编译原理课程实验一词法分析器.zip”根据文件名来看大概率是学长学姐整理好的一份实验包里面应该包含实验要求文档、参考代码框架、测试用例以及实验报告模板。有这样一个压缩包在手其实能省掉很多方向上的纠结剩下的就是把它吃透、消化成自己的东西。1.2 实验需求的深层拆解拆开这个实验核心需求其实就三块第一Token类别定义。这是整个实验的地基。你需要明确这个实验要识别的语言有哪些词法单元通常包括关键字如if、else、while、return、标识符变量名、函数名、整型常量、实型常量、运算符算术运算符、关系运算符、赋值运算符、界符括号、分号、逗号、大括号。定义Token类别的时候要预留扩展空间比如用枚举类型定义TokenType后面加新类别只需在枚举里追加一项。第二状态转换逻辑。词法分析的核心机制是有限状态自动机DFA你需要根据输入的字符决定当前处于什么状态、下一个字符跳转到什么状态。这部分需要画状态转换图把每个Token的识别路径理清楚。比如识别标识符时首字符必须是字母或下划线后续字符可以是字母、数字或下划线一旦遇到其他字符就说明标识符结束该回退一个字符进入下一轮识别。第三错误处理机制。这是不少同学容易忽略的点。实际源代码中不可避免会出现非法字符或非法组合比如、$这种不在任何规则中的符号或者像123abc这种情况。一个健壮的分析器要能捕获这些非法Token报告出错位置行号、列号和出错原因并且能够恢复继续分析而不是一遇错误就崩溃退出。说句实在话如果只是照着网上的代码抄一遍半天就能“做完”。但那样的话实验报告里“设计思路”一栏你会写得很痛苦答辩时老师随便问几个细节你就露馅了。所以建议还是从原理入手一步步自己推演清楚。2. 词法规则设计从正则到状态图的落地2.1 各类Token的模式描述词法规则的本质是正则表达式。以C语言子集为例各类Token的模式可以这样描述关键字if、else、while、for、int、char、float、return、void等。这些是保留字不能作为标识符使用。标识符字母或下划线开头后续为字母、数字或下划线模式记为[A-Za-z_][A-Za-z0-9_]*。整型常量[0-9]支持十进制进阶版可以要求支持十六进制0x[0-9A-Fa-f]。实型常量[0-9].[0-9]即小数形式进阶版可要求支持科学计数法。运算符单字符如 - * /双字符如 -- - ! ||。界符( ) { } [ ] ; ,等。这里有个经典的优先级问题关键字和标识符的模式都是字母序列那么int到底算关键字还是标识符词法分析器不应针对每个关键字单独建立一条识别路径正确做法是统一按标识符规则识别识别完整串后再查关键字表如果在表中命中则归类为关键字否则就是标识符。这样处理和扩展新关键字都更灵活。2.2 状态图驱动的识别流程把上述模式转化为状态图是实验设计中最费脑子的部分。以标识符识别为例其状态转换逻辑为初始状态为START读入一个字母或下划线进入ID状态在ID状态下继续读入字母、数字或下划线则留在ID状态读到其他字符则标识符结束返回Token同时把当前字符放回输入流即“回退一个字符”。再比如双字符运算符的识别处理起来更精细一些。读到!不能直接断定就是!还要往前看一位如果是就是!如果不是那!本身就是一个非法Token或单字符运算符。这种“超前查看lookahead 回退”的机制是词法分析器实现中最重要的技巧之一代码里通常用一个全局变量lookaheadChar来缓存那位“多读的”字符。我把各类Token的状态识别路径整理成了一个表方便在编码前核对逻辑Token类型起始字符后续字符结束条件特殊处理标识符/关键字字母或_字母、数字、_遇到其他字符回退一位查关键字表整型常量数字数字遇到非数字回退一位实型常量数字数字和一个小数点遇到非数字且非小数点注意小数点只能出现一次双字符运算符运算符首符只判断下一位下一位匹配则双字符不匹配则回退注释/*或/匹配到结束符忽略中间所有字符2.3 状态图驱动的识别流程这里多说一句实型常量识别的一个坑。如果代码用状态转移实现当读到数字串后的小数点并不能确定这个点一定是小数点——因为还可能是1.后面没有数字的非法形式或者是像1..2这种错误输入。所以进入实型常量识别状态后一定还要检查小数点后至少有一位数字否则要报错。我在第一次实现时没注意这个边界测试用例float x 1.;的时候程序直接把.当成了另一个Token结果后面语法分析直接崩了。注释跳过也是必须考虑的功能。C风格的注释有//行注释和/*...*/块注释两种块注释可能跨越多行所以分析器在跳过注释时需要维护行号计数。不少同学的实现中行号统计错误根源就是注释跨行时忘了对行号做lineNo处理。3. 代码实现与核心流程讲解3.1 整体框架搭建这个实验用什么语言实现没有硬性规定C/C和Java都是常见选择。从北邮实验的传统来看最早几届学长的版本多用C语言实现但用C的面向对象思路来管理会清晰很多。我自己采用的是C实现核心类Lexer负责字符流读取和Token输出Token结构体描述一个词法单元。下面给出一个完整的可运行版本基于常见实践的补充代码不长但是把这个实验的核心逻辑都覆盖了#include iostream #include fstream #include string #include vector #include unordered_set using namespace std; // Token类型定义 enum TokenType { KEYWORD, // 关键字 IDENTIFIER, // 标识符 INT_CONST, // 整型常量 REAL_CONST, // 实型常量 OPERATOR, // 运算符 DELIMITER, // 界符 ERROR_TOKEN, // 非法Token END_OF_FILE // 文件结束 }; // Token结构体 struct Token { TokenType type; string lexeme; // 单词原文 int line; // 行号 int column; // 列号 Token(TokenType t, string str, int l, int c) : type(t), lexeme(str), line(l), column(c) {} }; class Lexer { private: string input; // 源程序内容 int pos; // 当前扫描位置 int line; // 当前行号 int column; // 当前列号 char lookahead; // 超前缓存字符 bool hasLookahead; // 是否已有缓存字符 unordered_setstring keywordTable; // 关键字表 // 读取下一个字符维护行列号 char getNextChar() { if (hasLookahead) { hasLookahead false; return lookahead; } if (pos input.length()) return \0; // EOF标记 char c input[pos]; if (c \n) { line; column 1; } else { column; } return c; } // 回退一个字符 void ungetChar(char c) { lookahead c; hasLookahead true; } public: Lexer(const string source) : input(source), pos(0), line(1), column(1), hasLookahead(false) { // 初始化关键字表 string keywords[] {int, char, float, double, void, if, else, while, for, return}; for (auto kw : keywords) keywordTable.insert(kw); } // 获取下一个Token Token getNextToken() { char c getNextChar(); // 跳过空白和注释 while (c || c \t || c \n || c \r) { c getNextChar(); } // 文件结束 if (c \0) { return Token(END_OF_FILE, EOF, line, column); } int startLine line, startCol column - 1; // 标识符或关键字 if (isalpha(c) || c _) { string lexeme; while (isalnum(c) || c _) { lexeme c; c getNextChar(); } ungetChar(c); // 回退多读的字符 if (keywordTable.count(lexeme) 0) { return Token(KEYWORD, lexeme, startLine, startCol); } else { return Token(IDENTIFIER, lexeme, startLine, startCol); } } // 数字常量整型或实型 if (isdigit(c)) { string lexeme; while (isdigit(c)) { lexeme c; c getNextChar(); } // 判断是否为实型常量 if (c . isdigit(getNextChar())) { lexeme .; // 注意上面getNextChar已经多读了一位需要调整逻辑 c getNextChar(); // 读小数点后的第一位数字 while (isdigit(c)) { lexeme c; c getNextChar(); } ungetChar(c); return Token(REAL_CONST, lexeme, startLine, startCol); } else { ungetChar(c); return Token(INT_CONST, lexeme, startLine, startCol); } } // 运算符和界符这里列出主要部分 switch (c) { case : if (getNextChar() ) return Token(OPERATOR, , startLine, startCol); if (lookahead ) { lookahead 0; hasLookahead false; } else ungetChar(lookahead); // 简化处理判断是否有缓存字符 return Token(OPERATOR, , startLine, startCol); case : if (getNextChar() ) return Token(OPERATOR, , startLine, startCol); ungetChar(lookahead); return Token(OPERATOR, , startLine, startCol); case (: return Token(DELIMITER, (, startLine, startCol); case ): return Token(DELIMITER, ), startLine, startCol); case ;: return Token(DELIMITER, ;, startLine, startCol); // 其他运算符和界符处理类似不再一一列出 } // 无法识别的非法字符 string invalid(1, c); return Token(ERROR_TOKEN, invalid, startLine, startCol); } };这段代码为了篇幅做了精简实际实验时你需要把运算符分支补齐。注意看标识符识别那段的核心逻辑读到字母就进入循环直到遇到非字母数字字符才停下然后把最后读到的那个字符回退到输入流这样下一个Token的识别就能从正确位置开始。3.2 主程序调用与被处理数据的组织主程序要做的事情非常直接读入源文件、循环调用getNextToken()输出Token序列。输出格式建议包含Token类型、单词内容、行号、列号这样方便调试和验证。下面给出主函数框架int main(int argc, char* argv[]) { if (argc 2) { cerr 使用方法 argv[0] 源代码文件路径 endl; return 1; } ifstream fin(argv[1]); if (!fin.is_open()) { cerr 无法打开源文件 endl; return 1; } string source((istreambuf_iteratorchar(fin)), istreambuf_iteratorchar()); fin.close(); Lexer lexer(source); Token tok lexer.getNextToken(); while (tok.type ! END_OF_FILE) { cout tokenTypeToString(tok.type) , tok.lexeme 位置 tok.line : tok.column endl; tok lexer.getNextToken(); } return 0; }这里tokenTypeToString是一个把枚举类型转成可读字符串的辅助函数自己实现即可。主程序的逻辑越简单越好因为实验报告需要你证明“分析器能跑通各种测试用例”而测试用例的增删改都在这个主函数里操作保持简洁能省很多事。3.3 关于文件组织与报告的补充我注意到这个实验包是一个zip压缩包压缩包内通常包含源码目录、测试用例目录和实验报告文档。收到这种压缩包时建议先通读一遍实验要求文档确认老师对Token类别、输出格式、测试用例数量的具体要求再看参考代码是怎么组织的最后基于参考代码自己重写或改造。直接提交原封不动的代码风险很大因为老师手头上很可能就有这个标准包雷同程度一眼就能看出来。压缩包内的实验报告一般有固定的模板重点要写的部分包括设计思路状态图怎么画的、关键代码分析、测试用例设计与结果展示、实验中遇到的问题与解决办法。后两个部分是加分点一定要认真写很多同学栽在“测试用例太少”上只测了一个int a1;就完事老师问“你测过注释嵌套吗测过非法字符吗”直接哑口无言。4. 测试用例设计与验证过程4.1 覆盖核心功能的用例集测试用例怎么设计直接反映你对实验要求的理解深度。我当时的策略是至少准备五个程序文件分别覆盖常规代码、异常输入、边界情况和组合情况。这里给出一套可直接复现的测试矩阵用例文件测试内容期望输出test1.c变量定义与赋值语句含关键字、标识符、运算符、界符、整型常量全部正确识别test2.c浮点数运算含实型常量REAL_CONST正确输出test3.c算术运算与自增自减含、--、、等双字符运算符双字符运算符完整匹配test4.c非法输入含、$、123abc、1..2ERROR_TOKEN被捕获且程序不崩溃test5.c块注释跨多行、行注释、注释中的关键字注释被跳过行号统计正确写测试用例文件时要注意别把多个功能塞进一个文件里。一个用例文件最好只侧重一类场景这样一旦出现问题你能迅速定位是哪个识别逻辑有bug。4.2 输出验证与结果分析拿test1.c来说假设输入文件内容如下int a 10; float b 3.14; if (a b) printf(hello);期望的输出Token序列应该包含关键字int、标识符a、运算符、整型常量10、界符;、关键字float、标识符b、运算符、实型常量3.14、关键字if、界符(、标识符a、运算符、标识符b、界符)等。我在验证时发现一个很有意思的问题printf应该被识别为标识符但很多同学会把print、printf当成关键字。实际上除非实验要求中明确列出了printf作为关键字否则它就只是一个普通标识符。这个细节成了不少老师喜欢提问的点你在设计关键字表时务必以实验要求文档中给出的关键字列表为准。结果分析部分要做的不只是看输出对不对还要检查行号和列号的准确性。比如块注释跨行后后续Token的行号是否仍然正确这是实现中很容易出错的细节。4.3 辅助调试技巧词法分析器的调试核心就是追踪状态转换。如果你复现时遇到问题我建议在代码临时加上调试输出打印每个读入的字符、当前状态、是否发生回退。比如在getNextChar()和ungetChar()里各加一行cerr 读取: c 位置: line : column endl;就能直观看到字符流是怎么被消费的。有一个实用技巧是准备一个“最小复现案例”。比如双字符运算符识别不对就构造一个只包含 三种情况的小文件反复测试这三个Token的输出逻辑正确后再扩展到完整算符集合。逐段验证比一次性跑大文件然后对着几千行输出发呆要高效得多。5. 常见问题与排查技巧实录5.1 经典Bug盘点与根因分析我把自己实验过程中踩过的坑和周围同学常遇到的问题做了个汇总问题现象根因解决办法标识符与关键字识别混淆没有先识别完整串再查关键字表统一按标识符规则识别完成后再查关键字表最后一行Token丢失文件末尾没有处理EOF字符确保getNextChar()在读到文件末尾时返回结束标记主循环正确识别行号统计不准块注释跨行时没有维护行号在跳过注释的循环中遇到\n执行lineNo死循环状态转移图中非法字符无法跳转确保每个状态都有默认跳转分支遇到非法输入能退出当前识别流程123abc被识别成两个Token数字识别完毕后未检查后一位是否为字母数字串后收尾时若后一位是字母或下划线应整体报错为非法Token第一行那个问题是最常见的。很多同学写了一个isKeyword()函数在读取到第一个字母时就判断i i next f是不是if这种“边读边判”的方法把逻辑搞复杂了遇到ifx这种标识符就会产生误判。正确的方法永远是把完整的字母序列收集完再统一查表。123abc也是一个高频考点。C语言的词法规则要求数字后直接跟字母属于非法词素。我见过有两种处理方式一种是把123abc整体判为ERROR_TOKEN另一种是把123识别为整型常量把abc识别为标识符。从严格词法分析的角度看字符串123abc没法被任何一条正则完整匹配所以应整体报错把它拆开反而是掩盖了源代码错误。5.2 巧用文件重定向提升调试效率如果你用的是命令行工具测试时没必要每次手动输入测试用例。Linux或macOS下用重定向即可./lexer test1.cWindows的PowerShell里可以用Get-Content test1.c | .\lexer.exe。另外可以把输出同时重定向到文件中方便对比不同版本的输出差异./lexer test1.c output1.txt。还有一个比较“笨”但在截图上很有效的技巧测试时准备一个对照表左边是代码原文每一行右边是对应Token序列。这个截图放到实验报告里老师一眼就能看出你确实做了充分测试。5.3 边界情况与进阶考虑的取舍关于字符回退机制有个考点值得专门说回退的是字符还是整个Token显然只回退字符不能回退Token。这背后的含义是词法分析器对字符流的消费是单向的一旦一个Token被识别完成它就被输出了不会被放回输入流。这就是为什么识别标识符时要小心控制“超前读了一位”那位字符必须无条件地归还给输入流否则会漏掉Token。扩展要求方面如果学有余力可以加上以下功能处理转义字符如\n、\t、识别字符串常量、支持十六进制与八进制整型常量。这些在实验报告中作为“进阶实现”写出来往往能成为加分项。以字符串常量为例识别逻辑和注释跳过很像但要处理转义字符不能简单遇到就结束否则源代码中出现\会直接识别错误。我有一次在测试字符串时这个边界翻车印象特别深。6. 一次真实测试会话的完整复盘为了让大家更直观地了解整个实验的验收过程我把当时做的一次完整测试会话复盘在这里。测试输入是上面提到的test4.c文件内容故意写得很刁钻int main() { int a 10; float b 3.14; int c 123abc; /* 非法数字后直接跟字母 */ int d 1..2; /* 非法小数点后不能再跟小数点 */ char* s hello; // 字符串常量若扩展支持 return 0; }运行词法分析器后截取关键输出如下KEYWORD, int 位置1:1 IDENTIFIER, main 位置1:5 DELIMITER, ( 位置1:9 DELIMITER, ) 位置1:10 DELIMITER, { 位置1:12 KEYWORD, int 位置2:5 IDENTIFIER, a 位置2:9 OPERATOR, 位置2:11 INT_CONST, 10 位置2:13 DELIMITER, ; 位置2:15 KEYWORD, float 位置3:5 ... ERROR_TOKEN, 位置6:3 ERROR_TOKEN, $ 位置6:5注意第5行的123abc在严格模式下应输出一个ERROR_TOKEN但由于我在状态转移中数字识别规则是“最多识别连续数字”所以在实际运行中可能被拆成INT_CONST(123)和IDENTIFIER(abc)。如果在你的实验要求中这种情况允许拆开处理那还好如果实验文档明确规定数字后接字母是非法的你就要额外加一个检测逻辑。我当时把它识别成了两个Token后来对照实验文档发现要求必须报错于是专门加了一条检查数字串识别结束后如果后续字符是字母或下划线则回退回去并返回ERROR_TOKEN。和$这种字符在没有定义的情况下直接落入最后的default分支输出ERROR_TOKEN这是最理想的行为——识别出错但没有崩溃而且行号列号都正确。那次测试暴露的问题主要集中在实型常量边界和注释跨行的行号统计上。调试过程中我把行号输出和IDE里看到的行号逐行对照才发现/*块注释后的第一个Token行号比预期少了一行原因就是跳过注释的循环里少了\n的行号累加。这样的问题如果不做完整测试靠眼睛看代码是很难发现的。7. 扩展思考实验之后的下一步词法分析器实验虽然在编译器课程中属于“最简单”的环节但它是理解整个编译流程的窗口。做完这个实验后建议顺着两个方向深挖一是尝试为本次实验定义的Token类别补充一个简单的语法分析器递归下降或LR(0)都行这样你会立刻理解为什么词法分析要输出二元组而不是原始字符串二是把分析器适配到更完整的语言子集比如加入for和while循环语句的Token模式观察新增语法的成本集中在什么地方。这些扩展做下来你对“编译器的前端到底做了什么”会有质的理解飞跃。从课程学习角度来说词法分析器也是少数几个能在一周之内从零写完并验收通过的实验模块认真啃下来非常划算。本文还有配套的精品资源点击获取