词法分析器

词法单元

词法分析器，也称为分词器或扫描器，负责将源文本转换为词法单元（Token）。 这些词法单元稍后将被解析器消费，因此我们不必担心原始文本中的空白和注释。

让我们从简单的开始，将单个 + 文本转换为一个词法单元。

#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Token {
    /// 词法单元类型
    pub kind: Kind,

    /// 源代码中的起始偏移量
    pub start: usize,

    /// 源代码中的结束偏移量
    pub end: usize,
}

#[derive(Debug, Clone, Copy, PartialEq)]
pub enum Kind {
    Eof, // 文件结束
    Plus,
}

单个 + 给我们

[
    Token { kind: Kind::Plus, start: 0, end: 1 },
    Token { kind: Kind::Eof,  start: 1, end: 1 }
]

要遍历字符串，我们可以跟踪一个索引并假装我们在写 C 代码， 或者我们可以查看 字符串文档 并找到一个 Chars 迭代器来使用。

INFO

Chars 迭代器抽象了跟踪索引和边界检查，让我们感到真正的安全。

当我们调用 chars.next() 时，它会给我们一个 Option<char>。 但请注意，char 不是 0-255 的 ASCII 值， 它是一个 utf8 Unicode 码点值，范围是 0 到 0x10FFFF。

让我们定义一个入门的词法分析器抽象

use std::str::Chars;

struct Lexer<'a> {
    /// 源文本
    source: &'a str,

    /// 剩余字符
    chars: Chars<'a>
}

impl<'a> Lexer<'a> {
    pub fn new(source: &'a str) -> Self {
        Self {
            source,
            chars: source.chars()
        }
    }
}

INFO

这里的生命周期 'a 表示迭代器有一个对某处的引用，在这个例子中它引用了一个 &'a str。

要将源文本转换为词法单元，只需不断调用 chars.next() 并匹配返回的 char。 最后一个词法单元将始终是 Kind::Eof。

impl<'a> Lexer<'a> {
    fn read_next_kind(&mut self) -> Kind {
        while let Some(c) = self.chars.next() {
            match c {
              '+' => return Kind::Plus,
              _ => {}
            }
        }
        Kind::Eof
    }

    fn read_next_token(&mut self) -> Token {
        let start = self.offset();
        let kind = self.read_next_kind();
        let end = self.offset();
        Token { kind, start, end }
    }

    /// 获取源文本的长度偏移量，以 UTF-8 字节为单位
    fn offset(&self) -> usize {
        self.source.len() - self.chars.as_str().len()
    }
}

fn offset 中的 .len() 和 .as_str().len() 方法调用感觉像是 O(n)，所以让我们深入挖掘。

.as_str() 返回一个指向字符串切片的指针

// https://github.com/rust-lang/rust/blob/b998821e4c51c44a9ebee395c91323c374236bbb/library/core/src/str/iter.rs#L112-L115

pub fn as_str(&self) -> &'a str {
    // SAFETY: `Chars` is only made from a str, which guarantees the iter is valid UTF-8.
    unsafe { from_utf8_unchecked(self.iter.as_slice()) }
}

切片 是一个指向内存块的视图，表示为一个指针和一个长度。 .len() 方法返回存储在切片中的元数据

// https://github.com/rust-lang/rust/blob/b998821e4c51c44a9ebee395c91323c374236bbb/library/core/src/str/mod.rs#L157-L159

pub const fn len(&self) -> usize {
    self.as_bytes().len()
}

// https://github.com/rust-lang/rust/blob/b998821e4c51c44a9ebee395c91323c374236bbb/library/core/src/str/mod.rs#L323-L325

pub const fn as_bytes(&self) -> &[u8] {
    // SAFETY: const sound because we transmute two types with the same layout
    unsafe { mem::transmute(self) }
}

// https://github.com/rust-lang/rust/blob/b998821e4c51c44a9ebee395c91323c374236bbb/library/core/src/slice/mod.rs#L129-L138

