很多人一提起编译原理就发怵尤其“词法分析”这一章总觉得概念又多又绕。我在哈工大上这门课的时候陈鄞老师的课件翻来覆去看了好几遍才真正把词素、模式、Token这套东西理顺。后来自己动手写编译器实验才发现词法分析其实是整个编译器前端里最容易“看着简单、动手翻车”的部分——概念不清后面语法分析、语义分析全是连锁错误。这篇博客就把词法分析的基本概念按我自己的理解重新梳理一遍重点讲哈工大课程里那几个高频考点Token三元组到底是怎么回事、正则定义怎么用、状态转换图和有限自动机的关系、符号表在词法阶段要做什么以及实验里最容易踩的坑。无论你是正在刷教材的本科生、准备期末考试的考生还是想从零手写一个词法分析器的初学者这篇文章都能给你一个可以直接照着用的思路框架。1. 为什么词法分析要先于语法分析先拆单词再造句先看编译器前端的主流程源代码是一串字符经过词法分析变成Token流Token流再交给语法分析器按照文法规则构造语法树。简单说词法分析做的是“拆单词”语法分析做的是“造句”。如果一开始就试图在字符级别上根据文法做解析文法要写的极其复杂效率也低。把词法部分独立出来语法分析器就不用关心空格、注释、制表符这些琐碎的东西了。词法分析器本身是一个不太大的模块输入是字符流输出是Token流。这里的输出不是简单地把单词原样扔出去而是每个Token都要携带足够的信息。哈工大课件里标准说法是Token由名称、属性和词素三部分构成。有些教材写成二元组种别属性值其实含义类似。举个例子源码里写了一句position initial rate * 60;词法分析器会把字符流切成这些词素position标识符赋值运算符initial标识符加号rate标识符*乘号60整数常量;分号注意空格被直接忽略缩进和换行在大多数语言里也不产生TokenPython那种靠缩进定块的语言另说。如果词法分析器足够“聪明”它还可以把回车换行统一映射成行号标记方便后面报错时定位。从编译体系分工来看词法分析器是语法分析器的“替代字母表的预处理设备”。语法分析器所需要的最小单位就是Token如果让语法分析器去处理“i、f、(、空格”这种字符级输入文法规则会爆炸式增长。专门做词法分析还有三个实际好处设计简洁词法规则用正则描述实现用有限自动机非常成熟效率可控一次线性扫描就能完成背靠缓冲区还能进一步加速可移植性好不同语言的词法规则差异大独立成模块方便替换。词法分析器和语法分析器的接口通常是getToken()每次调用返回下一个Token。很多手写词法分析器会把这个函数放在一个循环里直到文件结束返回EOF Token。这个接口看起来简单却决定了后面所有阶段的输入质量所以“Token怎么组织”就成了第一个必须搞清楚的考点。2. 词素、模式与Token三个概念一次分清这部分是哈工大第二章开头最核心的定义也是期末最容易考辨析的点。很多同学一开始记混本质上是因为中文翻译把三个词弄得很接近。词素Lexeme源代码里的真实字符序列。它是活在源码里的具体字符串比如写了一个变量名countcount这个具体的字符序列就是词素。模式Pattern描述一类词素应该长什么样的规则。比如“以字母开头后面跟着字母、数字或下划线”就是一个模式它不关心具体是count还是index。Token语法分析器真正拿到的东西通常是一个“种别属性值”的组合。比如读到count返回Token为标识符, 指向符号表中count条目的指针。用一个生活化类比词素是你手里实实在在的水果模式是“水果店里所有圆形绿色的果子”这种挑选规则Token就是称好重贴好标签的购物袋里面装着水果和它的价格标签。语法分析器不需要知道这个苹果是从哪棵树上摘的只需要知道“这是一个苹果价格两元”。看一段典型代码来理解if (count 10) { ... }这里能切出的词素包括if、count、、10。它们对应的模式和Token如下词素模式Token名称属性if字符串“if”本身IF, -count标识符模式字母开头字母数字ID, “count”关系运算符模式“”GE, -10数字常量模式数字串NUM, 10这里面最容易误解的是关键字。关键字如if、while、return的词素和模式完全一致模式就是那个固定的字符串。词法分析器通常先把这些保留字放进一个预定义表读到一个词素后先查表能匹配上就输出对应关键字的Token否则按标识符处理。正因为关键字模式更具体它必须排在标识符模式之前匹配这也是很多初学者写正则时容易犯的顺序错误。属性值的存在让Token变得灵活。像10这样的数字常量如果Token只含种别NUM语法分析器不知道这个数是多少还得回头去翻源码。所以在词法分析阶段就把词素转换为内部表示比如整数10直接存成二进制数值字符串常量则把字面量拷贝到字符串表。这样一来后续阶段拿着Token就能直接工作。哈工大课件里还给了一个很实用的判断方法模式是集合的描述Token是集合中元素的分类结果。或者说一个模式可以匹配无限多个词素但每个词素只对应一个Token。明白这一点概念题基本就稳了。3. 用正则定义描述词法规则从“直觉规则”到严谨公式词法规则用自然语言描述总是不够精确比如“一个标识符”到底允许哪些字符所以《编译原理》教材里引入了正则表达式。正则表达式的本质是描述一个语言即字符串集合的简洁方式它允许五种基本运算并Uniona|b表示a或b连接Concatenationab表示a后面跟b闭包Closurea*表示a出现0次或多次正闭包a表示a出现1次或多次可选Optionala?表示a出现0次或1次。在此基础上还经常用字符类简写[0-9]等价于0|1|...|9[A-Z]等价于大写字母集合[^a]表示除a以外的任意字符。有了这些运算就能把C语言常见的词法模式写成正则定义。正则定义是一种命名方式先给基本集合起名再层层组合digit - [0-9] letter - [A-Za-z_] id - letter ( letter | digit )* number - digit ( . digit )? ( [eE] ( |- )? digit )? relop - | | | | | 这里id的模式就是“字母或下划线开头后面跟零个或多个字母、数字或下划线”。注意很多学生写id时容易漏掉下划线或者把下划线放在开头虽然语法上无伤大雅但和很多语言的具体关键字冲突规则是有区别的。考试里经常让你判断某个正则表达式能否匹配某个字符串。比如判断a (a|b)* b能否匹配aaab如果熟悉闭包运算应该知道(a|b)*可以匹配aa中间部分整个串是可以匹配的。这类题没有捷径只能把每一步展开来看。这里必须强调一个关键点正则表达式只是对词法模式的描述并不是词法分析器的实现方式。你不能在C语言里直接跑一段正则表达式文本就去识别Token而是要把正则编译成有限自动机或者人工画出状态转换图再写代码去模拟。哈工大课件从正则讲到状态图、再讲到DFA/NFA的转换就是为了解决“描述”到“实现”之间的鸿沟。在构造词法分析器时经常需要把多个正则组合起来。比如标识符的正则和所有关键字的正则构成一个并集匹配时还要遵循两条规则最长匹配如果多个词素都能匹配同一个Token取最长的那个。比如输入和都是合法的运算符但必须识别成。优先匹配如果同一个词素同时匹配多个Token的模式取最先声明的那一个。典型情况是关键字要放在标识符之前。这两条规则在正则定义阶段可能还不觉得重要写状态图、写代码时立刻就会碰到。4. 状态转换图与有限自动机让正则“活”起来手工实现词法分析器最直观的办法是画出状态转换图。状态转换图是个有向图每个结点表示一个状态初态用一个箭头指向终态用双圈或者加粗表示。边上的标签表示当读入某个字符时从当前状态转移到目标状态。以标识符为例状态图可以这样描述状态0初态读取字母或下划线进入状态1状态1读入字母、数字或下划线继续停留在状态1读入其他字符则识别出一个标识符进入接受状态并回退一个字符因为我们多读了一个不属于标识符的字符需要把它还给缓冲区。这里“多读一个字符”是手写词法分析器最经典的一个细节。比如源码是count1读取t之后读到时我们才知道标识符结束了。这时不能把丢掉必须回退缓冲区。教材里叫“向前看一个字符”还有“向前看两个字符”的情况比如和的区分。关系运算符的状态图更加典型。处理时初态读入进入状态A。在状态A如果读到就接受为如果读到其他字符就接受为但也要回退该字符。原因是既可以单独作为运算符也可以是的前缀。状态图虽然简单映射到代码时容易写成if嵌套逻辑一多就乱。我自己的习惯是先用表格把状态转移矩阵列出来再写代码。DFA和NFA的差异也是哈工大课程的必考概念NFA非确定有限自动机允许一个状态对同一输入有多个转移边也允许空转移读入空串就跳转。它更接近人脑对正则的直觉。DFA确定有限自动机)每个状态对每个输入字符最多只有一个转移边实现起来效率更高但状态数可能暴涨。正则转换为DFA的标准路径是Thompson构造法先把正则变成NFA再用子集构造法把NFA转成DFA最后最小化DFA。手写词法分析器时通常不直接走这么重的流程而是人肉模拟DFA的逻辑用变量表示当前状态、用switch或查表驱动转移。下面是一个简化版的手写标识符识别思路Python伪代码能帮助你理解状态机def get_id(source, pos): state 0 start pos while pos len(source): ch source[pos] if state 0: if ch.isalpha() or ch _: state 1 pos 1 else: break elif state 1: if ch.isalnum() or ch _: pos 1 else: break # 回退一个字符反正pos停在第一个不属于id的字符上 return source[start:pos], pos这段代码其实没有真正的“回退”而是让指针停在不可匹配的位置外层调用方就知道“这个字符留给下一个Token用”。实际项目里缓冲区管理往往用两个指针lexemeBegin和forward并且引入前瞻字符处理。手写代码时状态越多越容易出错所以我的建议永远是“先画状态图再写循环”。词法分析器生成器比如flex、lex本质上是把我们写好的正则定义编译成一张驱动表或一段C代码。它们内部已经把NFA转DFA、DFA最小化这些步骤做完了。如果你只是想快速完成一个课程实验用flex能省很多力气但如果你想真正理解词法分析手写一次状态机比调工具更能建立概念。5. 符号表与标识符管理编译器“通讯录”也是考点词法分析读到一个标识符position时只输出一个Token并不能让后续阶段知道这个标识符的类型、作用域、偏移量等信息。这些信息需要一处集中存放的地方这就是符号表。你可以把它想象成编译器的“通讯录”——每个标识符是一个联系人名字是索引后面挂着一堆属性。符号表最常见的字段包括字段说明名字标识符的字符串写法类型整型、浮点、数组、函数等通常在语义分析阶段填写作用域该标识符可见的范围存储位置相对地址、寄存器编号等其他属性数组维度、参数个数、返回类型等这里有个容易混淆的问题词法分析阶段到底该往符号表里填什么按哈工大课程强调的结论词法分析器遇到标识符时应当立即查符号表如果已有同名条目则返回该条目的指针否则新建一个条目至少把名字填进去。至于类型、偏移量等是后面的语法分析和语义分析逐步补充的。所以符号表不是词法分析器的“私有数据结构”而是整个编译器共享的公共设施。为什么要查重因为同一个标识符在同一个作用域里只能有一种属性。如果词法阶段不查重后面语义分析时会发现重复声明但那时已经丢失了“这是同一个名字出现多次”的信息处理起来反而绕路。加上查重之后标识符Token的属性值直接就是一个符号表条目指针后续阶段只需要通过指针访问条目不需要反复比较字符串效率也高。符号表的作用域处理是另一个常见考点。C语言里可以有全局和局部变量甚至嵌套的块。如果用一张哈希表存所有名字同名变量就会冲突。常见方案有两种栈式符号表每进入一个作用域就压入一张新表退出时弹出一张。查名字从栈顶往下逐表查找。链式符号表每个条目增加一个指针指向同一作用域的下一个条目另外每个作用域绑定一条链表查名字时沿着作用域链从内到外查。静态作用域语言里内层作用域的同名变量会隐藏外层变量。词法分析器只负责登记名字不需要管“隐藏”规则但符号表的数据结构必须能支撑后续语义分析时的查找和隐藏。所以学词法分析时就要把符号表怎么建、怎么查、怎么销毁理解透不然后面阶段会卡壳。符号表实现上最常用的是哈希表。哈希函数可以基于字符串的每个字符加权求和取模冲突处理用链地址法或开放地址法。课程实验里为了简单很多人直接用线性表每次插入一个新标识符就append到末尾查找时线性扫描。数据量小的时候完全够用但我也见过实验测评里有上千个标识符的情况线性表明显变慢建议还是写个简单哈希。一个容易忽略的细节是字符串本身怎么存储。哈希表里如果只存char*指针必须保证这个指针指向的内存长期有效。如果词法分析器的缓冲区会被后续Token覆盖就必须把标识符名字拷贝到独立分配的内存里或者用一个专门的字符串表统一存放。很多实验报告里出现诡异Bug就是指针指向了被复用的缓冲区。6. 词法错误与边界情况易错点和哈工大实验的常见坑词法分析阶段虽然只管“拆单词”但依然会碰到错误输入。最常见的词法错误主要有四类非法字符比如C语言源码里出现了、#预处理另说、中文全角分号等未终止的字符串或注释字符串/注释只有开始标记没有结束标记非法数字格式比如12abc、0x后没有十六进制数字标识符/数字过长超出编译器允许的长度上限。错误处理策略在编译原理教材里叫“错误恢复”。最简单实用的是恐慌模式panic mode发现错误后丢弃当前词素里无法识别的那段字符然后继续扫描直到找到下一个明确的分隔符换行、分号等再恢复到正常识别状态。这样做的好处是实现简单、不容易无限循环坏处是可能丢失部分信息导致错误提示不够精确。我在上手写词法分析器实验时遇到过一个特别经典的坑错误恢复时忘记前进指针导致死循环。例如遇到非法字符如果不跳过它就再次读取同一个字符永远卡在那里。正确做法是每次报告错误后至少移动一个字符或者直接跳过整段无法匹配的输入。具体来说手写词法分析器要特别处理这几个边界文件结尾的处理getToken()在读到EOF时必须返回EOF Token。状态机在EOF时也要判断当前状态是否可接受。比如读到一个尚未结束的字符串突然EOF应当报错而不是沉默退出。最长匹配的代码实现不能一看到就立刻返回LT Token必须尝试继续读下一个字符。如果下一个是才能返回LE。更复杂的情况比如在C模板里用法不同词法阶段一般只管按运算符切具体是移位还是模板右括号交给语法分析。手写时建议先把所有运算符按最长可能匹配排序逐个尝试。关键字和标识符的判定顺序一种做法是先用标识符正则匹配出id再查保留字表如果命中就改成关键字Token。另一种做法是把关键字直接当作特殊模式并且声明在标识符模式之前。两种都行但要注意第一种做法要求符号表里预先插入所有关键字词法分析器查表时会混入用户定义的标识符容易出错。我更推荐把保留字单独建一张哈希表和符号表互不干扰。空白和注释的跳过空白字符空格、制表符、换行通常被忽略但换行要计数以产生行号。注释也要跳过但C语言注释不能嵌套遇/*开始后必须找到第一个*/否则报“注释未结束”。处理注释时最容易漏掉行号更新导致后续报错位置偏移好几行。缓冲区回退识别过程中多读的字符要能“放回”。如果用单字符变量peek那么每次取下一个Token前把peek初始化成第一个字符遇到需要回退时直接把peek重置即可。但多向前看字符时就需要更复杂的缓冲区管理。课程实验规模一般向前看1-2个字符就够。我在哈工大实验里吃过一次亏把和的状态图简化合并导致a b被解析成a b语法分析阶段怎么调都不过。后来翻状态图才发现的状态和的状态必须分得清清楚楚读入后下一位如果是则进入EQ状态否则回退一位返回ASSIGN状态。这个改动看起来只是加了一个状态却让整个调试过程柳暗花明。关于错误提示建议每个Token都记录行号和列号。词法分析器输出错误信息时直接给出行列号方便自己和测试脚本定位。很多评测平台会检查错误输出的格式我通常会定义统一的错误输出函数void report_error(int line, int col, const char *msg) { fprintf(stderr, Line %d, Column %d: %s\n, line, col, msg); }别看这个函数只有一行它能让实验调试省下一半时间。最后再说说正则到状态图的实际落地。课程要求用正则定义描述规则但手写代码时很多人喜欢用一长串if判断结果代码越写越乱。我的习惯是把每个Token的识别写成一个小状态机函数主循环只负责分发。比如lex_identifier()、lex_number()、lex_relop()每个函数内部维护自己的状态变量和字符指针。这样每个函数的逻辑能控制在几十行以内排查Bug时一目了然。等你真的写出一个能处理C语言子集的词法分析器再回头看书上的状态转换图会感觉那些图就是代码的“灵魂画稿”。