我大学第一次翻开《编译原理》教材的时候说实话是被吓住的。前面几章全是正则、状态机、文法推导这些东西光看定义完全不知道学了能干嘛。直到自己动手写了一个词法分析器回头再看教材才真正明白编译器第一站到底在做什么。词法分析是编译原理里最适合入门、也最容易“做出东西”的一个模块它把一串毫无结构的字符流变成一个个有明确含义的单词Token是整个编译器的“前置车间”。这篇博文我打算用一种“学长带学弟”的方式把词法分析从原理到代码完整过一遍重点讲清楚三件事词法分析为什么非要单独拆出来、手工实现时怎么设计状态机、以及实际写代码会遇到哪些教材里不会写的坑。无论你是在赶编译原理课程实验还是在准备面试或者纯粹想给自己写的IDE插件补点底层知识这篇文章应该都能让你少走弯路。为了照顾不同基础的同学我会先用生活化的类比讲原理再给出可以直接跑起来的C语言实现最后聊一聊Flex这些工具和面试考点保证你合上文章就能上手。1. 词法分析到底在做什么先搞清楚它凭什么站在编译器第一站很多教材喜欢一上来就丢出“词法分析是编译过程的第一阶段”这句定义然后开始讲正则和DFA。我不太推荐这种顺序因为你对“它到底在解决什么问题”没有体感后面的状态机理论就是空中楼阁。所以我先用一个扎心的场景把它讲透。1.1 从字符流变成Token流像给一句话做分词想象你收到一封没有空格、没有标点的英文短信“iamveryhappy”。正常人一看就知道它应该被拆成“I am very happy”但计算机没有这种常识它只会一个字符一个字符地读。词法分析器干的事情本质上就是给字符串做“分词”它拿着源代码里的一大串字符按照语言规则把它们切成一个个有意义的“单词”。在程序语言里这些“单词”我们叫Token常见的类型有关键字如int、return、if、标识符变量名、函数名、数字常量、运算符、、、分隔符{、}、;等等。词法分析器每识别出一个Token就把它编号分类再附上必要的信息返回给语法分析器。比如源代码里有这么一行int total price * 3;词法分析器会依次吐出来这些Token关键字 int 标识符 total 运算符 标识符 price 运算符 * 数字常量 3 分隔符 ;你看一个字符串被“分词”后就从线性字符序列变成了一串有类型的Token流。这就像中文里没有空格也能断句一样编译器靠的就是词法规则来“断词”。1.2 为什么非要单独拆一层词法分析三个足够硬核的理由有些同学会问语法分析不是也能直接处理字符吗为什么非要先搞一层词法分析出来这个问题我当年也困惑过后来做完整棵语法树之后才想明白至少有三个很实际的理由。第一是降低复杂度。语法分析器需要的语法单位是“单词”而不是单个字符。如果让语法分析器直接面对字符流那么每个语法规则都要处理“遇到字母怎么办、遇到数字怎么办”这种细节文法会变得极其臃肿。把“字符流转单词流”这件相对独立和机械的事情抽出来语法分析规则就会清爽很多。这和你写代码时把工具函数抽到公共模块里一个道理。第二是方便压缩无关信息。源代码里有大量对语义无关的空白、换行和注释比如两个关键字之间有多少空格并不影响程序含义。词法分析器在扫描过程中可以顺手把这些东西丢掉只把“真的算数”的Token交给下一阶段。如果这个环节被塞进语法分析里空格判断逻辑会在每个语法规则的匹配过程中反复出现浪费空间和时间。第三是便于优化和复用。词法规则自身具备很强的正则结构天然适合用状态机去高效匹配把它独立出来之后可以单独做性能优化比如用查表代替逐字符判断甚至可以单独替换成自动生成工具如Flex产出的代码。我在后面会详细讲Flex你会看到这一步单独拆出来有多大的实用价值。2. 手工实现前的核心准备正则表达式、DFA与状态机的直觉理解如果你已经理解了“把字符流变成Token流”这个目标接下来就该动手设计实现方案了。教材上正规路线通常是先写出描述单词的正则表达式再把它转成NFA再转成DFA最后根据DFA写程序。这个流程理论严谨但第一次做实验的同学很容易被NFA、DFA的概念劝退。我的建议是如果你只是想完成一个能跑的词法分析器可以不那么严格地走“正则→NFA→DFA→代码”的全流程直接根据对Token模式的直觉画出状态转换图再照着写代码即可。但你至少要懂正则表达和状态机的基本逻辑否则代码会写得毫无章法。2.1 正则表达式描述单词的“模板语言”正则表达式简称regex是用来定义一个字符串集合的表达式语言。在词法分析里我们用它来精确描述“哪些字符串属于同一类Token”。比如标识符[a-zA-Z_][a-zA-Z0-9_]*整数常量[0-9]浮点数常量[0-9].[0-9]*这些表达式的含义很简单方括号表示“取中括号内的任意一个字符”星号表示“前面的部分重复零次或任意多次”加号表示“前面的部分至少出现一次”。它就像给字符串画了一块模板——只要字符串能套进这块模板就属于对应Token类型。有人可能会问我都直接写代码了还要正则干什么其实正则最大的作用是让你“把需求想清楚”。比如描述一个标识符时你必须明确第一个字符能不能是数字能不能是下划线能不能包含$这些细节写代码时当然能处理但如果不先整理成正则形式边写边想很容易漏掉边界情况。更关键的是很多自动生成工具Flex等直接就是让你写正则的你连核心逻辑都不用手写。2.2 从正则到状态机状态转移是最容易理解的手写方案状态机有限自动机是词法分析器运行时的“大脑”。你可以把它理解成一张地图你站在某个状态节点上读入一个字符根据字符决定跳到哪个状态同时可能“输出”一个Token。教材里会讲NFA和DFA的区别NFA允许一个状态遇到同一个字符跳到多个后继状态带不确定性DFA则是“一字符一状态”完全确定。实际写代码时我们当然希望用DFA因为它天然适合用switch-case或查表实现。如果是手写小规模词法分析器我强烈建议直接画一张状态转换图。比如识别整数的状态图可以这样设计状态0开始如果读到数字进入状态1状态1正在读数字继续读到数字留在状态1读到非数字说明数字结束输出Token回到开始状态识别标识符也类似从开始状态读到字母或下划线进入“标识符状态”在这个状态里继续读字母、数字、下划线都留在原地读非法字符就结束。把这些小状态图拼在一起再加上错误处理就是一个完整的词法分析器骨架。你不需要真的把整个状态机做成大的二维表用几个小函数配合当前“扫描模式”就能写清楚。2.3 最长匹配与错误处理动手前必须想明白的两个原则我在实际写代码时发现有两个设计原则如果提前想清楚后面能少改很多代码。第一个是最长匹配原则。比如源码里出现很明显应该被识别成一个“小于等于号”而不是先识别成小于号再识别成等号。词法分析器在扫描时要尽量“多吃”字符只要后续字符还属于当前Token的合法延续就会继续读下去直到读到一个无法延续的字符才停下来。这也是教材里总强调“词法分析要尽可能长地匹配一个Token”的原因。第二个是错误恢复策略。词法分析遇到非法字符比如出现在非字符串位置怎么办一般有两种做法直接报错终止或者跳过非法字符指出出错位置再继续扫下去。对于实验性质的编译器我倾向于采用后者因为一次运行能报出更多错误调试体验更好。但这需要你时刻记录当前字符的行号和列号否则报错信息根本没法定位。这个小细节很多人忽略觉得“反正只要识别Token就行”等真做语法分析回去查错的时候才发现没写行号有多痛苦。3. 完整实现手写一个C语言词法分析器从Token定义到主控循环理论讲了不少现在进入真正硬核的部分——写代码。我以C语言子集为例完整实现一个能识别标识符、关键字、整数、运算符和分隔符的词法分析器。选C语言是因为《编译原理》课程的经典教材普遍使用C而且C语言没有内置字典、列表这些高级结构反而更能看清算法本身的骨架。如果你用的是Java或Python思路完全一样只是容器和字符串处理API不同。3.1 Token体系设计类型枚举、属性值与符号表的取舍写词法分析器第一步不是写扫描逻辑而是先定义“Token长什么样”。在C语言里我习惯用一个枚举定义所有Token类型再用一个结构体保存类型和值typedef enum { TOKEN_EOF, // 文件结束 TOKEN_KEYWORD, // 关键字 int, return, if ... TOKEN_IDENT, // 标识符 TOKEN_NUMBER, // 数字常量 TOKEN_OP, // 运算符 - * / ... TOKEN_DELIM, // 分隔符 ( ) { } ; , TOKEN_ERROR // 非法字符 } TokenType; typedef struct { TokenType type; char lexeme[64]; // 单词原文比如变量名或数字字符串 int line; // 所在行号后面报错要用 } Token;这一步看起来简单但有两个点值得注意。第一要不要把关键字单独列成一种TokenType很多初学者会把关键字单独列出来比如TOKEN_INT、TOKEN_IF。这样做不是不行但会让Token类型数量膨胀而且后面语法分析时要做大量“是不是这个特定关键字”的判断直接用TOKEN_KEYWORD加lexeme文本判断更灵活。所以我更推荐的做法是词法分析阶段先按“标识符”规则把单词扫出来然后查一张关键字表如果命中就标记为TOKEN_KEYWORD否则就是普通标识符。第二Token里到底要不要带值对于数字常量光有lexeme字符串是不够的语法分析阶段需要数值。所以我在结构体里额外存了一个value字段typedef struct { TokenType type; char lexeme[64]; int value; // 仅当type为TOKEN_NUMBER时有效 int line; } Token;如果你后面要做更完整的编译器最好再引入符号表Symbol Table把变量名字符串映射到一个ID这样在语法分析和代码生成阶段不用反复比较字符串直接比较整型ID即可。符号表是另一个庞大主题做词法分析实验时可以先不实现但你要预留这个意识——Token里真正值得长期保存的是“类型位置”而不是一长串文本。3.2 关键函数实现识别标识符、数字、运算符的写法接下来是实现几个核心识别函数。我建议把它们按类别拆分每类一个函数主循环里通过首字符分流。这样结构清晰也方便后面对某类Token单独做优化。识别标识符和关键字的函数思路是先用字母或下划线开头然后尽量吃掉后续的字母、数字、下划线最后查关键字表int is_alpha(char c) { return (c a c z) || (c A c Z) || c _; } int is_digit(char c) { return c 0 c 9; } Token scan_ident_or_keyword(char first, int line) { char buf[64]; int len 0; buf[len] first; char c get_next_char(); // 从输入流读下一个字符 while (is_alpha(c) || is_digit(c)) { if (len 63) buf[len] c; c get_next_char(); } buf[len] \0; unget_char(c); // 多读的那个字符要放回去 Token t; if (is_keyword(buf)) t.type TOKEN_KEYWORD; else t.type TOKEN_IDENT; strcpy(t.lexeme, buf); t.line line; return t; }这段代码里有几个细节容易踩坑先给你提个醒。一是unget_char(c)非常重要当你读到“不是标识符一部分”的字符时这个字符其实是下一个Token的开头必须退回到输入流里否则下一个Token会丢字符。二是缓冲区长度要限制别让超长标识符把数组写爆更稳妥的做法是动态扩容但实验代码里用固定长度加截断就行。三是is_keyword(buf)本质上就是查表表可以用字符串数组实现const char *keywords[] {int, if, else, while, return, void, 0}; int is_keyword(const char *s) { for (int i 0; keywords[i] ! 0; i) { if (strcmp(keywords[i], s) 0) return 1; } return 0; }识别整数常量的函数也类似但要处理多位数以及可能的浮点数。如果你们实验只要求整数可以只处理[0-9]如果要求支持浮点数就要在数字串后面处理小数点甚至指数部分。我建议先做整数做完了再扩展别一上来就追求完整。运算符的识别稍微特殊一点因为它有单字符和多字符的区分。比如和、和。一个典型处理方式是先读第一个字符再做预判——如果第一个字符可能是某类多字符运算符的开头就再读第二个字符看能不能配成更长的合法运算符如果不能就把第二个字符退回去。下面是一个粗略的写法Token scan_operator_or_delim(char c, int line) { Token t; t.line line; if (c ) { char next_c get_next_char(); if (next_c ) { strcpy(t.lexeme, ); t.type TOKEN_OP; } else { unget_char(next_c); strcpy(t.lexeme, ); t.type TOKEN_OP; } return t; } // 其他运算符类似处理 - * / ! etc. if (c ; || c , || c ( || c ) || c { || c }) { t.type TOKEN_DELIM; t.lexeme[0] c; t.lexeme[1] \0; return t; } t.type TOKEN_ERROR; t.lexeme[0] c; t.lexeme[1] \0; return t; }这种“多读一个字符再决定”的策略本质上是把最长匹配原则落实到了代码里。你看手工实现时根本没有“回头重扫”的复杂操作只需要维护好“已读字符的回退机制”即可。3.3 主控制循环与代码骨架把零散的规则串起来各个识别函数写好之后主控循环就很简单了不断读字符根据首字符类型分发到对应识别函数直到读到文件结束符EOF为止。我把骨架整理成下面这样并加入了空白和注释跳过逻辑Token get_token() { Token t; char c; while (1) { c get_next_char(); if (c EOF) { t.type TOKEN_EOF; t.lexeme[0] \0; return t; } if (c || c \t || c \n) { continue; // 空白字符直接丢弃不必产生Token } // 这里可以加如果c /还要看下一个字符是否是/或*决定是否进入注释处理 if (is_alpha(c)) { return scan_ident_or_keyword(c, current_line); } if (is_digit(c)) { return scan_number(c, current_line); } if (c || c - || c * || c / || c || c || c || c !) { return scan_operator_or_delim(c, current_line); } if (c ( || c ) || c { || c } || c ; || c ,) { return scan_delim(c, current_line); } t.type TOKEN_ERROR; t.lexeme[0] c; t.lexeme[1] \0; t.line current_line; return t; } }当get_token()返回的Token类型是TOKEN_EOF时整个词法分析就结束了。这里有几个工程细节请你务必注意。第一current_line变量在读到\n时要在主循环里同步递增否则你所有的行号都会停留在初始值。第二注释在词法分析阶段通常被整体跳过但跳过的过程中依然要更新行号多行注释尤其要小心。第三错误Token返回后主程序可以打印“行号非法字符”然后继续调用get_token()这样才能实现前面说的错误恢复策略。3.4 与语法分析器的接口约定nextToken模式与回调模式词法分析和语法分析怎么衔接这是实验里很容易被忽视的一环。常见的有两种方式。一种是我们上面这种“主循环驱动”模式语法分析器需要Token时就调用get_token()词法分析器返回下一个Token。这种接口非常自然递归下降语法分析器里直接写Token t get_token();就行。另一种是回调模式词法分析器扫描整个文件每识别一个Token就调用一个回调函数处理它。这种模式比较适合做代码高亮、静态检查这种一次性遍历场景但不适合语法分析因为语法分析器是“按需取Token”的不是一次性全拿完。如果以后你在其他项目里看到这两种模式并存它们其实是针对不同应用场景的设计权衡。4. 踩坑实录与调试技巧我手写词法分析器时犯过的那些错这部分是我最想写给你的因为教材上不会讲这些。很多问题看起来“不就是一个字符比对吗”实际跑起来却会卡你两三个小时。我把自己的踩坑经历按高频程度整理出来。4.1 关键字和标识符的“抢戏”问题顺序错了全部乱套我第一次写词法分析器时曾经愚蠢地在主循环里先判断if (c i)然后试图匹配整段int。导致输入里所有以i开头的变量比如index都被错误识别成关键字。正确的做法是先把整个单词按“标识符”扫完得到完整字符串后再用查表判断它到底是不是关键字。也就是说关键字识别是“标识符识别完成之后的一个查表动作”而不是在字符级别提前分流。这个顺序一错后面语法分析就会收到一堆错误的Token。我还见过另一种反模式把关键字表塞在一个很大的if-else里比如if (strcmp(buf, int) 0) ... else if (strcmp(buf, if) 0) ...。这样写不仅难看而且每次比较都逐字符扫描性能也很差。实验规模无所谓但我建议循序表或哈希表为以后处理更多关键字做准备。4.2 多读一个字符的回退问题ungetc你真的用对了吗很多词法分析器都有预读需求。比如判断是不是的一部分必须读下一个字符才能决定。最自然的做法就是多读一个字符再放回去C标准库提供ungetc(c, fp)。但坑在于ungetc并不保证一定能放回任意多个字符。不同平台对“回退缓冲区大小”的实现不一样有的只允许一次回退一个字符。如果你在代码里循环回退多个字符某些环境下可能莫名其妙丢数据。为了避免这个问题我建议不要依赖库函数的多字符回退而是在自己的词法分析器里维护一个私有的“回退缓冲区”或“超前读取指针”。你完全可以一次性把整个文件读进内存然后用一个current指针和一个lookahead指针来管理读取与回退回退就等于把指针往回挪几下。这样做既绕开了ungetc的限制又让整个扫描过程更可控。还有个小技巧如果你实现了“只看一眼”的预读可以用一个pending_char变量暂存而不是真的把指针移回代码会更清晰。4.3 注释和字符串被错误截断行号更新不到位排查到崩溃我在实现跳过//单行注释和/* */多行注释时踩过一个特别隐蔽的坑。当扫描到/*进入注释状态后如果一直读到*/才退出中途一旦遇到文件结束EOF说明注释没有闭合应该报“未结束注释”的错误。但很多同学的代码在遇到EOF时直接返回导致这个错误被吞掉后面语法分析拿到一堆莫名其妙的Token。经验是处理注释时一定要单独维护一个“注释内部行号计数器”。不要在注释外的主循环里更新行号而是写一个skip_comment()函数在里面每读到一个换行符就更新行号。这样单行注释、多行注释、以及注释结束后回到主循环行号都不会乱。否则你就会遇到“明明在第20行报错却提示第5行”这种离奇问题。4.4 错误恢复不成体系报完错程序就崩溃谈不上调试效率最后一个坑属于全局设计。如果你在词法分析阶段遇到了非法字符直接调用exit(1)退出程序那么用户每次运行只能知道一个错误改完再跑才能看到下一个。这在小程序里还能忍到了几百行的源代码里就是灾难。所以我会建议你设计一个简单的错误恢复机制遇到非法字符时打印包含行号和列号的错误信息跳过当前非法字符继续扫描。列号的维护也不难在扫描时记录“当前行第几列”就行每次读到换行列号归零其他时候递增。当然错误恢复不是无脑跳过所有错误有些错误如未闭合注释后续很可能导致整段Token丢失恢复意义有限。但无论如何保留一个可用的错误信息格式比如[词法错误] 第10行第5列非法字符 对你的调试体验会有质的提升。5. 实验之后面试高频考点与后续拓展方向如果你把上面的代码跑通词法分析实验就算完成了。但我觉得这篇文章还应该多走一步把这些知识和面试、和真实工程工具串起来。毕竟很多同学学编译原理是为了应付面试或者在以后遇到相关任务时能快速上手。5.1 面试官最爱问的几个词法分析问题看看你能答上来几个面试里关于词法分析的问题通常不会让你现场写完整代码但非常喜欢考察概念和设计取舍。我整理了几个高频问题你可以拿来检验自己问题1词法分析和语法分析为什么要分开这个我在前面已经讲了三个理由回答时能说出“降低复杂度、过滤无关信息、逻辑独立可复用”这几层基本就能过关。问题2关键字在词法分析阶段是怎么识别出来的很多人会答“在识别标识符的同时特判关键字”这个方向对。但要答得更好你需要强调“先按标识符规则扫完整个单词再查关键字表决定类型”而不是在扫描过程中逐个字符匹配关键字。问题3什么是最长匹配原则为什么要用它简单说就是要尽可能多地读入字符使得当前词法单元最长。比如输入12abc有的语言会识别成数字12再加标识符abc有的语言如C/C会直接报错因为“数字串后紧跟字母”不是一个合法的数字常量。这里能扯出“不同语言有不同的词法规则”说明你真的理解Token的边界取决于语言定义。问题4如果让你实现一个词法分析器你会选择手写还是用Flex为什么这个问题没有标准答案。手写的好处是可控性强、无额外依赖、适合小规模语言Flex这类生成工具的好处是正则表达方便、可维护性好、生成的DFA已经做了最优化处理。我会说自己会先用Flex快速生成一个原型再针对热点路径手写优化这个回答比较务实。问题5手上的词法分析器性能不好应该怎么优化这个问题可以答几个方向用缓冲区批量读入避免频繁I/O用查表二维状态转移表替代大量if-else分支判断对长标识符用字符串哈希快速查关键字表整个扫描过程避免反复分配Token对象等。如果你能结合自己在实验里发现的具体瓶颈来举例会给面试官留下很深的印象。5.2 从手写到Flex自动生成器到底帮你做了什么事很多人学完词法分析课程却不知道业界已经不怎么手写词法分析器了。经典的生成工具是Flex你把词法规则写在.l文件里它就会生成一个完整的C词法分析器。比如下面这段规则片段%% int|if|else|while|return return KEYWORD; [a-zA-Z_][a-zA-Z0-9_]* return IDENT; [0-9] return NUMBER; [ \t\n] ; . return ERROR; %%Flex会把这些正则表达式编译成一个DFA然后生成一个yylex()函数来驱动。你多写的那些状态判断、回退字符逻辑、最长匹配原则它全在幕后替你处理了。这也是为什么我在前面一直强调即使你最终想用Flex也应该先手写一次只有手写过你才真正理解Flex替你省掉了哪些事以及它的正则规则里隐含的优先级机制写在前面规则优先匹配。用Flex写词法分析器的好处是代码简洁、规则清晰、不再需要手工维护状态机细节。它的学习成本也很低只需要搞清楚.l文件的结构、如何编译生成C代码、以及yylex()的返回值是Token类型这几个点。当然Flex生成的代码比较冗长如果你做的是一个教学用的小编译器手写几百行反而更直观。所以工具选型本质上取决于项目规模和维护需求没有绝对优劣。5.3 还能怎么玩词法分析不只是编译器的专利它离我们很近最后我想打破一个认知词法分析不是只能用在编译器里。很多你日常用到的工具核心就是词法分析。代码编辑器里的语法高亮就是先把源码切成Token流再给每种Token类型涂颜色各种代码格式化工具、静态检查工具linter也是靠词法分析把代码结构先摸清楚才能识别出“这个变量根本没被使用”之类的问题日志文件解析器、配置文件解析器同样离不开Tokenizer。我有个朋友曾经接到一个小需求给一个领域专用的公式编辑器写输入校验。他一开始想用正则硬刚发现各种嵌套括号和复杂标识符让正则越写越恐怖。后来换了个思路手写一个几十行的词法分析器把输入拆成Token流校验逻辑立刻清晰了。这件事给我很大启发词法分析是一种极其实用的“文本结构化”思维它不要求你有一个完整的编译器项目才能用上。学会识别出“这里需要把一坨文本变成结构化Token流”是比会写DFA更重要的能力。如果你还想继续深入下一步自然是语法分析递归下降或LR分析、语义分析和中间代码生成。你会发现词法分析器写的质量直接影响语法分析阶段的实现体验——Token类型设计得好语法规则写起来就像搭积木Token类型设计得混乱语法分析代码就会被一堆特判堆满。这也是为什么很多《编译原理》课程实验把词法分析作为第一个大作业它既独立可完成又为后面的庞大系统打底。我在实际带完一遍词法分析实验后最大的体会是看懂状态机原理和写出能跑的状态机程序中间隔着的正是那些细节——字符回退、行号维护、错误恢复、关键字查表顺序。自己动手踩一遍这些坑比背十遍教材公式都管用。最后再分享一个调试小技巧在词法分析阶段写一个dump_tokens(FILE *fp)函数把识别出的每个Token按“行号 | 类型 | 原文”打印成表格。每次改完代码先跑一遍看Token流是否符合预期再去做后续语法分析否则语法树出了问题你根本不知道是词法层还是语法层的锅。