1. 从一段看起来没问题的代码说起很多人学编译原理卡在词法分析这一关不是因为概念难而是因为一上手就被正则表达式有限自动机状态转移这些词砸晕了。我当初也是这么过来的——教材翻到词法分析那一章满页的圆圈箭头和数学符号看完感觉自己懂了合上书让自己写一个能跑的扫描器又完全不知道从哪下手。这篇笔记就是写给同样卡在这一步的人。我会把词法分析器到底在干什么为什么需要它怎么从零写一个能用的版本这几件事讲透重点放在可操作的实现思路上而不是把教材里的定义再抄一遍。你不需要先精通自动机理论只要会一门编程语言我用Python举例但思路是通用的就能跟着把东西做出来。词法分析器Lexer也叫Scanner做的事情说白了就一句话把一串字符流切成一个个有意义的词Token。比如你写int x 10 20;人眼一看就知道这是类型 变量名 赋值 数字 加号 数字 分号但计算机看到的只是一串ASCII码。词法分析器就是那个把字符流翻译成Token流的翻译官。听起来简单但真正动手写的时候你会发现一堆问题冒出来空格怎么处理注释怎么跳过和怎么区分123abc这种非法输入怎么办字符串里的转义字符怎么解析这些问题教材上往往一笔带过但实际写代码时每一个都能卡你半天。下面我就按实际实现的顺序把这些坑一个个填掉。2. Token的设计先想清楚切出来的东西长什么样在动手写扫描逻辑之前有一件事必须先定下来Token的数据结构。这个设计决定了后面所有代码的写法如果一开始没想清楚写到一半发现字段不够用返工成本很高。2.1 Token至少需要哪几个字段一个最小可用的Token我建议包含三个字段类型type这是个什么词是关键字、标识符、数字、运算符还是分隔符。类型通常用枚举表示。值value这个词的原始内容是什么比如标识符count的值就是字符串count数字42的值可以是整数42也可以是字符串42。位置position这个词在源代码的第几行第几列。这个字段新手最容易忽略但它是后面报错时能给出第3行第5列有语法错误这种友好提示的关键。很多人一开始只写type和value觉得位置信息无所谓。等到写语法分析器的时候发现报错只能说有个地方错了用户根本不知道去哪找这时候再回头加位置信息所有Token的构造点都要改一遍。所以我的建议是位置信息从第一天就加上哪怕暂时用不到。from enum import Enum, auto from dataclasses import dataclass class TokenType(Enum): # 字面量 NUMBER auto() STRING auto() IDENTIFIER auto() # 关键字 IF auto() ELSE auto() WHILE auto() INT auto() # 运算符 PLUS auto() MINUS auto() STAR auto() SLASH auto() ASSIGN auto() EQ auto() # 分隔符 LPAREN auto() RPAREN auto() LBRACE auto() RBRACE auto() SEMICOLON auto() # 特殊 EOF auto() dataclass class Token: type: TokenType value: object line: int column: int def __repr__(self): return fToken({self.type.name}, {self.value!r}, {self.line}:{self.column})这里用dataclass是为了少写一堆样板代码__repr__是为了调试时打印出来好看。别小看这个repr调试词法分析器的时候你会打印成百上千个Token格式清晰能省很多时间。2.2 关键字和标识符的关系为什么不在扫描时直接区分一个常见的设计问题是if、while这些关键字是在扫描阶段就识别成独立的Token类型还是先统一识别成标识符后面再查表转换两种做法都有人用但我更推荐在词法分析阶段就区分。原因是关键字是语言保留的不能被用作变量名。如果你先扫描成标识符那if 5这种代码在词法阶段就检查不出来要等到语法分析甚至语义分析才发现报错位置会变得很模糊。在词法阶段直接识别关键字遇到if就返回TokenType.IF那么当解析器期望一个标识符却拿到IF时就能立刻报关键字不能作为变量名。实现上很简单扫描到一个完整的单词后先查关键字表命中就返回对应的关键字类型没命中才当作标识符。KEYWORDS { if: TokenType.IF, else: TokenType.ELSE, while: TokenType.WHILE, int: TokenType.INT, }这个表随着语言支持的扩展会越来越长但结构始终是这个结构。注意关键字表要用哈希表Python的dict就是查找是O(1)不要用一串if-else去判断那样每扫一个标识符都要比较好几次性能差很多。2.3 位置信息怎么维护才不出错位置信息看着简单实际写起来很容易错。核心是要维护两个变量当前行号line和当前列号column。每读一个字符column加1遇到换行符line加1、column归零。但这里有个坑Token的位置应该记录它的起始位置而不是结束位置。因为报错时我们想知道这个词从哪开始而不是到哪结束。所以正确的做法是在开始扫描一个Token之前先把当前的line和column存下来扫描结束后用存下来的值构造Token。def next_token(self): self.skip_whitespace_and_comments() start_line self.line start_column self.column # ... 扫描逻辑 ... return Token(token_type, value, start_line, start_column)还有一个细节制表符Tab怎么算列号有的实现把Tab算作1列有的算作4列或8列。这个没有标准答案但整个项目里必须统一否则报错位置会飘。我一般简单处理Tab就算1列够用了。3. 手写扫描器一个字符一个字符地啃Token结构定好之后就可以写扫描逻辑了。词法分析器的核心就是一个大循环每次从输入里读一个Token出来直到读完为止。这个循环内部根据当前字符是什么决定走哪条分支。3.1 主循环的骨架先看整体结构这是所有手写词法分析器的通用骨架class Lexer: def __init__(self, source: str): self.source source self.pos 0 # 当前字符在source中的下标 self.line 1 self.column 1 self.current_char source[0] if source else None def advance(self): 前进一个字符同时维护行列号 if self.current_char \n: self.line 1 self.column 1 else: self.column 1 self.pos 1 if self.pos len(self.source): self.current_char self.source[self.pos] else: self.current_char None def peek(self, offset1): 预读后面的字符不移动指针 peek_pos self.pos offset if peek_pos len(self.source): return self.source[peek_pos] return None def tokenize(self): tokens [] while self.current_char is not None: token self.next_token() if token is not None: tokens.append(token) tokens.append(Token(TokenType.EOF, None, self.line, self.column)) return tokens这里有两个关键方法advance和peek。advance是消费当前字符并前进peek是偷看后面的字符但不前进。为什么需要peek因为有些Token需要看两个字符才能确定比如和和。没有peek的话你读到时不知道后面跟的是不是另一个就没法正确切分。提示peek的offset参数默认是1表示看下一个字符。有些实现需要看更远比如处理...这种三字符运算符就需要peek(2)。但大多数语言peek(1)就够了。3.2 空白和注释最容易被低估的部分跳过空白空格、Tab、换行看起来是最简单的但注释的处理往往比想象中麻烦。注释分两种单行注释//到行尾和多行注释/* */。单行注释好处理一直advance到换行符就行。多行注释的坑在于如果文件结束了还没遇到结束标记怎么办这是语法错误必须报出来不能默默忽略。我见过不少教学实现直接while循环找*/文件结束就死循环或者静默退出这是不对的。def skip_whitespace_and_comments(self): while self.current_char is not None: if self.current_char in \t\n\r: self.advance() elif self.current_char / and self.peek() /: # 单行注释 while self.current_char is not None and self.current_char ! \n: self.advance() elif self.current_char / and self.peek() *: # 多行注释 self.advance() # 吃掉 / self.advance() # 吃掉 * while True: if self.current_char is None: raise SyntaxError( f第{self.line}行: 多行注释未闭合 ) if self.current_char * and self.peek() /: self.advance() self.advance() break self.advance() else: break注意多行注释里那个while True加显式的None检查这是防止未闭合注释导致死循环的关键。另外注释里如果嵌套了//或者别的符号不需要特殊处理因为多行注释内部一切字符都当普通字符跳过直到遇到*/。3.3 数字扫描整数、小数、以及那些边界情况数字扫描的核心逻辑是只要当前字符是数字就继续读。但实际语言里数字不止整数还有小数、科学计数法、不同进制等等。我们先从最简单的整数开始再逐步扩展。def scan_number(self): start_line, start_column self.line, self.column result while self.current_char is not None and self.current_char.isdigit(): result self.current_char self.advance() # 检查小数点 if self.current_char . and self.peek() and self.peek().isdigit(): result self.current_char self.advance() while self.current_char is not None and self.current_char.isdigit(): result self.current_char self.advance() return Token(TokenType.NUMBER, float(result), start_line, start_column) return Token(TokenType.NUMBER, int(result), start_line, start_column)这里有个细节值得说判断小数点时我加了self.peek().isdigit()这个条件。为什么因为1.foo这种写法里点号可能是成员访问运算符不是小数点。如果不检查后面是不是数字就会把1.当成一个浮点数然后foo变成标识符解析结果就错了。这个坑我在写第一个版本时踩过调试了半天才发现。科学计数法1e10、2.5e-3的处理类似遇到e或E时往后看是不是数字或者正负号加数字是的话就继续读。这里不展开代码思路是一样的用peek预判确认是数字的一部分才消费。3.4 标识符和关键字字母开头字母数字下划线继续标识符的规则很简单首字符必须是字母或下划线后续字符可以是字母、数字或下划线。扫描逻辑就是一个while循环把符合条件的字符都吃进来。def scan_identifier(self): start_line, start_column self.line, self.column result while (self.current_char is not None and (self.current_char.isalnum() or self.current_char _)): result self.current_char self.advance() # 查关键字表 token_type KEYWORDS.get(result, TokenType.IDENTIFIER) return Token(token_type, result, start_line, start_column)注意isalnum()在Python里对Unicode字符也返回True比如中文、日文都是alnum。如果你的语言只支持ASCII标识符就要显式判断a c z or A c Z。这个细节取决于你的需求但心里要清楚这个区别不然可能莫名其妙允许了中文变量名。3.5 运算符单字符、双字符、以及最长匹配原则运算符扫描是词法分析里最容易写错的地方核心原则是最长匹配能匹配两个字符的就不要只匹配一个。比如看到要往后看是不是或是的话就组成或。def scan_operator(self): start_line, start_column self.line, self.column ch self.current_char nxt self.peek() # 双字符运算符优先 two_char ch (nxt or ) if two_char in (, !, , , , ||, , --): self.advance() self.advance() return Token(TWO_CHAR_OPS[two_char], two_char, start_line, start_column) # 单字符运算符 self.advance() if ch in SINGLE_CHAR_OPS: return Token(SINGLE_CHAR_OPS[ch], ch, start_line, start_column) raise SyntaxError(f第{start_line}行第{start_column}列: 非法字符 {ch})这个结构的关键是先尝试匹配长的失败了再匹配短的。如果反过来先匹配单字符那永远会被切成两个解析器就懵了。这个原则在词法分析里叫最大吞噬maximal munch是所有词法分析器都必须遵守的。4. 那些教材不写但实际会遇到的坑前面讲的是正常路径但真正让词法分析器难写的是各种边界情况和错误处理。这一章我专门讲这些。4.1 非法字符报错还是跳过遇到语言不认识的字符比如、$、#假设你的语言不支持这些应该怎么办有两种选择报错终止或者跳过继续。我的建议是报错但不要立即终止。报错是为了让用户知道有问题不终止是为了让用户一次看到所有错误而不是改一个跑一次。实现上可以收集错误列表扫描结束后统一抛出。class Lexer: def __init__(self, source): # ... self.errors [] def next_token(self): # ... else: self.errors.append( f第{self.line}行第{self.column}列: 无法识别的字符 {self.current_char} ) self.advance() return None # 跳过这个字符继续扫描注意这里返回None主循环里要判断None并跳过。这样扫描器不会因为一个非法字符就崩掉能继续往后扫把后面的错误也找出来。4.2 字符串字面量转义和未闭合字符串的处理比看起来复杂。首先是转义字符\n、\t、\\、\这些要正确解析成对应的字符。其次是未闭合字符串读到文件结束还没遇到结束引号必须报错。def scan_string(self): start_line, start_column self.line, self.column self.advance() # 跳过开头的引号 result while self.current_char is not None and self.current_char ! : if self.current_char \\: self.advance() if self.current_char is None: break escape_map {n: \n, t: \t, \\: \\, : } result escape_map.get(self.current_char, self.current_char) self.advance() else: result self.current_char self.advance() if self.current_char ! : raise SyntaxError(f第{start_line}行: 字符串未闭合) self.advance() # 跳过结尾引号 return Token(TokenType.STRING, result, start_line, start_column)这里有个容易忽略的点转义字符处理时如果反斜杠后面是文件结尾要break出去让未闭合检查报错不能直接访问self.current_char然后崩掉。这种边界情况在测试时很难想到但用户输入千奇百怪早晚会遇到。4.3 数字后面直接跟字母123abc怎么处理123abc这种输入不同语言处理方式不同。有的报错有的切成123和abc两个Token。我倾向于报错因为这几乎肯定是用户写错了比如想写变量名但以数字开头。实现上在scan_number结束后检查当前字符是不是字母或下划线是的话就报错if self.current_char is not None and (self.current_char.isalpha() or self.current_char _): raise SyntaxError( f第{start_line}行: 数字后面不能直接跟字母 )这个检查很便宜但能帮用户避免很多隐蔽的bug。4.4 位置信息在错误处理中的实际价值前面强调位置信息重要这里举个实际例子。假设输入是int x 10; int y ;如果没有位置信息报错只能说非法字符。有了位置信息就能说第2行第9列: 无法识别的字符 。用户一眼就知道去哪改。这就是为什么我反复强调位置信息要从第一天就加上——它的价值在错误处理时才体现出来但等到那时候再加就晚了。5. 从能跑到好用测试与调试的实战方法写完扫描器只是第一步怎么确认它是对的、怎么快速定位问题这些才是真正花时间的地方。5.1 用表格驱动测试把预期结果写清楚词法分析器的测试特别适合表格驱动输入一段代码预期输出一串Token。把测试用例写成表格一目了然加新用例也方便。输入预期Token序列int x 10;INT, IDENTIFIER(x), ASSIGN, NUMBER(10), SEMICOLON, EOFa bIDENTIFIER(a), EQ, IDENTIFIER(b), EOF// commentEOFhello\nSTRING(hello换行), EOF1.5 2NUMBER(1.5), PLUS, NUMBER(2), EOF写测试时我习惯把Token序列转成字符串比较比如INT IDENTIFIER ASSIGN NUMBER SEMICOLON EOF这样断言写起来简单失败时diff也好看。5.2 调试技巧打印Token流和单步跟踪调试词法分析器最有效的方法就是把Token流打印出来看。我通常在tokenize方法里加一个debug开关打开时每生成一个Token就打印一行包括类型、值和位置。这样一眼就能看出是在哪一步切错了。如果打印出来发现某个Token不对就在对应的scan方法里加print看每次advance时current_char是什么。词法分析器的bug基本都是少读了一个字符或多读了一个字符单步跟踪很快就能定位。提示调试时可以用一个很短的输入比如ab这样Token少容易对照。不要一上来就用几百行的代码调试那样输出太多反而看不清。5.3 性能什么时候需要担心手写词法分析器的性能对于一般项目来说完全够用。一个字符一个字符地读在现代机器上每秒能处理几MB的源代码编译一个几万行的项目也就几十毫秒。所以不要过早优化。但如果你的场景是IDE的实时语法高亮每次按键都要重新扫描那就需要注意了。优化的方向通常是避免频繁的字符串拼接用列表收集字符最后join以及用预读缓冲减少函数调用开销。不过这些是后话先把正确性搞定。6. 词法分析器在整个编译流程中的位置最后聊一个容易被忽略的问题词法分析器的边界在哪它该做多少事不该做多少事6.1 词法分析和语法分析的分工一个常见的困惑是像a.b.c这种成员访问词法分析器要不要处理点号答案是词法分析器只负责把.切成一个独立的Token具体它表示成员访问还是小数点是语法分析器的事。词法分析器不应该有上下文的概念它看到的永远是局部的字符序列。这个边界很重要。如果词法分析器开始根据上下文做判断代码会变得极其复杂而且容易出错。保持词法分析器的无状态除了行列号是让它简单可靠的关键。6.2 什么时候该用工具生成而不是手写手写词法分析器适合学习和小型语言。如果是工业级语言比如要实现一个完整的C编译器通常会用量具如Lex/Flex根据正则表达式自动生成。工具生成的扫描器性能更好也更容易维护。但我的建议是先手写一遍再用工具。手写一遍能让你真正理解Token是怎么切出来的遇到工具生成的代码出问题时也知道去哪找原因。直接上工具遇到问题只能干瞪眼。6.3 后续可以怎么扩展这个扫描器目前只支持最基本的Token类型。后续可以扩展的方向包括支持更多运算符位运算、三元运算符、支持字符字面量单引号、支持多行字符串、支持Unicode标识符等等。每加一种都是在scan方法里加一个分支结构不变。真正有意思的扩展是错误恢复当遇到非法Token时不只是报错而是尝试猜测用户想写什么给出更友好的提示。比如输入whiel可以提示你是不是想写 while。这需要引入编辑距离计算但能大幅提升用户体验。我个人在实际写扫描器时的体会是最难的不是算法而是把所有边界情况想全。教材上的例子永远是12这种理想输入但真实代码里什么奇怪的东西都有。多写测试、多拿真实代码跑是发现边界情况的最好方法。我自己的习惯是每遇到一个扫描器处理不了的输入就把它加进测试用例这样扫描器会越来越健壮。