Lexer

Token

Lexer（トークナイザ、スキャナとも呼ばれる）は、ソーステキストをトークンに変換する責任を負っています。これらのトークンは後でパーサーによって消費されるため、元のテキストから空白やコメントを気にする必要がありません。

簡単な例から始めましょう。単一の + をトークンに変換してみます。

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 の範囲を持つ UTF-8 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 に対して match を実行します。最終的なトークンは常に 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 に適切な理由があるのは、同じレイアウトを持つ2つの型を転送しているため。
    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: `crate::ptr::metadata(self)` が定数安定になったら置き換えるべき。
    // 本稿執筆時点では、「定数安定関数は他の定数安定関数しか呼び出せない」というエラーが発生する。

    // SAFETY: `PtrRepr` のユニオンから値にアクセスすることは安全である。*const T と PtrComponents<T> は同じメモリレイアウトを持つ。
    // この保証は標準ライブラリのみが行える。
    unsafe { crate::ptr::PtrRepr { const_ptr: self }.components.metadata }
}

上記のすべてのコードは、コンパイル時に1つのデータアクセスにまとめられるため、.as_str().len() は実際には O(1) です。

先読み

++ や += のような多文字オペレータをトークン化するには、ヘルパー関数 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 で書いたライザーは、とても退屈です。まるで長〜い連続した if 文を書いているかのように、各 char をチェックしてそれぞれに対応するトークンを返す必要があります。

本当の楽しみは、実際に JavaScript をトークン化し始めることから始まります。

ECMAScript 言語仕様を開いて、再び JavaScript を学び直しましょう。

TIP

初めて仕様を開いたとき、その内容がどこにも意味が通じず、外語のような難解な専門用語だらけだったため、小部屋にこもり涙を流したのを今でも覚えています。もし内容が理解できない場合は、私の仕様の読み方ガイドを参考にしてください。

コメントは意味を持たないため、ランタイムを実装する場合スキップしても問題ありません。しかし、リナーやバンドラーを実装する場合は、コメントを考慮する必要があります。

識別子とユニコード

私たちは主に ASCII でコーディングしていますが、第11章 ECMAScript 言語：ソーステキストによると、ソーステキストはユニコードでなければならないとされています。さらに、第12.6章名前とキーワードでは、識別子は「ユニコード標準付録 #31」に定められた「デフォルト識別子構文」に基づいて解釈されるべきだとされています。詳しくは以下の通りです：

IdentifierStartChar ::
    UnicodeIDStart

IdentifierPartChar ::
    UnicodeIDContinue

UnicodeIDStart ::
    ユニコードプロパティ「ID_Start」を持つ任意のユニコードコードポイント

UnicodeIDContinue ::
    ユニコードプロパティ「ID_Continue」を持つ任意のユニコードコードポイント

これにより、var ಠ_ಠ は書けるものの、var 🦀 は書けません。 ಠ は「ID_Start」のユニコードプロパティを持ちますが、🦀 は持ちません。

INFO

この目的のために、unicode-id-start パッケージを公開しました。 unicode_id_start::is_id_start(char) および unicode_id_start::is_id_continue(char) を呼び出して、ユニコードをチェックできます。

キーワード

if、while、for などのすべてのキーワードは、全体としてトークン化され、解釈される必要があります。パーサーで文字列比較を行わないようにするために、これらをトークン種別列挙に追加する必要があります。

rust

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

TIP

undefined はキーワードではありません。ここに追加する必要はありません。

キーワードのトークン化は、前述の識別子のマッチングと同様です。

rust

fn match_keyword(&self, ident: &str) -> Kind {
    // すべてのキーワードは 1 < 長さ <= 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 に保存します。 2進数、8進数、整数のパース手法の例は、jsparagus にあります。

Rust の最適化

より小さなトークン

Kind 列挙体の中にトークン値を格納して、よりシンプルかつ安全なコードを目指したい気持ちは自然ですが、

rust

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

実際には、Rust の列挙体のバイトサイズはすべてのバリエーションの和（ユニオン）になります。この列挙体は、元の列挙体（1バイトのみ）と比べてかなり多くのバイトを占有します。この Kind 列挙体はパーサーで頻繁に使用されるため、1バイトの列挙体よりも多バイトの列挙体を使うことは明らかに遅くなります。

文字列のインターニング

コンパイラでは String を使うのは非効率的です。主な理由は以下の通りです：

String はヒープ領域に割り当てられるオブジェクト
文字列比較は時間計算量が O(n)

String Interning は、キャッシュ内に一意の識別子を持つ各異なる文字列値の1つのコピーを保持することで、これらの問題を解決します。異なる識別子または文字列ごとにヒープアロケーションは1回だけで済み、文字列比較は 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"))) となります。

Lexer ​

Token ​

先読み ​

JavaScript ​

コメント ​

識別子とユニコード ​

キーワード ​

トークン値 ​

Rust の最適化 ​

より小さなトークン ​

文字列のインターニング ​

Lexer

Token

先読み

JavaScript

コメント

識別子とユニコード

キーワード

トークン値

Rust の最適化

より小さなトークン

文字列のインターニング