手写词法分析器：从原理到实现，避开预读与位置信息陷阱

1. 词法分析器到底在编译器里扮演什么角色

很多人学编译原理，一上来就被“有限自动机”“正则表达式”“NFA转DFA”这些术语砸晕，结果代码没写几行，先被理论劝退。我当初也是这么过来的，后来在某个模拟项目里被要求手写一个能跑通四则运算的词法分析器，才真正把这块知识嚼碎咽下去。这篇笔记就围绕词法分析器这个核心，把它的定位、设计思路、手写实现和踩坑经验一次讲透。

先说清楚它是什么。词法分析器（Lexer，也叫扫描器 Scanner）是编译器的第一个实质性阶段，它的输入是一串字符流，输出是一个个带有类型标记的词法单元（Token）。你可以把它想象成流水线上的第一道分拣工：源代码是一堆混在一起的原材料，词法分析器负责把它们切成一个个有意义的“零件”，并贴上标签——这是关键字、那是标识符、那是数字常量、那是运算符。

它能解决什么问题？最直接的是把“字符”这种底层表示，提升到“词”这个有语义的层次。后续的语法分析器不需要再去关心i和f这两个字符怎么拼成if，它只需要拿到一个类型为“关键字IF”的Token就够了。这种分层解耦是编译器设计的经典思路：每一层只干一件事，把结果交给下一层。

适合谁来参考？如果你正在学编译原理课程、准备手写一个简易编译器、或者想给某个DSL（领域特定语言）做解析前端，这篇内容都能直接拿来用。我会从设计思路讲到可运行的代码，再把我实际调试时遇到的坑一个个列出来。哪怕你之前没接触过自动机理论，跟着走也能写出一个能用的词法分析器。

2. 词法分析器的整体设计与方案选型

2.1 为什么词法分析要独立成一个阶段

初学者常问：为什么不把词法分析和语法分析合并成一步做完？我一开始也觉得分开是脱裤子放屁，后来写了一个稍微复杂点的表达式解析器才明白，分开至少有三个实打实的好处。

第一是简化设计。词法层面处理的是正则语言，用有限自动机就能搞定；语法层面处理的是上下文无关语言，需要下推自动机。两者的理论模型不同，混在一起会让代码逻辑变得极其混乱。分开之后，词法分析器内部只需要维护一个状态机，语法分析器只需要面对Token序列，各自的心智负担都小很多。

第二是提升效率。词法分析阶段可以做很多优化，比如把空白字符和注释直接丢弃，让语法分析器拿到的输入更干净。如果合并处理，语法分析器每次读字符都要判断是不是空白、是不是注释，重复劳动太多。

第三是增强可移植性。词法分析器往往和具体的字符编码、换行符约定强相关，而语法分析器更关心语言结构。把字符层面的脏活累活隔离在词法层，换一个平台或者换一种编码时，只需要改词法分析器，语法分析器纹丝不动。

提示：如果你只是写一个极简的计算器，确实可以把词法和语法揉在一起。但只要语言稍微复杂一点，分开就是更明智的选择。这不是教条，是无数人踩坑后的共识。

2.2 手写扫描器 vs 自动生成工具

实现词法分析器有两条主流路线：一是用Lex/Flex这类工具自动生成，二是纯手写。我在不同项目里两种都用过，这里说说各自的适用场景。

自动生成工具的好处是快。你只需要写正则表达式和对应的动作，工具帮你生成C代码。对于关键字多、Token类型繁杂的大型语言，这种方式能省下大量重复劳动。但它的缺点也很明显：生成的代码可读性差，调试困难，而且引入了一个额外的构建依赖。学生做课程设计时，用Flex往往会被要求“不能使用自动生成工具”，因为老师想看你理解原理。

