2.3 手写一个词法分析器

2.3 手写一个词法分析器

本节摘要：本节用 Python 写一个约百行、可读性优先的词法分析器：支持标识符、关键字、整数与浮点、运算符与分号，实现最长匹配、行号追踪、非法字符报错。写完把主线语句喂进去，观察切分全程，并对照第 2.2 节的自动机理论，看理论如何落到分支语句上。

阅读完本节，你应当能够：

1. 实现带最长匹配的标识符与数字扫描函数
2. 组织词法单元的数据结构与关键字查表逻辑
3. 用测试用例验证扫描器行为，包括边界输入
4. 把手写分支与 DFA 转移表两种实现方式对应起来

设计先行

写代码前定三件事。第一，接口：提供 tokenize 函数，输入源码字符串，返回单元列表。第二，数据结构：每个单元是一个小对象，字段有类别、词素、行号。第三，错误策略：非法字符记入错误列表、跳过继续扫（完整恢复策略见 2.4 节）。

# 词法单元的容器与关键字表
KEYWORDS = {"if", "else", "while", "return", "int", "float"}

class Token:
    def __init__(self, kind, lexeme, line):
        self.kind = kind      # 类别：ID、NUM、ASSIGN、MUL ...
        self.lexeme = lexeme  # 词素：源码里的原样字符
        self.line = line      # 行号：报错定位用
    def __repr__(self):
        return f"({self.kind} {self.lexeme} 行{self.line})"
​

核心扫描循环

主体是一个逐字符的 while 循环，按首字符分流到各分支——这正是 DFA 的"按当前状态与字符查表"的手写版：

def tokenize(src):
    tokens, errors = [], []
    i, line, n = 0, 1, len(src)
    while i < n:
        c = src[i]
        if c == "\n":                       # 换行：丢弃但累计行号
            line += 1; i += 1
        elif c in " \t\r":                  # 空白：直接丢弃
            i += 1
        elif c.isalpha() or c == "_":       # 标识符或关键字分支
            start = i
            while i < n and (src[i].isalnum() or src[i] == "_"):
                i += 1                      # 最长匹配：贪心读完
            lex = src[start:i]
            kind = "KW" if lex in KEYWORDS else "ID"
            tokens.append(Token(kind, lex, line))
        elif c.isdigit():                   # 数字分支
            start = i
            while i < n and src[i].isdigit():
                i += 1
            if i < n and src[i] == "." and i + 1 < n and src[i+1].isdigit():
                i += 1
                while i < n and src[i].isdigit():
                    i += 1                  # 小数部分
            tokens.append(Token("NUM", src[start:i], line))
        elif c == "=":                      # 单字符运算符分支
            tokens.append(Token("ASSIGN", c, line)); i += 1
        elif c == "*":
            tokens.append(Token("MUL", c, line)); i += 1
        elif c == "-":
            tokens.append(Token("SUB", c, line)); i += 1
        elif c == ";":
            tokens.append(Token("SEMI", c, line)); i += 1
        else:
            errors.append(f"第 {line} 行：无法识别的字符 {c!r}")
            i += 1                          # 跳过坏字符，继续扫
    return tokens, errors
​

三个细节值得停一秒。标识符分支的内层 while 就是 2.2 节 DFA 状态 C 的自循环——"字母数字星号"落到了代码里。数字分支对小数点的判断做了"向前多看一个字符"，防止 3. 后面没有数字时误吞点号（点号可能属于下一个词素，比如成员访问的间隔符）。单字符运算符分支预留了扩展位：真要支持双等号、加等号这类双字符运算符，只需在分支里加一次双字符前瞻。

跑通主线语句

src = "total = price * qty - discount;"
tokens, errors = tokenize(src)
for t in tokens:
    print(t)
# 输出：
# (ID total 行1) (ASSIGN = 行1) (ID price 行1) (MUL * 行1)
# (ID qty 行1) (SUB - 行1) (ID discount 行1) (SEMI ; 行1)
print("错误数：", len(errors))   # 0
​

七加一共计八个单元，与第 2.1 节的表格逐项吻合。再喂几个刁钻输入验证边界：

tests = [
    "dis counter",        # 空格分隔：两个标识符，验证不粘连
    "discount",           # 无空格：一个标识符，验证最长匹配
    "3.14 + 42",          # 浮点与整数并存
    "pri@ce = 1",         # 非法字符 @ 夹在中间
]
for s in tests:
    tk, er = tokenize(s)
    print(s, "=>", [t.kind + ":" + t.lexeme for t in tk], "错误:", er)
# 关键输出（节选）：
# discount => ['ID:discount']                   最长匹配，未拆词
# pri@ce = 1 => ['ID:pri', 'ASSIGN:=', 'NUM:1'] 错误: 第 1 行：无法识别的字符 '@'
​

第四个用例最能说明问题：@ 被报错跳过后，扫描器恢复运行，ce 没有被无理吞掉，等号和数字 1 也完整切出。报错不中断是词法层错误处理的基本姿态，理由在 2.4 节展开。

手写分支与 DFA 的对应

把手写实现和 2.2 节的理论对上号，理解会深一层：

最后一行是手写实现的取巧之处：因为标识符、数字的词形互不重叠，按首字符分流后再贪心前进，天然达到最长匹配，不需要 DFA 那种"走到死路再回退"的机制。真到词形重叠的场合（比如 1e10 究竟是数字还是别的、两点号对上小数点），就得上真正的回退或双前瞻。工业级扫描器正是把这套前瞻判断写到极致，反而不再依赖生成器。

⚠️ 常见坑：用正则库直接切词（比如拿语言自带的正则引擎逐个模式尝试）。这隐含地把"最长匹配加优先级"交给正则引擎的默认规则，注释和字符串里的内容会被误切，嵌套场景（字符串里又有引号）更是直接出错。扫描器可以用正则库做零件，但不能把整个控制权交出去。

💡 关键直觉：这份百行扫描器的价值不在能用，而在可改。想加一种新词法类别（比如单行注释），只需加一个分支；想改标识符规则（比如允许美元符），改一处条件。生成器改规则要重学工具语法，手写版改的是你完全理解的东西——教学与原型场景，手写完胜。

本节要点回顾

• 结构：主循环按首字符分流，分支即 DFA 转移表的手写展开
• 最长匹配：内层 while 贪心前进，靠词形不重叠回避显式回退
• 边界处理：小数点双前瞻、关键字查表在最长匹配之后
• 验证方法：刁钻输入打边界——无空格粘连、非法字符夹心、浮点整数并存
• 取舍：手写版透明可改，生成器版省力规范，工程上两者共存各有阵地

下一节专讲输入不干净时的完整策略：错误信息怎么写才有用，恢复怎么做才不会吞掉真正的病灶。