从零编写现代编译器 02 - 词法分析器：把文本切成 Token

上一篇里，编译器能处理的输入是硬编码的——它只认识 fn main() -> i64 { return 42; } 这一个程序，Token 序列直接写死在代码里。换一个数字就得改编译器源码。这不叫编译，这叫字符串替换。

这一篇要做的事情：给 Sprout 写一个词法分析器（lexer），让它读入任意源文本，逐字符扫描，输出一串带位置信息的 Token。后续的解析器将消费这个 Token 流，而不再关心原始字符。

词法分析器做什么

编译器前端的第一道工序是词法分析。它的输入是源文件的字节流，输出是 Token 序列。每个 Token 标记了一段源文本的语法角色：这是一个关键字，那是一个整数字面量，这里是左括号，那里是分号。

词法分析器不关心 Token 之间的组合是否合法。return return return 在词法层面完全没有问题——三个 Return Token。判断组合是否合法是解析器的工作。词法分析器只负责切割。

类比一下：词法分析像把一段中文拆成词语，每个词标上词性。"我吃了三碗饭"变成 [我/代词] [吃/动词] [了/助词] [三/数词] [碗/量词] [饭/名词]。句子通不通顺，语法分析再管。

Token 类型定义

Sprout 语言当前阶段需要以下 Token 类型。随着语言特性增加，这个枚举会扩展，但骨架不会变。

#[derive(Debug, Clone, PartialEq)]
pub enum TokenKind {
    // 关键字
    Fn, Let, Mut, If, Else, While, Return, True, False,

    // 字面量
    Int(i64),
    Ident(String),

    // 运算符
    Plus, Minus, Star, Slash,           // + - * /
    EqEq, BangEq, Lt, Gt, LtEq, GtEq, // == != < > <= >=
    AndAnd, OrOr, Bang,                  // && || !
    Assign,                              // =

    // 分隔符
    LParen, RParen,                      // ( )
    LBrace, RBrace,                      // { }
    Semi, Colon, Comma,                  // ; : ,
    Arrow,                               // ->

    // 特殊
    Eof,
    Error(String),
}

几个设计决定：

• Int(i64) 把数值直接存进 Token。词法阶段就完成字符串到数字的转换，后续不再重复解析。
• Ident(String) 存储标识符文本。关键字匹配在扫描时完成——先按标识符规则扫描，再查表判断是否是关键字。
• Error(String) 不是异常，是一种正常的 Token 类型。遇到无法识别的字符时，lexer 生成一个 Error Token 并继续扫描。这样一次扫描就能报告所有词法错误，而不是在第一个错误处停下。

Span：每个 Token 的出生证明

光有 Token 类型不够。编译器报错时需要指出错误在源文件中的位置。所以每个 Token 都携带一个 Span，记录它在源文本中的字节偏移范围。

#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Span {
    pub start: usize,
    pub end: usize,
}

#[derive(Debug, Clone, PartialEq)]
pub struct Token {
    pub kind: TokenKind,
    pub span: Span,
}

对于源文本 fn main()：

Token	start	end	对应文本
Fn	0	2	fn
Ident("main")	3	7	main
LParen	7	8	(
RParen	8	9	)

Span 采用字节偏移而不是行列号。字节偏移是单调递增的整数，比较和切片都很快。需要显示行列号时，拿偏移值在源文本中反查换行符位置即可。这个转换只在报错时执行，不拖慢正常编译路径。

区间是左闭右开 [start, end)。source[span.start..span.end] 直接得到原始文本，不需要加一减一。

Lexer 结构

Lexer 持有源文本和当前扫描位置。它是一个状态机，但状态极简——只需要知道"现在看到第几个字节"。

pub struct Lexer<'src> {
    source: &'src str,
    pos: usize,
}

impl<'src> Lexer<'src> {
    pub fn new(source: &'src str) -> Self {
        Lexer { source, pos: 0 }
    }

    fn peek(&self) -> Option<char> {
        self.source[self.pos..].chars().next()
    }

    fn advance(&mut self) -> Option<char> {
        let ch = self.peek()?;
        self.pos += ch.len_utf8();
        Some(ch)
    }

    fn peek_second(&self) -> Option<char> {
        let mut chars = self.source[self.pos..].chars();
        chars.next();
        chars.next()
    }
}