手写扫描器的好处是完全可控。每一个字符怎么处理、每一个状态怎么跳转，都在你眼皮底下。调试的时候可以直接打断点，看当前读到哪个字符、处于哪个状态。对于学习目的和中小型语言，手写是更好的选择。我个人的经验是：先把自动机的理论搞清楚，然后手写一遍，最后再用工具生成一遍对比，这样理解最深。

这篇笔记走的是手写路线，因为标题里明确是“学习笔记”，重点在理解原理而不是快速产出。

2.3 Token的数据结构设计

Token是词法分析器的输出单元，它的结构设计直接影响后续使用的便利性。一个典型的Token至少包含三部分信息：类型（type）、原始文本（lexeme）、附加属性（attribute）。

类型用来区分这是关键字、标识符、数字还是运算符。原始文本是它在源代码里的原始样子，比如count这个标识符的lexeme就是字符串"count"。附加属性则用来携带更多信息，比如数字Token需要把字符串"3.14"转换成浮点数值3.14存进去，标识符Token可能需要指向符号表的入口。

我用Python写的时候，习惯用一个简单的类或者命名元组来表示Token：

from dataclasses import dataclass from enum import Enum, auto class TokenType(Enum): NUMBER = auto() IDENTIFIER = auto() KEYWORD_IF = auto() KEYWORD_ELSE = auto() KEYWORD_WHILE = auto() PLUS = auto() MINUS = auto() STAR = auto() SLASH = auto() LPAREN = auto() RPAREN = auto() ASSIGN = auto() EQ = auto() LT = auto() GT = auto() EOF = auto() @dataclass class Token: type: TokenType lexeme: str value: object = None line: int = 1 column: int = 1

这里我额外加了line和column两个字段，用来记录Token在源代码中的位置。这个信息在报错时极其有用——没有它，你只能告诉用户“语法错误”，有了它，你可以说“第3行第15列附近缺少分号”。很多手写词法分析器一开始偷懒不加位置信息，后期想补就得大改，建议一开始就加上。

注意：TokenType用枚举而不是整数常量，是为了避免不同Token类型之间意外相等。我见过有人用1表示数字、2表示标识符，结果调试时把2当成数字类型，查了半天才发现是标识符。枚举能从根本上杜绝这类低级错误。

3. 核心细节解析与手写实操要点

3.1 输入缓冲与字符读取的细节处理

词法分析器本质上是一个字符一个字符地读，然后根据当前字符和状态决定下一步。听起来简单，但字符读取这块有几个细节如果处理不好，后面会一直出bug。

第一个细节是预读（lookahead）。很多Token需要看两个字符才能确定。比如=和==，读到第一个=时你不能立刻返回赋值Token，得再看下一个字符是不是=。如果是，就组成等于号；如果不是，就把那个字符“退回去”，返回赋值Token。实现预读有两种常见方式：一是用缓冲区加指针回退，二是用带peek功能的读取器。

我习惯用第二种，写一个简单的字符流类：

class CharStream: def __init__(self, text): self.text = text self.pos = 0 self.line = 1 self.column = 1 def peek(self, offset=0): idx = self.pos + offset if idx < len(self.text): return self.text[idx] return '\0' def advance(self): if self.pos >= len(self.text): return '\0' ch = self.text[self.pos] self.pos += 1 if ch == '\n': self.line += 1 self.column = 1 else: self.column += 1 return ch def eof(self): return self.pos >= len(self.text)

peek(0)看当前字符，peek(1)看下一个字符，advance()消费当前字符并前进。这个设计让预读变得很自然，不需要手动管理回退。

第二个细节是行号和列号的维护。上面代码里，每次遇到换行符就把行号加一、列号重置，其他字符列号加一。这个逻辑看起来简单，但如果你在预读时不小心调用了advance()，行号列号就会错乱。我的经验是：只有真正消费字符时才调用advance，peek永远不改变位置。这条规则能避免90%的位置信息错误。

第三个细节是文件结束的处理。当读到字符串末尾时，应该返回一个特殊的EOF Token，而不是让程序崩溃。EOF Token是语法分析器判断输入结束的标志，必须显式产生。

