词法分析器

标记（Token）

词法分析器，也称为分词器或扫描器，负责将源代码文本转换为标记（tokens）。这些标记之后将由解析器消费，因此我们无需担心原始文本中的空白字符和注释。

让我们从简单开始，将单个 + 文本转换为一个标记。

rust

#[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 值，而是范围为 0 到 0x10FFFF 的 utf8 Unicode 码点值。

让我们定义一个基础的词法分析器抽象结构

rust

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。

rust

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() 返回一个指向字符串切片的指针

rust

// 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` 仅来自字符串，这保证了迭代器是有效的 UTF-8。
    unsafe { from_utf8_unchecked(self.iter.as_slice()) }
}

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

rust

// 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()
}

rust

// 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 安全，因为我们转换的是具有相同布局的两种类型
    unsafe { mem::transmute(self) }
}

rust

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

pub const fn len(&self) -> usize {
    // FIXME: 当该函数变为 const-stable 后，替换为 `crate::ptr::metadata(self)`。
    // 截至目前，这会导致 "Const-stable 函数只能调用其他 const-stable 函数" 错误。

    // SAFETY: 从 `PtrRepr` 联合体访问值是安全的，因为 *const T
    // 与 PtrComponents<T> 具有相同的内存布局。只有 std 可以做出此保证。
    unsafe { crate::ptr::PtrRepr { const_ptr: self }.components.metadata }
}

上述所有代码在编译后将合并为一次数据访问，因此 .as_str().len() 实际上是 O(1)。

预读（Peek）

为了对多字符操作符（如 ++ 或 +=）进行标记化，需要一个辅助函数 peek：

rust

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

我们不希望推进原始的 chars 迭代器，因此克隆迭代器并前进索引。

INFO

如果深入源码，我们会发现 clone 是廉价的，它只是复制了追踪和边界索引。

rust

// 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 中的真实实现：

rust

// 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

我仍然记得第一次打开规范时，躲到一个角落里痛哭流涕，因为感觉就像在阅读满是术语的外文文本。如果某些内容难以理解，请前往我的阅读规范指南。

注释

注释没有语义意义，如果我们正在编写运行时，可以跳过它们；但如果我们要编写一个检查器或打包工具，则必须考虑它们。

标识符与 Unicode

我们大多数时候使用 ASCII 编码，但第 11 章：源代码的 ECMAScript 语言指出源代码应为 Unicode 格式。而第 12.6 节：名称与关键字指出标识符应根据 Unicode 标准附录 #31 中给出的默认标识符语法解释。详细来说：

IdentifierStartChar ::
    UnicodeIDStart

IdentifierPartChar ::
    UnicodeIDContinue

UnicodeIDStart ::
    具有 Unicode 属性 “ID_Start” 的任意 Unicode 码点

UnicodeIDContinue ::
    具有 Unicode 属性 “ID_Continue” 的任意 Unicode 码点

这意味着我们可以编写 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 都需要被标记化，并作为整体进行解释。必须将它们添加到标记类型枚举中，以便在解析器中无需进行字符串比较。

rust

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

TIP

undefined 不是关键字，因此无需在此处添加。

标记关键字仅需匹配前面的标识符即可。

rust

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
    }
}

标记值

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

这些值目前仍以纯源文本形式存在，让我们将其转换为 Rust 类型，以便更方便地处理。

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 枚举中，以追求更简洁和更安全的代码：

rust

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

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

字符串驻留（String Interning）

在编译器中使用 String 并不高效，主要原因包括：

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

String Interning 通过在缓存中仅存储每个不同字符串值的一份副本及其唯一标识符来解决这些问题。每个不同标识符或字符串只需一次堆分配，字符串比较变为 O(1)。

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

一个合适的起点是使用 string-cache，它提供了一个 Atom 类型以及编译时常量 atom!("string") 接口。

使用 string-cache 后，TokenValue 变为

rust

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

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

词法分析器 ​

标记（Token） ​

预读（Peek） ​

JavaScript ​

注释 ​

标识符与 Unicode ​

关键字 ​

标记值 ​

Rust 优化 ​

更小的标记 ​

字符串驻留（String Interning） ​

词法分析器

标记（Token）

预读（Peek）

JavaScript

注释

标识符与 Unicode

关键字

标记值

Rust 优化

更小的标记

字符串驻留（String Interning）