Lexer

Token

O léxico (também chamado tokenizer ou scanner) transforma o texto-fonte em tokens. O parser consumirá esses tokens depois, assim não precisamos nos preocupar com espaços em branco e comentários do texto original no estágio seguinte.

Comecemos simples e transformemos apenas o texto + em um 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,
}

Um único + produz:

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

Para percorrer a string, dá para manter um índice e fingir que estamos em C, ou dar uma olhada na documentação de str e trabalhar com o iterador Chars.

INFO

O iterador Chars esconde o índice e o boundary checking — sensação bem “segura”.

Ele nos dá Option<char> em chars.next(). Mas atenção: char não é um ASCII 0–255; é um ponto Unicode UTF-8 com faixa até 0x10FFFF.

Definimos um léxico bem inicial:

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

O tempo de vida 'a aqui diz que o iterador referencia algum lugar — neste caso, &'a str.

Para converter texto em tokens, basta repetir chars.next() e fazer match em cada char. O último token será sempre 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()
    }
}

As chamadas .len() e .as_str().len() dentro de offset parecem O(n); vamos entender por quê.

.as_str() devolve um slice que aponta para a string:

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

Um slice é uma visão de memória (ponteiro + comprimento). O método .len() lê só os metadados do slice:

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

Tudo isso costuma virar um único acesso a dados, então .as_str().len() é na prática O(1).

Peek

Para tokenizar operadores multi-caractere como ++ ou +=, precisamos de um helper peek:

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

Não queremos avançar o iterador original chars, então clonamos e consumimos esse clone.

INFO

clone é barato — veja o código-fonte: copia só os índices de rastreamento e de limite.

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

A diferença: peek sempre devolve o mesmo próximo char; chars.next() avança e devolve outros chars.

Por exemplo na string abc:

• peek() repetido → Some('a'), Some('a'), ...
• next() repetido → Some('a'), Some('b'), Some('c'), None.

Com peek, tokenizar ++ e += vira ifs aninhados.

Implementação real do 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,
    ),
},

A mesma ideia vale para os demais operadores — e daí ampliamos o léxico de JavaScript.

JavaScript

Um léxico em Rust é meio entediante: parece C, com cadeias longas de if checando cada char.

O jogo fica interessante quando o alvo é JavaScript.

Abra a especificação da linguagem ECMAScript e relembre JS.

TIP

Lembro da primeira vez que abri a spec e fui chorar num canto — parecia texto estranho cheio de jargão. Se esbarrar nisso, veja o guia para ler a especificação.

Comentários

Comentários não têm significado semântico; dá para ignorá-los num runtime, mas precisam ser considerados em linter ou bundler.

Identificadores e Unicode

Quase sempre digitamos ASCII, mas o capítulo 11 — Source Text diz que o texto-fonte é Unicode. E o 12.6 — Names and Keywords diz que identificadores seguem a sintaxe “Default Identifier” do UAX #31. Em detalhe:

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”

Ou seja, var ಠ_ಠ vale, mas var 🦀 não — ಠ tem ID_Start e 🦀 não.

INFO

Publiquei o crate unicode-id-start para isso. Use unicode_id_start::is_id_start(char) e unicode_id_start::is_id_continue(char) para validar Unicode.

Keywords

Todas as palavras-chave (if, while, for…) precisam virar tokens inteiros. Coloque-as no enum Kind para não comparar strings no parser.

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

TIP

undefined não é keyword — não precisa entrar aqui.

Na prática, depois do identificador basta converter para keyword:

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

Mais tarde compararemos identificadores, números e strings — por exemplo no linter.

Hoje esses valores ainda são fatias do texto; vamos pendurá-los como tipos 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),
}

Ao tokenizar identificador foo ou string "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") }

Converta para String Rust com let s = self.source[token.start..token.end].to_string() e grave em token.value = TokenValue::String(s).

Para número 1.23, há Token { start: 0, end: 3 }. Use parse: self.source[token.start..token.end].parse::<f64>() e guarde em token.value. Binário, octal e inteiros: exemplo no jsparagus.

Rust Optimizations

Smaller Tokens

É tentador colocar valores dentro de Kind e simplificar:

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

Mas o tamanho de um enum Rust é a união dos variantes. Esse enum pesa muito mais que um Kind de 1 byte. O parser usa Kind o tempo todo — manter 1 byte é obviamente mais rápido.

String Interning

String pura em compilador costuma ser cara:

• aloca na heap
• comparação é O(n)

String interning guarda uma cópia por valor distinto com id único. Uma alocação por literal/identificador distinto e comparação O(1).

Há várias libs em crates.io.

Um começo sólido é string-cache com tipo Atom e atom!("texto") em compile time.

Com isso, TokenValue fica:

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

e uma comparação vira matches!(value, TokenValue::String(atom!("string"))).