Лексер

Токен

Лексер (tokenizer, scanner) превращает исходный текст в токены. Их затем ест парсер — про пробелы и комментарии в оригинале можно не думать.

Превратим один символ + в токен.

rust

#[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.

INFO

Итератор Chars прячет счётчик и границы.

chars.next() возвращает Option<char>. Учтите: char — не байт 0–255, это скалярное значение Unicode до 0x10FFFF.

Набросок лексера:

rust

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

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

    /// Get the length offset from the source text, in UTF-8 bytes
    fn offset(&self) -> usize {
        self.source.len() - self.chars.as_str().len()
    }
}

Вызовы .len() и .as_str().len() внутри fn offset кажутся 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` is only made from a str, which guarantees the iter is valid 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 sound because we transmute two types with the same layout
    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: 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:

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() сдвигает позицию.

Для строки abc:

повторный peek() — Some(a) снова и снова
chars.next() — 'a', 'b', '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 и освежите знания.

TIP

Помню, как в первый раз залез в спецификацию, спрятался в угол и чуть не плакал от жаргона. Если так же — начните с как читать спецификацию.

Comments

Комментарии семантики не несут — в рантайме их можно пропускать, но линтер и бандлер должны их учитывать.

Identifiers and Unicode

Обычно пишем в ASCII, но глава 11: исходный текст требует Unicode. Глава 12.6 говорит: идентификаторы следуют Unicode 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", у краба — нет.

INFO

Для этого я выложил крейт unicode-id-start. Можно вызывать unicode_id_start::is_id_start(char) и unicode_id_start::is_id_continue(char).

Keywords

Все ключевые слова (if, while, for и т.д.) нужно токенизировать целиком. Их добавляют в перечисление видов токенов, чтобы в парсере не сравнивать строки.

rust

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

TIP

undefined не ключевое слово — в enum не обязателен.

Ключевые слова — это сопоставление уже распознанного идентификатора.

rust

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

Token Value

Идентификаторы, числа и строки часто сравнивают на следующих фазах, например в линтере.

Сейчас значения лежат как срез исходника — превратим их в типы Rust для удобства.

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

Чтобы получить String в Rust: let s = self.source[token.start..token.end].to_string() и token.value = TokenValue::String(s).

Для числа 1.23 токен с Token { start: 0, end: 3 }. В f64 через parse: self.source[token.start..token.end].parse::<f64>(), результат в token.value. Для двоичных, восьмеричных и целых — примеры в jsparagus.

Оптимизации в Rust

Меньшие токены

Заманчиво засунуть значения прямо в Kind ради простоты:

rust

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

Размер enum в байтах — по максимуму среди вариантов. По сравнению с однобайтовым discrimination-only enum этот упакует много байт. В парсере Kind везде — с одним байтом работать очевидно быстрее.

Интернирование строк

String в компиляторах недёшев:

это куча
сравнение строк O(n)

String interning держит одну копию каждого уникального значения с идентификатором в кэше. Один раз выделили каждую уникальную строку на кучу, сравнение становится O(1).

На crates.io множество библиотек с разными плюсами и минусами.

Стартовая точка — string-cache с типом Atom и atom!("string") на этапе компиляции.

С ним TokenValue выглядит так:

rust

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

а сравнение строк превращается в matches!(value, TokenValue::String(atom!("string"))).

Лексер ​

Токен ​

Peek ​

JavaScript ​

Comments ​

Identifiers and Unicode ​

Keywords ​

Token Value ​

Оптимизации в Rust ​

Меньшие токены ​

Интернирование строк ​

Лексер

Токен

Peek

JavaScript

Comments

Identifiers and Unicode

Keywords

Token Value

Оптимизации в Rust

Меньшие токены

Интернирование строк