詞法分析器

Token (語彙單元)

詞法分析器，也稱為語彙分析器或掃描器，負責將原始文字轉換為語彙單元 (tokens)。這些語彙單元稍後會被語法解析器使用，這樣我們就不必擔心原始文字中的空格和註解。

讓我們先從簡單的開始，將單個 + 文字轉換為語彙單元。

#[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 值，它是一個 utf8 Unicode 碼位值，範圍從 0 到 0x10FFFF。

讓我們定義一個起始的詞法分析器抽象

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。

要將原始文字轉換為語彙單元，只需不斷呼叫 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 }
    }

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

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。

提示

我仍然記得我第一次打開規範時，因為它感覺像是到處都是術語的外語文字，所以跑到一個小角落哭泣。因此，如果有些事情不合邏輯，請前往我的閱讀規範指南。

註解

註解沒有語義含義，如果我們正在編寫執行時間，則可以跳過它們，但如果我們正在編寫程式碼檢查器或打包器，則需要將它們納入考量。

識別碼和 Unicode

我們大多使用 ASCII 編碼，但是 第 11 章 ECMAScript 語言：原始文字 指出原始文字應採用 Unicode 格式。而 第 12.6 章名稱和關鍵字 指出識別碼是根據 Unicode Standard Annex #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，都需要被標記化並整體解釋。它們需要被新增到語彙單元種類列舉中，這樣我們就不必在語法解析器中進行字串比較。

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

語彙單元值

我們經常需要在編譯器的後續階段中比較識別碼、數字和字串，例如在程式碼檢查器中測試識別碼。

這些值目前是純文字格式，讓我們將它們轉換為 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 } 的語彙單元。要將其轉換為 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")))。