3.2 正则表达式到有限自动机的思维转换

词法分析器的核心理论是正则表达式和有限自动机。但实际手写时，你不需要真的画一个状态转移图再照着写代码。更实用的做法是：把每一类Token的识别规则想清楚，然后用if-else或者switch-case组织起来。

以标识符为例，它的规则是：以字母或下划线开头，后面跟任意个字母、数字或下划线。用正则写就是[a-zA-Z_][a-zA-Z0-9_]*。手写代码时，逻辑就是：

def read_identifier(self): start = self.stream.pos while not self.stream.eof(): ch = self.stream.peek() if ch.isalnum() or ch == '_': self.stream.advance() else: break lexeme = self.stream.text[start:self.stream.pos] return lexeme

这段代码本质上就是一个有限自动机：状态0是“还没读到任何字符”，状态1是“已经读到了合法标识符字符”，状态1遇到非标识符字符就终止。你不需要显式地写出状态变量，循环条件本身就表达了状态转移。

数字的识别稍微复杂一点，因为要处理整数、小数、可能还有科学计数法。我建议先支持整数和小数，科学计数法作为扩展。整数和小数的规则是：以数字开头，后面可以跟小数点，小数点后面再跟数字。注意3.这种形式通常是不合法的，小数点后面必须至少有一位数字。

def read_number(self): start = self.stream.pos while self.stream.peek().isdigit(): self.stream.advance() if self.stream.peek() == '.' and self.stream.peek(1).isdigit(): self.stream.advance() while self.stream.peek().isdigit(): self.stream.advance() lexeme = self.stream.text[start:self.stream.pos] return lexeme

这里用peek(1).isdigit()来判断小数点后面是否跟着数字，避免把3.误识别为小数。这个细节很多教程会忽略，但实际写的时候一定会遇到。

3.3 关键字与标识符的区分策略

关键字（如if、else、while）在词法上和标识符完全一样，都是字母序列。区分它们有两种常见策略。

第一种是先统一按标识符读入，再查关键字表。读到一个字母序列后，拿它去关键字集合里查一下，如果在集合里就返回对应的关键字Token，否则返回标识符Token。这种方式代码简洁，关键字表可以用哈希集合实现，查询是O(1)的。

KEYWORDS = { 'if': TokenType.KEYWORD_IF, 'else': TokenType.KEYWORD_ELSE, 'while': TokenType.KEYWORD_WHILE, } def read_identifier_or_keyword(self): lexeme = self.read_identifier() token_type = KEYWORDS.get(lexeme, TokenType.IDENTIFIER) return Token(token_type, lexeme)

第二种是在自动机里为每个关键字单独建一条路径。这种方式理论上更快，因为不需要读完整标识符再查表，但实现起来非常繁琐，关键字一多就难以维护。除非是性能极其敏感的场景，否则不推荐。

我强烈建议用第一种。它的额外开销就是一次哈希查询，在现代机器上可以忽略不计。而且关键字表可以动态修改，比如你想支持用户自定义关键字，改一下字典就行。

提示：关键字表用字典而不是列表，是因为字典的查找是常数时间，列表是线性时间。当关键字有几十个时，这个差异在大量Token的场景下会显现出来。养成用字典的好习惯。

3.4 空白字符与注释的跳过逻辑

空白字符（空格、制表符、换行符）和注释在语法层面没有意义，词法分析器应该直接跳过它们。但跳过不等于忽略——换行符影响行号统计，注释里可能有换行，这些都要正确处理。

空白字符的处理很简单：只要当前字符是空白，就advance，直到遇到非空白为止。注意换行符的advance会自动更新行号，所以不需要额外处理。

注释分两种：单行注释和块注释。单行注释通常以//或#开头，一直到行尾。块注释以/*开头，*/结尾，中间可以跨多行。块注释的处理要小心：如果读到文件结束都没遇到*/，应该报错“未闭合的注释”。

def skip_whitespace_and_comments(self): while not self.stream.eof(): ch = self.stream.peek() if ch in ' \t\n\r': self.stream.advance() elif ch == '/' and self.stream.peek(1) == '/': while not self.stream.eof() and self.stream.peek() != '\n': self.stream.advance() elif ch == '/' and self.stream.peek(1) == '*': self.stream.advance() self.stream.advance() while not self.stream.eof(): if self.stream.peek() == '*' and self.stream.peek(1) == '/': self.stream.advance() self.stream.advance() break self.stream.advance() else: raise LexerError("未闭合的块注释", self.stream.line, self.stream.column) else: break

这里用了Python的while...else结构：如果循环正常结束（没遇到break），说明读到了文件末尾还没找到*/，就抛出异常。这个技巧在处理“必须找到某个终止符”的场景时很好用。

4. 完整词法分析器的实现与调试记录

4.1 主循环的骨架搭建

有了前面的各个组件，主循环就是把它们串起来。逻辑很直接：跳过空白和注释，看当前字符是什么，分派到对应的读取函数，产生Token，重复直到文件结束。

class Lexer: def __init__(self, text): self.stream = CharStream(text) self.tokens = [] def tokenize(self): while not self.stream.eof(): self.skip_whitespace_and_comments() if self.stream.eof(): break ch = self.stream.peek() if ch.isalpha() or ch == '_': self.tokens.append(self.read_identifier_or_keyword()) elif ch.isdigit(): self.tokens.append(self.read_number()) elif ch == '+': self.stream.advance() self.tokens.append(Token(TokenType.PLUS, '+')) elif ch == '-': self.stream.advance() self.tokens.append(Token(TokenType.MINUS, '-')) elif ch == '*': self.stream.advance() self.tokens.append(Token(TokenType.STAR, '*')) elif ch == '/': self.stream.advance() self.tokens.append(Token(TokenType.SLASH, '/')) elif ch == '(': self.stream.advance() self.tokens.append(Token(TokenType.LPAREN, '(')) elif ch == ')': self.stream.advance() self.tokens.append(Token(TokenType.RPAREN, ')')) elif ch == '=': self.stream.advance() if self.stream.peek() == '=': self.stream.advance() self.tokens.append(Token(TokenType.EQ, '==')) else: self.tokens.append(Token(TokenType.ASSIGN, '=')) elif ch == '<': self.stream.advance() self.tokens.append(Token(TokenType.LT, '<')) elif ch == '>': self.stream.advance() self.tokens.append(Token(TokenType.GT, '>')) else: raise LexerError(f"非法字符 '{ch}'", self.stream.line, self.stream.column) self.tokens.append(Token(TokenType.EOF, '')) return self.tokens

这个骨架覆盖了基本的运算符、括号、标识符、关键字和数字。你可以看到，每个分支都很短，逻辑清晰。如果Token类型更多，可以把单字符运算符的处理合并成一个字典查找，减少重复代码。

4.2 多字符运算符的预读处理

上面代码里==的处理展示了预读的典型用法。类似的还有<=、>=、!=、&&、||等。处理模式都一样：先消费第一个字符，再看下一个字符是否匹配，匹配就消费并返回双字符Token，不匹配就返回单字符Token。

这里有一个容易犯的错误：预读之后忘记消费第二个字符。比如处理==时，如果只advance了一次就返回，那么第二个=会被下一轮主循环再次处理，导致产生两个赋值Token而不是一个等于Token。这个bug很隐蔽，因为程序不会崩溃，只是Token序列错了，语法分析阶段才会报奇怪的错误。

我的建议是：每写一个多字符运算符的处理分支，就立刻写一个对应的测试用例。比如输入a == b，期望得到[IDENTIFIER, EQ, IDENTIFIER, EOF]。测试通过再写下一个。

4.3 错误处理与位置信息报告

词法分析器遇到非法字符时，不能简单地打印错误然后退出。好的错误处理应该包含三个要素：错误类型、位置信息、可能的修复建议。

位置信息就是行号和列号，前面已经在CharStream里维护了。错误类型要具体，比如“非法字符”和“未闭合的注释”是两种不同的错误。修复建议则要看情况，比如遇到非法字符@，可以提示“该字符不是合法的运算符或标识符起始字符”。

class LexerError(Exception): def __init__(self, message, line, column): super().__init__(f"第{line}行第{column}列: {message}") self.line = line self.column = column

实际调试时，我习惯在错误信息里把出错位置附近的源代码片段也打印出来，用^指向具体位置。这个功能在命令行工具里特别有用，用户一眼就能看到问题在哪。

注意：词法分析阶段的错误恢复是一个进阶话题。简单的做法是遇到错误就抛出异常终止；复杂一点的做法是跳过当前字符，继续扫描，尽可能多地报告错误。对于学习项目，抛出异常就够了；对于生产级编译器，错误恢复是必须的。

4.4 测试用例设计与验证方法

写完词法分析器，怎么验证它是对的？我通常从三个层次设计测试。

第一层是单元测试，针对每个读取函数单独测试。比如read_number输入"3.14"应该返回"3.14"，输入"42"应该返回"42"，输入"3."应该只返回"3"然后留下.给下一个Token。

第二层是集成测试，输入一段完整的代码，检查输出的Token序列是否符合预期。比如：

def test_basic_expression(): lexer = Lexer("x = 3 + 4 * (y - 1)") tokens = lexer.tokenize() types = [t.type for t in tokens] expected = [ TokenType.IDENTIFIER, TokenType.ASSIGN, TokenType.NUMBER, TokenType.PLUS, TokenType.NUMBER, TokenType.STAR, TokenType.LPAREN, TokenType.IDENTIFIER, TokenType.MINUS, TokenType.NUMBER, TokenType.RPAREN, TokenType.EOF ] assert types == expected

第三层是边界测试，专门测那些容易出错的边界情况：空输入、只有空白、只有注释、未闭合的注释、非法字符、文件末尾没有换行、超长标识符等。这些用例往往能发现最隐蔽的bug。

我踩过的一个坑是：输入为空字符串时，tokenize应该只返回一个EOF Token。但我的第一版代码在skip_whitespace_and_comments之后没有再次检查eof，导致空输入时进入了字符分派逻辑，然后peek返回'\0'，被当成非法字符报错。修复方法就是在跳过空白后加一次if self.stream.eof(): break。

5. 常见问题与排查技巧实录

5.1 词法分析器典型问题速查表

下面这张表整理了我实际写词法分析器时遇到的高频问题，以及对应的排查思路和解决方法。

5.2 预读逻辑的常见陷阱

预读是词法分析器里最容易出错的地方，没有之一。我总结了几条经验，能帮你避开大部分坑。

第一条：预读不消费。peek(1)只是看一眼下一个字符，不改变流的位置。只有确定要组成多字符Token时，才调用advance()消费它。这个原则听起来简单，但在写代码时很容易顺手就advance了。

第二条：预读要考虑边界。当当前字符是最后一个字符时，peek(1)应该返回一个特殊值（比如'\0'），而不是抛出索引越界异常。CharStream的peek方法里已经处理了这种情况，返回'\0'。但你在判断时要注意，'\0'不等于任何合法字符，所以不会误匹配。

第三条：嵌套预读要小心。有些场景需要看两个字符，比如>>=这种三字符运算符。这时候要用peek(2)。但每多一层预读，逻辑复杂度就上升一截。我的建议是：如果运算符超过两个字符，考虑用最长匹配策略配合一个小的状态机，而不是堆叠if-else。

5.3 性能优化的几个实用技巧

词法分析器的性能通常不是瓶颈，但在处理大文件时，一些优化能带来明显提升。

第一个技巧是避免频繁的字符串切片。每次读取Token时，self.stream.text[start:self.stream.pos]都会创建一个新字符串。对于短Token这没什么，但如果标识符很长、Token数量很多，累积开销不可忽视。优化方法是记录start和end索引，只在需要时切片，或者用内存视图。

第二个技巧是用字符分类表代替isalpha/isdigit。Python的isalpha()和isdigit()是方法调用，有一定开销。如果性能敏感，可以预先构建一个256长度的布尔数组，用字符的ASCII码直接索引。不过对于学习项目，这个优化没必要，可读性更重要。

第三个技巧是批量处理空白字符。与其一个字符一个字符地跳过空白，不如用正则表达式或者字符串查找一次性跳过连续空白。Python里可以用re.match(r'\s+', text[pos:])找到空白段的长度，然后一次性advance。这个优化在空白密集的代码里效果明显。

提示：优化之前先测量。我见过有人花大力气优化词法分析器，结果发现整个编译过程的时间都花在语法分析上，词法分析只占5%。用cProfile跑一下，找到真正的瓶颈再动手。

5.4 从词法分析到语法分析的衔接要点

词法分析器写完之后，下一步就是语法分析。衔接的时候有几个点需要注意。

第一，Token序列要以EOF结尾。语法分析器需要一个明确的结束标志，否则它不知道什么时候停止。EOF Token的lexeme可以是空字符串，但类型必须是EOF。

第二，Token类型要足够细分。如果你把所有的运算符都归为一个“OPERATOR”类型，语法分析器还得再去判断具体是哪个运算符，这就把词法层的职责推到了语法层。正确的做法是每个运算符一个类型，或者至少把不同优先级的运算符分开。

第三，位置信息要传递下去。语法分析器报错时也需要位置信息，所以Token里的line和column要保留。有些实现为了省内存把位置信息去掉，结果语法错误只能报“某处有错误”，用户体验很差。

第四，考虑设计一个Token流接口。语法分析器通常需要预读多个Token（LL解析器需要看一个，LR解析器可能需要看更多）。与其直接传一个列表，不如封装一个TokenStream类，提供peek(k)和next()方法。这样语法分析器的代码会更干净。

class TokenStream: def __init__(self, tokens): self.tokens = tokens self.pos = 0 def peek(self, offset=0): idx = self.pos + offset if idx < len(self.tokens): return self.tokens[idx] return self.tokens[-1] # 返回EOF def next(self): token = self.peek() if self.pos < len(self.tokens) - 1: self.pos += 1 return token

这个设计让语法分析器可以自由地预读，而不用担心索引越界。返回EOF作为默认值是一个常用技巧，因为EOF永远不会被合法消费，预读超出范围时返回它最安全。

6. 我个人在实际操作中的几点体会

写词法分析器这件事，理论看一遍就懂，代码写一遍才知道坑在哪。我最大的体会是：不要一开始就追求大而全。第一版只支持数字、标识符和四则运算符，跑通之后再逐步加关键字、加注释、加多字符运算符。每加一个功能就补一组测试，这样出问题时能快速定位是哪次修改引入的。

另一个体会是位置信息的价值被严重低估。我最初写词法分析器时觉得行号列号是锦上添花，后来做语法分析时才发现，没有位置信息的报错几乎没法用。建议从第一行代码就把位置信息加上，后面会感谢自己。

最后分享一个小技巧：如果你不确定某个字符序列应该被识别成什么Token，可以先用一个简单的正则表达式测试工具验证一下你的规则，再把规则翻译成代码。这样能避免“想当然”导致的逻辑错误。比如1.2.3这种输入，你的数字识别逻辑会怎么处理？提前想清楚，比写完再调试省时间。

这个内容后续还可以这样扩展：把词法分析器改造成支持缩进敏感的语言（比如用缩进代替花括号），或者加入字符串字面量和转义字符的处理。这两个方向都能让你对词法分析的理解再深一层。