peek 看当前字符但不移动位置，advance 消费当前字符并前进。peek_second 向前多看一个字符，用于识别双字符运算符。位置用字节偏移维护，advance 按 char 的 UTF-8 编码长度前进，确保不会切断多字节字符。

逐字符扫描

核心方法 next_token 每次调用返回一个 Token。扫描逻辑按当前字符分派：

pub fn next_token(&mut self) -> Token {
    self.skip_whitespace();

    let start = self.pos;

    let ch = match self.advance() {
        Some(ch) => ch,
        None => return Token {
            kind: TokenKind::Eof,
            span: Span { start, end: start },
        },
    };

    let kind = match ch {
        '(' => TokenKind::LParen,
        ')' => TokenKind::RParen,
        '{' => TokenKind::LBrace,
        '}' => TokenKind::RBrace,
        ';' => TokenKind::Semi,
        ':' => TokenKind::Colon,
        ',' => TokenKind::Comma,
        '+' => TokenKind::Plus,
        '*' => TokenKind::Star,
        '/' => TokenKind::Slash,

        '-' => {
            if self.peek() == Some('>') {
                self.advance();
                TokenKind::Arrow
            } else {
                TokenKind::Minus
            }
        }

        '=' => {
            if self.peek() == Some('=') {
                self.advance();
                TokenKind::EqEq
            } else {
                TokenKind::Assign
            }
        }

        '!' => {
            if self.peek() == Some('=') {
                self.advance();
                TokenKind::BangEq
            } else {
                TokenKind::Bang
            }
        }

        '<' => {
            if self.peek() == Some('=') {
                self.advance();
                TokenKind::LtEq
            } else {
                TokenKind::Lt
            }
        }

        '>' => {
            if self.peek() == Some('=') {
                self.advance();
                TokenKind::GtEq
            } else {
                TokenKind::Gt
            }
        }

        '&' => {
            if self.peek() == Some('&') {
                self.advance();
                TokenKind::AndAnd
            } else {
                TokenKind::Error(
                    format!("unexpected character: '{}'", ch)
                )
            }
        }

        '|' => {
            if self.peek() == Some('|') {
                self.advance();
                TokenKind::OrOr
            } else {
                TokenKind::Error(
                    format!("unexpected character: '{}'", ch)
                )
            }
        }

        '0'..='9' => return self.scan_integer(start),

        'a'..='z' | 'A'..='Z' | '_' => {
            return self.scan_identifier_or_keyword(start)
        }

        other => TokenKind::Error(
            format!("unexpected character: '{}'", other)
        ),
    };

    Token { kind, span: Span { start, end: self.pos } }
}

结构很直白：单字符 Token 匹配后直接返回对应类型；双字符 Token 先看第二个字符是否匹配，匹配就多消费一个字符，不匹配就退回单字符版本；数字和字母开头的字符分别进入专门的扫描函数。

跳过空白

空白字符（空格、制表符、换行符）对 Sprout 没有语法意义，直接跳过：

fn skip_whitespace(&mut self) {
    while let Some(ch) = self.peek() {
        if ch.is_ascii_whitespace() {
            self.advance();
        } else if ch == '/' && self.peek_second() == Some('/') {
            // 行注释：跳到行尾
            while let Some(c) = self.peek() {
                if c == '\n' { break; }
                self.advance();
            }
        } else {
            break;
        }
    }
}

行注释 // 的处理放在空白跳过里。遇到 // 后消费到行尾（不含换行符本身，换行符在下一轮被空白跳过逻辑消费）。注释像空白一样消失，不产生 Token。

这里有一个细节：/ 本身是除法运算符，// 是注释。lexer 在 skip_whitespace 中先检查 //，只有当 / 后面不是 / 时，才会在 next_token 的主分派中把它当除法处理。处理顺序保证了不冲突。

整数字面量

遇到数字字符后，继续消费连续的数字，然后将整段文本解析为 i64：

fn scan_integer(&mut self, start: usize) -> Token {
    while let Some('0'..='9') = self.peek() {
        self.advance();
    }
    let text = &self.source[start..self.pos];
    let kind = match text.parse::<i64>() {
        Ok(value) => TokenKind::Int(value),
        Err(_) => TokenKind::Error(
            format!("integer literal overflow: {}", text)
        ),
    };
    Token { kind, span: Span { start, end: self.pos } }
}

