Phoenix 词法分析器的设计与实现

2026-07-29 #Rust #编译原理 #Phoenix 24 min

Phoenix 是我编写的一门基于栈的逆波兰表示法语言，全部数值统一为 64 位浮点数。本文只讨论编译前端的第一个阶段，即词法分析器的实现：它如何把一段源文本切分为词法单元序列，为什么它可以用一种相当简单的结构写成，以及当前实现中还有哪些值得改进的地方。

一、语言的词法结构

在动手实现之前，先把需要识别的词法单元列清楚。Phoenix 的词法集合非常小：

对应的类型定义如下：

#[derive(Debug, PartialEq, Clone)]
pub enum Token {
    EOF,
    Placeholder,

    Operator(char),
    Identifier(String),
    Digit(f64),

    Def,
    If,
    Else,
    Dow,
    Dollar, // $
    Var,

    LeftBracket,  // {
    RightBracket, // }

    Print,
    Printa,
}

这张表里有一个特征值得特别指出：所有符号类的词法单元都只有一个字符。语言中不存在 ==、>=、->、+= 这类由多个字符组成的运算符。这个特征将在后面反复起作用。

二、扫描器：三个原语

词法分析器的底层是一个游标结构 Scanner，它持有整份源文本和一个当前位置：

pub struct Scanner {
    chars: Vec<char>,
    current_idx: usize,
}

impl Scanner {
    pub fn new(contents: String) -> Self {
        Self {
            chars: contents.chars().collect(),
            current_idx: 0,
        }
    }
}

在此之上只定义了三个方法：

fn peek(&self) -> Option<char> {
    self.chars.get(self.current_idx).copied()
}

fn advance(&mut self) -> Option<char> {
    let c = self.peek()?;
    self.current_idx += 1;
    Some(c)
}

fn take_while(&mut self, pred: impl Fn(char) -> bool) -> String {
    let mut s = String::new();
    while let Some(c) = self.peek() {
        if !pred(c) {
            break;
        }
        s.push(c);
        self.current_idx += 1;
    }
    s
}

三者的分工是明确的：

• peek 观察但不消耗。它提供做出判断所需的信息，同时保证游标状态不变。
• advance 消耗一个字符，游标前进一位。
• take_while 连续消耗满足谓词的字符，直到遇到第一个不满足的字符为止，并把消耗掉的部分作为字符串返回。

有一处不变式必须强调：take_while 在谓词失败时执行的是 break，它不会消耗那个导致失败的字符。这与 Rust 标准库中 Iterator::take_while 的语义恰好相反——标准库版本会把第一个不满足谓词的元素也取走并丢弃。如果在这里沿用了标准库的语义，源文本 x! 中的 ! 就会在读取标识符 x 时被吞掉，导致存储操作丢失。整个词法分析器能够正常工作，很大程度上依赖于这条不变式。

三、为什么三个原语就足够

这套接口之所以够用，是由两方面共同决定的：一方面是理论上的界限，另一方面是 Phoenix 自身的语言设计。

3.1 理论背景

绝大多数编程语言的词法结构是正则的，也就是说，每一类词法单元构成的字符串集合都可以被某个确定性有限自动机（deterministic finite automaton，通常缩写为 DFA）识别。确定性有限自动机的核心性质是状态数有限且与输入长度无关，因此它严格地从左向右单向读入，不需要回退，时间复杂度为输入长度的线性函数，空间复杂度为常数。

手写的扫描器实际上就是把这样一台自动机用程序的控制流编码出来。自动机的当前状态并没有保存在某个变量里，而是体现为程序执行到了哪一个分支、哪一行代码。三个原语与自动机的基本操作一一对应：peek 对应观察下一个输入符号以选择状态转移，advance 对应执行一次转移，take_while 则对应一个自环状态，等价于正则表达式中的 [字符类]*，并且天然实现了最长匹配（maximal munch）。

需要澄清的是，这套写法并不是“不需要回退”，而是用有限的前瞻替代了回退。核心原则可以概括为一句话：

先做判断，再执行消耗。

只要判断所需的信息可以在不改变游标状态的前提下获得，就永远不会出现“消耗之后才发现不该消耗”的局面。

3.2 语言设计层面的原因

理论上的可能性并不自动带来实现上的简单。Phoenix 的词法分析器之所以可以写得如此紧凑，是以下几个设计决策共同作用的结果：

1. 符号类词法单元全部是单字符的。语言使用 = 表示相等、~ 表示不等，从而回避了 C 语言家族中 = 与 == 的经典二义性。这意味着看到第一个字符，词法单元的种类就已经唯一确定，一个字符的前瞻就足够做出全部分派决策。

2. 语言中没有字符串字面量。字符输出通过 32 printa 这样的方式完成。这一条绕开了整类问题：转义序列 \" 需要在扫描过程中携带一个转义标志，字符串插值需要在词法单元内部嵌套完整的表达式，原始字符串需要匹配可变长度的定界符。这些都是 take_while 无法表达的形态。

3. 注释使用单字符定界且不允许嵌套。[ ... ] 的结构使得跳过注释只需要向前扫描到第一个 ]。如果允许嵌套注释，注释体就不再是正则语言，必须引入一个深度计数器，扫描器也就不再是一台有限自动机。

4. 数值类型只有 64 位浮点数一种。没有 1u8、1.0f32、0x1F、1_000 这类类型后缀、进制前缀和分隔符，数值字面量的词法规则因此极为简单。

5. 函数调用使用独立的前缀符号 $。$foo 中的 $ 先被消耗，随后再读取名字，两步互不干扰。如果函数调用写作 foo(...)，就需要在读完标识符后再判断下一个字符是否为左括号，这类判断本应属于语法分析阶段。

四、主循环：先消费后分派

顶层函数 lexer 接管扫描器，反复取出词法单元直到输入耗尽：

pub fn lexer(mut scanner: Scanner) -> Vec<Token> {
    let mut tokens = Vec::<Token>::new();
    loop {
        let character = match scanner.advance() {
            Some(character) => character,
            None => {
                tokens.push(Token::EOF);
                break;
            }
        };

        if character.is_whitespace() {
            continue;
        };

        if character == '[' {
            scanner.skip_comment();
            continue;
        }

        // ... 后续分支
    }
    tokens
}

这里有一个实现选择值得单独说明。主循环采用的是先消费、后分派：它调用 advance 取出一个字符，再根据这个字符决定进入哪一个分支。而更常见的写法是先观察、后分派，即用 peek 拿到字符做判断，把消耗完全交给各个分支内部。

先消费的写法在这里能够成立，恰恰是因为前面提到的性质：分派是完备的，第一个字符唯一决定了词法单元的种类，因此提前消耗不会造成任何损失。换句话说，当前实现能够采用这种写法，本身就是语言词法在首字符上前缀无关的一个证明。

它的代价体现在代码形态上。由于首字符已经被取走，扫描标识符时必须把它重新拼接回去：

let mut partial = String::from(character);
partial.push_str(&scanner.take_while(|c| c.is_alphanumeric() || c == '_'));

如果改为先观察后分派，这两行可以合并为一行，因为 take_while 能够从首字符开始一次性读完整个词：

let word = scanner.take_while(|c| c.is_alphanumeric() || c == '_');

两种写法都是正确的，但后者在结构上更为统一：每一类词法单元的扫描逻辑都完整地封闭在自己的分支内部，主循环只负责分派。

五、各类词法单元的扫描

5.1 空白与注释

空白字符直接跳过，不产生任何词法单元。注释的处理由 skip_comment 承担：

fn skip_comment(&mut self) {
    while let Some(c) = self.advance() {
        if c == ']' {
            return;
        }
    }
}

进入该方法时，[ 已经在主循环中被消耗，因此这里只需向前推进到第一个 ]。

5.2 数值字面量

if character.is_ascii_digit() || character == '.' {
    let mut partial = String::from(character);
    partial.push_str(&scanner.take_while(|c| c.is_ascii_digit() || c == '.'));
    let digit: f64 = partial
        .parse()
        .expect(format!("Invalid token: {}", partial).as_str());
    tokens.push(Token::Digit(digit));
    continue;
}

这里采用的策略值得单独命名：它并没有把数值的自动机结构编码进控制流，而是先扫描一个超集，再交由 f64::from_str 做最终裁决。谓词 c.is_ascii_digit() || c == '.' 会接受 1.2.3 这样明显非法的输入，真正的合法性判断被推迟到了字符串解析这一步。

这是一种在实践中相当常见的技巧。它的好处是彻底回避了一个麻烦：如果按照标准的自动机结构逐状态实现，扫描器在读入小数点之后会进入一个“尚未接受”的中间状态，此时若下一个字符不是数字，就需要决定是报错还是回退。采用扫描超集的策略，就把这个决策整体交给了一个现成的、经过充分测试的解析函数。

代价是错误处理的位置发生了转移，这一点在第七节讨论。

5.3 标识符与关键字

if character.is_alphabetic() || character == '_' {
    let mut partial = String::from(character);
    partial.push_str(&scanner.take_while(|c| c.is_alphanumeric() || c == '_'));

    if vec!["def", "dow", "if", "else", "print", "printa", "var"]
        .contains(&partial.as_str())
    {
        match partial.as_str() {
            "def" => tokens.push(Token::Def),
            "dow" => tokens.push(Token::Dow),
            "if" => tokens.push(Token::If),
            "else" => tokens.push(Token::Else),
            "print" => tokens.push(Token::Print),
            "printa" => tokens.push(Token::Printa),
            "var" => tokens.push(Token::Var),
            &_ => eprintln!("Undefined situation"),
        }
    } else {
        tokens.push(Token::Identifier(partial));
    }
    continue;
}

关键字与标识符共用同一条扫描路径：先按标识符规则读出完整的词，再查表判断它是否为关键字。这一步不是可有可无的优化，而是正确性的前提。

考虑一个具体场景。Phoenix 同时拥有 print 和 printa 两个关键字，前者是后者的真前缀。如果扫描器采用“直接匹配关键字字符串”的策略，源文本中的 printa 就会被切分为 print 和标识符 a 两个词法单元。同样地，变量名 dowx 会被误切为关键字 dow 加标识符 x。take_while 提供的最长匹配语义正好堵住了这个漏洞：它先把整个词读完，再判断词的身份。

从形式语言的角度看，这一步的合法性来自正则语言对补运算和差运算的封闭性——“是标识符但不是关键字”的集合仍然是正则语言，因此可以先识别较大的集合，再用查表把关键字从中分离出来，而不必为每个关键字单独编写状态机。

5.4 单字符符号

剩下的分支都是单字符匹配，不需要任何前瞻：

if vec!['+', '-', '*', '/', '!', '=', '~', '>', '<'].contains(&character) {
    tokens.push(Token::Operator(character));
    continue;
}

if character == '{' {
    tokens.push(Token::LeftBracket);
    continue;
}

if character == '}' {
    tokens.push(Token::RightBracket);
    continue;
}

if character == '$' {
    tokens.push(Token::Dollar);
    continue;
}

六、实现中的若干取舍

6.1 字符向量与索引

Scanner 把源文本预先收集为 Vec<char>，游标是字符下标而非字节偏移。这个选择有明确的收益：peek 是常数时间的下标访问，索引算术不必考虑 UTF-8 变长编码，current_idx += 1 永远是正确的。

代价有两处。其一是启动时需要一次完整的遍历和一次与源文本等量的内存分配。其二是失去了零拷贝的可能：由于底层不再是连续的 &str，take_while 只能逐字符构造一个新的 String，每个标识符和每个数值字面量都对应一次堆分配。

对于当前规模的语言，这个取舍是合理的。工业级实现（例如 rustc_lexer）通常持有 &str 并使用字节偏移，take_while 返回源文本的切片而非新字符串，从而做到零拷贝，但相应地必须小心处理字符边界与列号计算。

6.2 take_while 的分配开销

skip_comment 目前用 advance 循环实现，因此不产生分配。但如果未来把它改写为 take_while(|c| c != ']') 以求形式统一，就会把整个注释体复制到一个随即丢弃的 String 中。

更合适的做法是把这个原语拆成两个：

fn skip_while(&mut self, pred: impl Fn(char) -> bool) {
    while let Some(c) = self.peek() {
        if !pred(c) {
            break;
        }
        self.current_idx += 1;
    }
}

fn take_while(&mut self, pred: impl Fn(char) -> bool) -> String {
    let start = self.current_idx;
    self.skip_while(pred);
    self.chars[start..self.current_idx].iter().collect()
}

需要保留内容的场合使用 take_while，只需推进游标的场合使用 skip_while。

6.3 Operator(char) 的粒度

当前把 + - * / ! = ~ > < 统一归入 Operator(char)。这样做的好处是词法层的代码简短，新增运算符不需要修改枚举。

代价是把区分的工作推迟到了语法分析阶段：语法分析器拿到 Operator('+') 之后仍然要再做一次字符匹配。同时，! 在语义上是存储操作而不是算术运算符，把它与 + 归为一类掩盖了这一区别。如果为每个运算符定义独立的变体，编译器就能在 match 处提供穷尽性检查，非法状态在类型层面即不可表达。

这是简洁性与类型安全之间的权衡，两种选择都能找到成熟项目的先例。

七、已知缺陷与改进方向

以下几点是当前实现中确实存在的问题，按影响程度排列。

7.1 词法单元不携带位置信息

Token 枚举中没有任何字段记录该词法单元在源文本中的位置。这意味着后续阶段一旦发现错误，只能报告“某处有问题”，无法指出具体的行号与列号。对于任何面向使用者的语言实现，这是最需要优先解决的缺陷。

由于 Scanner 已经维护了 current_idx，补充这一信息的成本很低：

#[derive(Debug, Clone, PartialEq)]
pub struct Spanned {
    pub token: Token,
    pub start: usize,
    pub end: usize,
}

在主循环中记录进入分支前的 current_idx 作为 start，产生词法单元时的 current_idx 作为 end 即可。行号与列号可以在需要报错时，由字节偏移或字符偏移反查得到，不必在扫描过程中实时维护。

7.2 错误通过 panic 报告

数值解析使用了 expect：

.expect(format!("Invalid token: {}", partial).as_str())

源文本中一个 1.2.3 就会导致整个进程终止。这里存在两个独立的问题。

其一是错误处理方式。使用者的语法错误属于可预期的输入，不是程序缺陷，应当作为值返回而非触发 panic。可行的改造是让扫描函数返回 Result：

#[derive(Debug, Clone, PartialEq)]
pub enum LexError {
    UnexpectedChar { ch: char, at: usize },
    UnterminatedComment { at: usize },
    MalformedNumber { at: usize, text: String },
}

其二是性能细节。expect 接受 &str 参数，因此其中的 format! 在每一次调用时都会被求值并分配，即使解析成功。正确的写法是 unwrap_or_else(|_| panic!(...))，把格式化推迟到失败路径。

7.3 未终止的注释被静默接受

skip_comment 在遇到输入结束时直接返回，不报告任何异常。源文本中一个遗漏了 ] 的注释会静默吞掉文件的剩余全部内容，而使用者只会看到程序行为异常，得不到任何提示。改进方式是区分两种终止原因：

fn skip_comment(&mut self) -> Result<(), LexError> {
    let at = self.current_idx;
    self.skip_while(|c| c != ']');
    match self.advance() {
        Some(_) => Ok(()),
        None => Err(LexError::UnterminatedComment { at }),
    }
}

7.4 无法识别的字符被静默丢弃

主循环的最后一个分支是 if character == '$'。如果输入字符不匹配任何分支，循环会直接进入下一轮，既不产生词法单元，也不发出任何警告。源文本中出现 @ 或 # 时，它们会被无声地忽略。

把一连串 if 改写为 match 并显式提供兜底分支，可以让编译器帮助确认所有情况都已覆盖：