pub const fn len(&self) -> usize {
    // FIXME: Replace with `crate::ptr::metadata(self)` when that is const-stable.
    // As of this writing this causes a "Const-stable functions can only call other
    // const-stable functions" error.

    // SAFETY: Accessing the value from the `PtrRepr` union is safe since *const T
    // and PtrComponents<T> have the same memory layouts. Only std can make this
    // guarantee.
    unsafe { crate::ptr::PtrRepr { const_ptr: self }.components.metadata }
}

所有上述代码将被编译成单个数据访问，所以 .as_str().len() 实际上是 O(1)。

向前看

要对多字符运算符（如 ++ 或 +=）进行分词，需要一个辅助函数 peek：

fn peek(&self) -> Option<char> {
    self.chars.clone().next()
}

我们不想推进原始的 chars 迭代器，所以我们克隆迭代器并推进索引。

INFO

如果我们深入研究源代码，clone 是很便宜的， 它只是复制跟踪索引和边界索引。

// https://github.com/rust-lang/rust/blob/b998821e4c51c44a9ebee395c91323c374236bbb/library/core/src/slice/iter.rs#L148-L152

impl<T> Clone for Iter<'_, T> {
    fn clone(&self) -> Self {
        Iter { ptr: self.ptr, end: self.end, _marker: self._marker }
    }
}

peek 和 chars.next() 的区别在于前者始终返回相同的下一个 char， 而后者会向前移动并返回不同的 char。

为了演示，考虑字符串 abc：

• 重复调用 peek() 返回 Some(a)、Some(a)、Some(a)、...
• 重复调用 chars.next() 返回 Some('a')、Some('b')、Some('c')、None。

有了 peek，对 ++ 和 += 进行分词就只是嵌套的 if 语句。

这是 jsparagus 的一个真实实现：

// https://github.com/mozilla-spidermonkey/jsparagus/blob/master/crates/parser/src/lexer.rs#L1769-L1791

'+' => match self.peek() {
    Some('+') => {
        self.chars.next();
        return self.set_result(
            TerminalId::Increment,
            SourceLocation::new(start, self.offset()),
            TokenValue::None,
        );
    }
    Some('=') => {
        self.chars.next();
        return self.set_result(
            TerminalId::AddAssign,
            SourceLocation::new(start, self.offset()),
            TokenValue::None,
        );
    }
    _ => return self.set_result(
        TerminalId::Plus,
        SourceLocation::new(start, self.offset()),
        TokenValue::None,
    ),
},

上述逻辑适用于所有运算符，所以让我们扩展对 JavaScript 词法分析的知识。

JavaScript

用 Rust 编写的词法分析器相当无聊，感觉像是在写 C 代码， 我们编写长长的链式 if 语句，检查每个 char，然后返回相应的词法单元。

真正的乐趣开始于我们为 JavaScript 进行词法分析时。

让我们打开 ECMAScript 语言规范 并重新学习 JavaScript。

TIP

我仍然记得我第一次打开规范时，我躲在一个小角落里痛苦地哭泣， 因为感觉就像在读充满术语的外语文本。 所以如果事情不太明白，请去看看我的规范阅读指南。

注释

注释没有语义意义，如果我们编写运行时，可以跳过它们， 但如果我们编写 linter 或 bundler，则需要考虑它们。

标识符和 Unicode

我们主要用 ASCII 编码， 但 第 11 章 ECMAScript 语言：源文本 规定源文本应该是 Unicode。 第 12.6 章 名称和关键字 规定标识符根据 Unicode 标准附录 #31 中给出的默认标识符语法进行解释。 详细说明：

IdentifierStartChar ::
    UnicodeIDStart

IdentifierPartChar ::
    UnicodeIDContinue

UnicodeIDStart ::
    any Unicode code point with the Unicode property "ID_Start"

UnicodeIDContinue ::
    any Unicode code point with the Unicode property "ID_Continue"