parse::<i64>() 失败时（通常是数字超过 i64::MAX = 9223372036854775807），lexer 不会崩溃，而是生成一个 Error Token，带上原始文本以便报错。Span 照常记录——即使是错误 Token，也要准确指出它在源文件的位置。

当前只支持十进制整数。十六进制 0x、八进制 0o、二进制 0b 前缀可以后续添加，扫描逻辑类似：检查 0 后面的前缀字符，再按对应基数扫描数字。

标识符与关键字

标识符以字母或下划线开头，后跟字母、数字或下划线。扫描完成后查关键字表：

fn scan_identifier_or_keyword(&mut self, start: usize) -> Token {
    while let Some(ch) = self.peek() {
        if ch.is_ascii_alphanumeric() || ch == '_' {
            self.advance();
        } else {
            break;
        }
    }
    let text = &self.source[start..self.pos];
    let kind = match text {
        "fn"     => TokenKind::Fn,
        "let"    => TokenKind::Let,
        "mut"    => TokenKind::Mut,
        "if"     => TokenKind::If,
        "else"   => TokenKind::Else,
        "while"  => TokenKind::While,
        "return" => TokenKind::Return,
        "true"   => TokenKind::True,
        "false"  => TokenKind::False,
        _        => TokenKind::Ident(text.to_string()),
    };
    Token { kind, span: Span { start, end: self.pos } }
}

关键字和标识符共用同一套扫描规则，区别只在最后一步的查表。这意味着 fn 是关键字，但 fn2 是合法标识符——因为 fn2 作为整体不匹配任何关键字。这种"先扫描再分类"的策略也叫最长匹配（maximal munch）：lexer 贪婪地消费尽可能多的字符，然后判断结果属于哪个类别。

双字符运算符的判定

双字符运算符的扫描遵循统一模式：看到第一个字符后，peek 第二个字符。如果第二个字符匹配，消费它并返回双字符 Token；否则返回单字符 Token。

以 < 和 <= 为例：

1. 读到 <，peek 下一个字符。
2. 下一个是 =？消费它，返回 LtEq。
3. 下一个不是 =？不消费，返回 Lt。

-> 也是同一模式。读到 -，peek 下一个。是 > 就返回 Arrow，不是就返回 Minus。

& 和 | 有点特殊：在 Sprout 中，单独的 & 和 | 没有意义（不支持位运算），所以如果第二个字符不匹配，直接生成 Error Token。这个设计选择值得解释——很多语言允许单独的 & 和 | 作为位运算符，但 Sprout 不需要位运算，提前拒绝这些字符可以避免用户写错了 && 而只写了 & 却得不到任何提示的情况。

双字符运算符的扫描顺序也有讲究。next_token 中是先匹配第一个字符，在匹配体内再看第二个字符。这意味着 lexer 永远不会把 <= 错误地切割成 < 加 =，因为 < 的处理分支总是会检查后面是否跟着 =。只要每个单字符 Token 的处理分支都正确检查了可能的双字符延伸，就不会出现切割错误。这就是最大吞噬原则在运算符层面的体现。

还有一个容易忽视的边界情况：源文件的最后一个字符是 < 时，peek 返回 None，不匹配 =，所以返回 Lt。不需要特殊处理文件末尾。

错误恢复

词法阶段的错误恢复策略很简单：遇到无法识别的字符，生成一个 Error Token，然后继续扫描下一个字符。lexer 不会因为一个 @ 就放弃整个文件。

输入: fn main@() { return 42; }

扫描结果：

Fn          [0, 2)     "fn"
Ident       [3, 7)     "main"
Error       [7, 8)     "@"     <- unexpected character: '@'
LParen      [8, 9)     "("
RParen      [9, 10)    ")"
LBrace      [11, 12)   "{"
Return      [13, 19)   "return"
Int(42)     [20, 22)   "42"
Semi        [22, 23)   ";"
RBrace      [24, 25)   "}"
Eof         [25, 25)

@ 变成了一个带 Span 的 Error Token。后面的 Token 照常产出。后续的解析器可以收集所有 Error Token，一次性报告给用户，而不是只报第一个。

这种策略对词法层面已经足够好。更复杂的错误恢复（比如缺少闭合括号）是解析器的责任。

完整扫描示例

把所有部分组合起来，提供一个便利函数把整个源文件扫描成 Token 列表：

pub fn tokenize(source: &str) -> Vec<Token> {
    let mut lexer = Lexer::new(source);
    let mut tokens = Vec::new();
    loop {
        let token = lexer.next_token();
        let is_eof = token.kind == TokenKind::Eof;
        tokens.push(token);
        if is_eof { break; }
    }
    tokens
}

用它扫描 fn main() -> i64 { return 42; }：

Fn              [0,  2)
Ident("main")   [3,  7)
LParen          [7,  8)
RParen          [8,  9)
Arrow           [10, 12)
Ident("i64")    [13, 16)
LBrace          [17, 18)
Return          [19, 25)
Int(42)         [26, 28)
Semi            [28, 29)
RBrace          [30, 31)
Eof             [31, 31)

注意 i64 在当前阶段被扫描为 Ident，不是关键字。这是故意的——i64 是类型名，它在解析器或语义分析阶段才获得特殊含义。词法分析器只管字符层面的分类。fn、return 这些保留字才在词法阶段就被识别为关键字，因为它们在任何上下文中都不能用作变量名。

再看一个带错误的输入 let x = 10 + @y;：

Let             [0,  3)
Ident("x")      [4,  5)
Assign          [6,  7)
Int(10)         [8,  10)
Plus            [11, 12)
Error("@")      [13, 14)
Ident("y")      [14, 15)
Semi            [15, 16)
Eof             [16, 16)

@ 被记录为错误，但 y 和分号照常识别。编译器可以在收集完所有 Token 后，统一报告第 13 字节处有一个无法识别的字符。

测试 lexer

词法分析器的测试写起来很机械，但不可省略。每新增一类 Token，至少覆盖正常情况和边界情况：

#[test]
fn test_arrow_vs_minus() {
    let tokens = tokenize("->-");
    assert_eq!(tokens[0].kind, TokenKind::Arrow);
    assert_eq!(tokens[1].kind, TokenKind::Minus);
}

#[test]
fn test_integer_overflow() {
    let tokens = tokenize("99999999999999999999");
    assert!(matches!(tokens[0].kind, TokenKind::Error(_)));
}

#[test]
fn test_keyword_prefix_is_identifier() {
    // "return_value" 不是关键字 return
    let tokens = tokenize("return_value");
    assert!(matches!(tokens[0].kind,
        TokenKind::Ident(ref s) if s == "return_value"));
}

第三个测试很关键：它验证最长匹配规则。return_value 整体是一个标识符，lexer 不能在 return 处切断然后把 _value 当作另一个 Token。

测试用例的选取原则是覆盖每一类 Token 的正常路径和边界条件。对于整数，边界条件是零、最大值、溢出值。对于标识符，边界条件是单字符标识符、关键字前缀、下划线开头的名字。对于运算符，边界条件是相邻的双字符运算符（如 <=->，应该被切成 LtEq、Arrow 还是 Lt、Assign、Gt？答案是 LtEq 后面跟 Arrow——最长匹配决定了这一点）。每次新增 Token 类型时，配套的测试用例是交付的一部分，不是可选项。

练习

1. 给 lexer 添加 // 行注释支持（如果你从头跟着写，这部分已经在 skip_whitespace 中实现了）。扫描下面这段程序，验证注释被完整跳过，Token 流中不包含注释内容：

fn main() -> i64 {
    // 返回程序退出码
    return 0; // exit code
}

预期 Token 流：Fn, Ident("main"), LParen, RParen, Arrow, Ident("i64"), LBrace, Return, Int(0), Semi, RBrace, Eof。两条注释都消失了。

2. 思考题：如果未来 Sprout 要支持块注释 /* ... */，需要处理嵌套（/* outer /* inner */ still comment */）吗？嵌套块注释和非嵌套块注释在 lexer 实现上有什么区别？

---

上一篇：01 - return 42：从源码到可执行文件
下一篇：03 - 语句解析：let、赋值和分号