match character {
    c if c.is_whitespace() => continue,
    '[' => scanner.skip_comment()?,
    c if c.is_ascii_digit() || c == '.' => { /* ... */ }
    c if c.is_alphabetic() || c == '_' => { /* ... */ }
    '+' | '-' | '*' | '/' | '!' | '=' | '~' | '>' | '<' => {
        tokens.push(Token::Operator(character))
    }
    '{' => tokens.push(Token::LeftBracket),
    '}' => tokens.push(Token::RightBracket),
    '$' => tokens.push(Token::Dollar),
    c => return Err(LexError::UnexpectedChar { ch: c, at: scanner.current_idx }),
}

7.5 关键字查表的冗余

当前实现先用 vec![...].contains(...) 判断是否为关键字，再用 match 确定是哪一个，同一份数据被查询了两次，并且每识别一个标识符就构造一次临时 Vec。一个返回 Option 的辅助函数可以同时完成两件事，且不产生任何分配：

fn keyword(word: &str) -> Option<Token> {
    match word {
        "def" => Some(Token::Def),
        "dow" => Some(Token::Dow),
        "if" => Some(Token::If),
        "else" => Some(Token::Else),
        "print" => Some(Token::Print),
        "printa" => Some(Token::Printa),
        "var" => Some(Token::Var),
        _ => None,
    }
}

调用处只需一行：

tokens.push(keyword(&word).unwrap_or(Token::Identifier(word)));

7.6 标识符的字符集范围

is_alphabetic 与 is_alphanumeric 是 Unicode 感知的，因此当前实现允许 变量 这样的标识符。这未必是有意为之，但它是一个需要明确表态的设计决策：如果希望限制为 ASCII，应改用 is_ascii_alphabetic 与 is_ascii_alphanumeric；如果希望正式支持 Unicode 标识符，则应参照 UAX #31 定义 XID_Start 与 XID_Continue，并考虑规范化问题。

八、词法层的设计边界

最后有必要记录一件事：当前这套实现的简洁性是有条件的，条件就是第三节列出的那几项语言设计决策。任何一项发生变化，实现复杂度都会相应上升。按代价从小到大排列：

1. 只需要把前瞻长度从一个字符提升到两个字符。增加 >=、<=、~= 这类双字符运算符，或者把 -> 从注释内容提升为正式语法，或者引入 // 行注释（此时需要与除法运算符 / 区分）。改造方式是为 Scanner 增加 peek_nth(n) 方法，主循环改为先观察后分派。

2. 需要在扫描过程中携带状态，take_while 不再适用，但词法仍然是正则的。典型例子是带转义序列的字符串字面量：扫描器必须维护一个布尔标志来记录前一个字符是否为反斜杠。这类扫描只能退回到 loop { peek; advance } 的手写循环，但由于标志只有有限种取值，语言本身依然属于正则语言。

3. 破坏正则性，必须引入计数器或栈。嵌套注释 [[ ... ]] 需要一个深度计数器，字符串插值需要在词法单元内部递归调用扫描器。此时扫描器已经不再是有限自动机，而是一台退化的下推自动机。

4. 词法层无法独立解决的情况。最典型的是负数字面量。当前 - 只承担二元减法。如果希望支持 -5 作为字面量，就会遇到 5 -5 - 这类输入应当如何切分的问题——这是一个真正的二义性，无法在词法层单独消解，只能依靠“负号必须紧贴数字且其前必须是空白”这类附加规则，或者引入一个独立的取负运算符。

明确这条边界的价值在于：它把“实现写得简单”从一种运气转化为一项可以主动维护的性质。在为语言添加新特性时，可以先判断该特性落在上述哪一档，从而预先知道需要付出的代价。

九、小结

Phoenix 的词法分析器建立在三个原语之上：peek 负责观察，advance 负责消耗单个字符，take_while 负责消耗一段连续的字符类。这三者足以覆盖全部词法单元，其根本原因在于语言的词法在首字符上是前缀无关的——看到第一个字符就能唯一确定词法单元的种类，因此一个字符的前瞻可以完全替代回退。

当前实现在结构上是正确且清晰的，主要的改进空间集中在工程层面：补充位置信息、把 panic 改为 Result、为未终止注释和未知字符提供明确的诊断。这些改动都不涉及扫描逻辑本身，属于在既有骨架上的增量完善。