18 сен в 00:43

Лексер простыми словами на Rust

Простой

Ожидает приглашения

Всем привет, сегодня поговорим о том, что такое лексер и как его написать. Если
вам не терпится посмотреть на код, промотайте до самого низа статьи.

Что такое лексер?

По сути, лексер просто разбивает исходный код на отдельные токены. К примеру:

let a = 2

Превратится в:

[
    Let,
    Identifier(
        "a",
    ),
    EqualSign,
    Number(
        123,
    ),
]

И все! Правда, можно еще можно добавить анализ кода на синтаксические ошибки, и
отслеживания позиции токенов в коде. Ну а на сегодня мы напишем простейший
лексер для Rust. Если вам нужен "full-batteries" лексер для Rust, то вас может
заинтересовать syn (он содержит не только
лексер, но и парсер). Если вы хотите поизучать создание ЯП в целом, то
почитайте Crafting Interpeters.

А если вам нужен кастомный лексер именно для вашего ЯП, но вам лень его писать
ручками, вы можете использовать Flex.

Пишем код!

Я старался писать этот код по всем принципам "clean-code". Надеюсь что вам будет
понятно, что я пытался передать этим кодом. Также, этот код сильно упрощен,
но внесение новых типов токенов т.е. масштабирование не будет проблемой.

Итак, для начала напишем главную функцию lex() которая принимает на вход
исходный код в виде строки, а уже на выходе выдает последовательность токенов.

Для того чтобы не писать огромный тип в каждой функции, мы напишем алиас:

use std::str::Chars;
use std::iter::Peekable;

type Source<'s> = Peekable<Chars<'s>>;

Для представления входных данных мы будем использовать структуры из стандартной
библиотеки Rust: Peekable и Chars. Peekable дает возможность смотреть на
один токен вперед, а Chars - это просто последовательность char.

fn lex(mut source: Source) -> Vec<Token> {    
    let mut tokens = Vec::new();    
    while let Some(token) = token(&mut source) {
        tokens.push(token);
    }    
    tokens
}

Пока есть токены, мы их "лексим".

Определим объект Token, определяюший все типы токенов. Вообще в Rust очень
удобно реализованы enum - их можно использовать не только для представления
токенов, но и AST, CFG, и множества других структур используемых в компиляторах,
так как в самих вариантах enum можно хранить любые данные.

enum Token {
    Number(i64),
    Identifier(String),
    Let,
    EqualSign, // '='
}

Дальше напишем функцию token(), которая будет непосредственно "лексить"
токены. Единственная цель этой функции - определение того, какой тип токена мы
будем лексить.

fn token(source: &mut Source) -> Option<Token> {
    let c = source.peek()?;
    if c.is_ascii_digit() { // [0-9]        
        Some(number(source))    
    } else if c.is_ascii_alphabetic() { // [a-zA-Z]        
        Some(identifier_or_keyword(source))
    } else {        
        symbol(source)
    }
}

Теперь напишем функции для каждого типа токена:

Числа - 123:

fn number(source: &mut Source) -> Token {    
    let buffer = take_till(source, |c| c.is_ascii_digit()); // [0-9]
    let token = buffer.parse().parse(); // Никогда не произойдет ошибки т.к. `buffer` всегда будет попадать под паттерн числа    
    Token::Number(token)
}

Переменные и ключевые слова - let, abc:

fn identifier_or_keyword(source: &mut Source) -> Token {
    let buffer = take_till(source, |c| c.is_ascii_alphanumeric()); // [a-zA-Z0-9]
    match buffer.as_str() {
        "let" => Token::Let,
        _ => Token::Identifier(buffer),
    }
}

Другие символы - пробелы, табы, операторы:

fn symbol(source: &mut Source) -> Option<Token> {
    let c = source.next().unwrap(); // Никогда не будет `None` т.к. в `token()` мы смотрим на один токен вперед с помощью `.peek()`    
    match c {
        '=' => Some(Token::EqualSign),
        ' ' | '\n' | '\t' => skip(source),
        _ => panic!("Неопознаный токен: '{c}'"), // Можно сделать нормальную обработку ошибок, но для наших целей этого вполне хватит.    
    }
}

fn skip(source: &mut Source) -> Option<Token> {
    skip_till(source, |c| matches!(c, ' ' | '\n' | '\t'));
    token(source) // Сразу же обрабатываем следуюший токен потому что `token()` который вызвал эту функцию, ожидает новый токен на выходе
}

Вы наверное увидели функции take_till и skip_till. Я не хочу их писать, но
суть в том, что они совершают какое-то действие до определенного условия.

Вот и все! Мы написали очень простой лексер всего лишь в 75 строчках кода.
Кстати, вот полная версия кода:

use std::str::Chars;
use std::iter::Peekable;

type Source<'s> = Peekable<Chars<'s>>;

#[derive(Debug)]
enum Token {
    Number(i64),
    Identifier(String),
    Let,
    EqualSign,
}

fn main() {
    let source = r#"let a = 123"#;
    let tokens = lex(source.chars().peekable());
    println!("{tokens:#?}");
}

fn lex(mut source: Source) -> Vec<Token> {
    let mut tokens = Vec::new();
    while let Some(token) = token(&mut source) {
        tokens.push(token);
    }
    tokens
}

fn token(source: &mut Source) -> Option<Token> {
    let c = source.peek()?;
    if c.is_ascii_digit() {
        Some(number(source))
    } else if c.is_ascii_alphabetic() {
        Some(identifier_or_keyword(source))
    } else {
        symbol(source)    
    }
}

fn number(source: &mut Source) -> Token {
    let buffer = take_till(source, |c| c.is_ascii_digit());
    let token = buffer.parse().unwrap();
    Token::Number(token)
}

fn identifier_or_keyword(source: &mut Source) -> Token {
    let buffer = take_till(source, |c| c.is_ascii_alphanumeric());
    match buffer.as_str() {
        "let" => Token::Let,
        _ => Token::Identifier(buffer),
    }
}

fn take_till(source: &mut Source, till: impl Fn(char) -> bool) -> String {
    let mut buffer = String::new();
    while let Some(c) = source.peek() {
        if !till(*c) {
            break;
        }
        buffer.push(*c);
        source.next();
    }
    buffer
}

fn symbol(source: &mut Source) -> Option<Token> {
    let c = source.next().unwrap();
    match c {
        '=' => Some(Token::EqualSign),
        ' ' | '\n' | '\t' => skip(source),
        _ => panic!("Неопознаный токен: '{c}'"),
    }
}

fn skip(source: &mut Source) -> Option<Token> {
    skip_till(source, |c| matches!(c, ' ' | '\n' | '\t'));
    token(source)
}

fn skip_till(source: &mut Source, till: impl Fn(char) -> bool) {
    while let Some(c) = source.peek() {
        if !till(*c) {
            break;
        }
        source.next();
    }
}

Компилируем с помощью rustc:

> rustc source.rs

И запускаем скомпилированный бинарник:

> ./source
[
    Let,
    Identifier(
        "a",
    ),
    EqualSign,
    Number(
        123,
    ),
]

Ура! Лексер работает.

Некоторые ресурсы которые могут быть полезны для изучения:

Возможно скоро напишу статью о парсерах.

Теги:

Хабы: