第3章：手工实现词法分析器

词法分析，说白了就是让计算机学会“认字”。

我刚开始学编译原理时，觉得这步很简单。不就是把代码拆成一个个单词吗？后来自己动手写了一遍，才发现坑不少。嗯，今天我们就用Python手撸一个简单的词法分析器。

3.1 词法分析器在干啥？

你想想看，编译器拿到源代码，第一件事是什么？它得先看懂你写了啥。比如这段代码：

int a = 10 + 20;

人一眼就能看出：int是关键字，a是变量名，10和20是数字，=和+是运算符，;是分隔符。

但计算机不认识这些。它只认识0和1。所以我们需要一个程序，把源代码字符串，转换成一个个有意义的“词法单元”（Token）。

核心任务：输入源代码字符串 → 输出Token序列

3.2 我们要识别哪些东西？

根据题目要求，我们需要识别五类东西：

类别	例子	说明
关键字	int, if, else, while, return	语言保留的单词，不能用作变量名
标识符	a, myVar, counter	变量名、函数名等
数字	10, 3.14, 0xFF	整数和浮点数
运算符	+, -, *, /, =, ==	单字符和多字符运算符
分隔符	;, (, ), {, }	用来分隔代码结构

我在项目中遇到过一个问题：有人把关键字当变量名用了。比如写了个 int int = 5;，词法分析器直接报错。所以关键字必须优先匹配。

3.3 设计Token结构

每个Token至少需要两个信息：类型和值。我习惯用Python的namedtuple来定义：

from collections import namedtuple

Token = namedtuple('Token', ['type', 'value'])

# 举个例子
t1 = Token('KEYWORD', 'int')
t2 = Token('IDENTIFIER', 'a')
t3 = Token('NUMBER', '10')
t4 = Token('OPERATOR', '+')
t5 = Token('DELIMITER', ';')

这样每个Token都清清楚楚。你想想看，后续语法分析器拿到这些Token，就知道怎么处理了。

3.4 核心逻辑：状态机

词法分析器的核心，其实是一个有限状态自动机。说白了就是：

读一个字符
判断它属于哪一类
如果是数字开头，就继续读直到不是数字为止
如果是字母开头，就继续读直到不是字母或数字为止
如果是运算符或分隔符，直接返回

我画了一张流程图，帮你理解这个过程：

3.5 代码实现

好了，理论说完了，直接上代码。我习惯把代码写得清晰一点，方便以后维护。

import re
from collections import namedtuple

Token = namedtuple('Token', ['type', 'value'])

# 定义关键字集合
KEYWORDS = {'int', 'float', 'if', 'else', 'while', 'return', 'void', 'char'}

# 定义运算符（注意：多字符运算符要优先匹配）
OPERATORS = {'==', '!=', '<=', '>=', '&&', '||', '+', '-', '*', '/', '=', '<', '>', '!'}

# 定义分隔符
DELIMITERS = {';', ',', '(', ')', '{', '}', '[', ']'}

def lexer(code):
    tokens = []
    i = 0
    length = len(code)
    
    while i < length:
        ch = code[i]
        
        # 跳过空白字符
        if ch.isspace():
            i += 1
            continue
        
        # 识别数字
        if ch.isdigit():
            start = i
            while i < length and (code[i].isdigit() or code[i] == '.'):
                i += 1
            num_str = code[start:i]
            # 简单判断：如果包含小数点，就是浮点数
            if '.' in num_str:
                tokens.append(Token('NUMBER', float(num_str)))
            else:
                tokens.append(Token('NUMBER', int(num_str)))
            continue
        
        # 识别标识符或关键字
        if ch.isalpha() or ch == '_':
            start = i
            while i < length and (code[i].isalnum() or code[i] == '_'):
                i += 1
            word = code[start:i]
            if word in KEYWORDS:
                tokens.append(Token('KEYWORD', word))
            else:
                tokens.append(Token('IDENTIFIER', word))
            continue
        
        # 识别运算符（优先匹配多字符）
        matched = False
        for op_len in [2, 1]:  # 先尝试2字符，再尝试1字符
            if i + op_len <= length:
                candidate = code[i:i+op_len]
                if candidate in OPERATORS:
                    tokens.append(Token('OPERATOR', candidate))
                    i += op_len
                    matched = True
                    break
        if matched:
            continue
        
        # 识别分隔符
        if ch in DELIMITERS:
            tokens.append(Token('DELIMITER', ch))
            i += 1
            continue
        
        # 如果都不匹配，报错
        raise SyntaxError(f"无法识别的字符: '{ch}' 在位置 {i}")
    
    return tokens

# 测试一下
code = "int a = 10 + 20;"
result = lexer(code)
for token in result:
    print(token)

小技巧：我习惯把关键字、运算符、分隔符都定义成集合（set），这样查找速度更快。Python的集合底层是哈希表，O(1)时间复杂度。

3.6 避坑指南

我曾经在写词法分析器时踩过一个坑：运算符的优先级匹配。比如输入 ==，如果先匹配 =，就会把 == 拆成两个 =，逻辑就全错了。

解决办法很简单：先匹配多字符运算符，再匹配单字符。代码里我用了 for op_len in [2, 1] 这个技巧。

注意：词法分析器不要处理语义问题。比如 10abc 这种，词法分析器应该把它识别成数字 10 和标识符 abc，至于合不合理，那是语法分析器的事。

3.7 测试一下

我们来跑几个例子：

# 测试1：简单赋值
code1 = "int x = 42;"
print(lexer(code1))
# 输出：[Token(type='KEYWORD', value='int'), Token(type='IDENTIFIER', value='x'), 
#        Token(type='OPERATOR', value='='), Token(type='NUMBER', value=42), 
#        Token(type='DELIMITER', value=';')]

# 测试2：带运算符的表达式
code2 = "if (a >= 10) { return a + 1; }"
print(lexer(code2))
# 输出：...（自己试试看）

嗯，到这里，一个简单的词法分析器就完成了。你想想看，其实核心逻辑并不复杂，就是逐个字符扫描，根据字符类型做不同的处理。

我个人习惯把词法分析器写得尽量简单，因为后面还有语法分析、语义分析等着我们。词法分析器只要保证输出正确的Token序列就行，别想太多。

记住一句话：词法分析器是编译器的“眼睛”，它负责看，不负责理解。理解的事情，交给后面的阶段。

📚 课程目录

第3章：手工实现词法分析器

3.1 词法分析器在干啥？

3.2 我们要识别哪些东西？

3.3 设计Token结构

3.4 核心逻辑：状态机

3.5 代码实现

3.6 避坑指南

3.7 测试一下