这意味着我们可以写 var ಠ_ಠ 但不能写 var 🦀， ಠ 具有 Unicode 属性 "ID_Start"，而 🦀 没有。

INFO

我发布了 unicode-id-start crate 正是为了这个目的。 可以调用 unicode_id_start::is_id_start(char) 和 unicode_id_start::is_id_continue(char) 来检查 Unicode。

关键字

所有关键字，如 if、while 和 for 都需要被分词并作为一个整体解释。 它们需要被添加到词法单元类型枚举中，这样我们就不必在解析器中进行字符串比较。

pub enum Kind {
    Identifier,
    If,
    While,
    For
}

TIP

undefined 不是关键字，这里不需要添加它。

对关键字进行分词就是匹配上面的标识符。

fn match_keyword(&self, ident: &str) -> Kind {
    // 所有关键字的长度都是 1 < length <= 10
    if ident.len() == 1 || ident.len() > 10 {
        return Kind::Identifier;
    }
    match ident {
        "if" => Kind::If,
        "while" => Kind::While,
        "for" => Kind::For,
        _ => Kind::Identifier
    }
}

词法单元值

在编译器后期的阶段，我们经常需要比较标识符、数字和字符串， 例如在 linter 中测试标识符。

这些值目前是纯源文本， 让我们将它们转换为 Rust 类型，以便更容易使用。

pub enum Kind {
    Eof, // 文件结束
    Plus,
    Identifier,
    Number,
    String,
}

#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Token {
    /// 词法单元类型
    pub kind: Kind,

    /// 源代码中的起始偏移量
    pub start: usize,

    /// 源代码中的结束偏移量
    pub end: usize,

    pub value: TokenValue,
}

#[derive(Debug, Clone, PartialEq)]
pub enum TokenValue {
    None,
    Number(f64),
    String(String),
}

当标识符 foo 或字符串 "bar" 被分词时，我们得到

Token { kind: Kind::Identifier, start: 0, end: 2, value: TokenValue::String("foo") }
Token { kind: Kind::String, start: 0, end: 4, value: TokenValue::String("bar") }

要将它们转换为 Rust 字符串，调用 let s = self.source[token.start..token.end].to_string() 并用 token.value = TokenValue::String(s) 保存它。

当我们对数字 1.23 进行分词时，我们得到一个带有 Token { start: 0, end: 3 } 的词法单元。 要将其转换为 Rust f64，我们可以使用字符串 parse 方法，调用 self.source[token.start..token.end].parse::<f64>()，然后将值保存到 token.value 中。 对于二进制、八进制和整数，可以在 jsparagus 中找到它们的解析技术示例。

Rust 优化

更小的词法单元

将词法单元值放在 Kind 枚举中以追求更简单、更安全的代码是很诱人的：

pub enum Kind {
    Number(f64),
    String(String),
}

但众所周知，Rust 枚举的字节大小是其所有变体的联合体。 与只有 1 字节的原始枚举相比，这个枚举占用了很多字节。 解析器中会大量使用这个 Kind 枚举， 处理一个 1 字节的枚举明显比处理多字节枚举更快。

字符串驻留

在编译器中使用 String 性能不佳，主要原因是：

• String 是堆分配对象
• 字符串比较是 O(n) 操作

字符串驻留 通过 在缓存中只存储每个不同字符串值的一个副本（带有唯一标识符）来解决这些问题。 每个不同的标识符或字符串只会有一次堆分配，字符串比较变成 O(1)。

crates.io 上有很多字符串驻留库， 各有不同的优缺点。

一个足够的起点是使用 string-cache， 它有一个 Atom 类型和一个编译时的 atom!("string") 接口。

有了 string-cache，TokenValue 变成

#[derive(Debug, Clone, PartialEq)]
pub enum TokenValue {
    None,
    Number(f64),
    String(Atom), 
}

字符串比较变成 matches!(value, TokenValue::String(atom!("string")))。