词法分析器

Token

词法分析器，也称为标记分析器或扫描器，负责将源文本转换至 Token。这些 Token 之后会被解析器使用，因此我们不必再担心原始文本中的空白和注释。

让我们从简单部分开始，将单个 + 文本转换成 Token。

#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Token {
    /// Token Type
    pub kind: Kind,

    /// Start offset in source
    pub start: usize,

    /// End offset in source
    pub end: usize,
}

#[derive(Debug, Clone, Copy, PartialEq)]
pub enum Kind {
    Eof, // end of file
    Plus,
}

单个 + 会产生下列结果

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

为了循环遍历该字符串，我们可以跟踪它的索引并假装自己在编写 C 代码，也可以查看 字符串文档，找到 Chars 迭代器并使用它。

提示

Chars 迭代器汇总抽象索引和边界检查，让我们真正安心。

当我们调用 chars.next() 时，它会向我们提供 Option<char>。但请注意，char 并非 0-255 的 ASCII 值，它是一个 0 至 0x10FFFF 范围内的 utf8 Unicode 点值。

让我们定义一个启动词法分析器抽象

use std::str::Chars;

struct Lexer<'a> {
    /// Source Text
    source: &'a str,

    /// The remaining characters
    chars: Chars<'a>
}

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

提示

此处的生命周期 'a 表明迭代器对某处有引用，在此情况下，它引用 &'a str。

要将源文本转换成 Token，只需继续调用 chars.next() 即可，并匹配返回的 char。最后的 Token 始终是 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 }
    }

    /// Get the length offset from the source text, in UTF-8 bytes
    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

要标记 ++ 或 += 等多字符运算符，需要一个助手函数peek

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

不想推进一步原始chars迭代器，所以克隆迭代器并推进索引。

提示

如果深入到源代码，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。

提示

我还记得我第一次打开规范时，躲到一个小角落里痛苦地哭泣，因为感觉就像在读外语，到处都是行话。因此，如果事情没有意义，请转到我的规范阅读指南。

注释

注释没有语义含义，如果我们编写的是运行时，可以跳过它们，但如果我们编写的是 linter 或打包器，则需要考虑它们。

标识符和 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”，而 🦀 没有。

提示

我发布了 unicode-id-start 箱体，目的正是如此。可以调用 unicode_id_start::is_id_start(char) 和 unicode_id_start::is_id_continue(char) 来检查 Unicode。

关键字

所有 关键字（如 if、while 和 for）都需要标记化为一个整体并进行解释。需要将这些关键字添加进 token 类别枚举，这样我们就不用在解析器中进行字符串比较。

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

提示

undefined 不是关键字，这里没有必要添加它。

标记化关键字将只是匹配上述标识符。

fn match_keyword(&self, ident: &str) -> Kind {
    // all keywords are 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, // end of file
    Plus,
    Identifier,
    Number,
    String,
}

#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Token {
    /// Token Type
    pub kind: Kind,

    /// Start offset in source
    pub start: usize,

    /// End offset in source
    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 } 的 token。若要将其转换为 Rust f64，我们可以通过调用 self.source[token.start..token.end].parse::<f64>() 来使用字符串 parse 方法，然后将该值保存在 token.value 中。对于二进制、八进制和整数，我们可在 jsparagus 中找到采用相应解析技术的示例。

Rust 优化

更小的 token

将 token 值放入 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"))).