[Перевод] Увлекательный лексический анализ языка Rust30.11.2023 22:45

04caf2e4d48664c6c23941b5ce4e23b0.png

Введение

Давайте поговорим о лексическом анализе. Сначала я собирался назвать этот пост «Реализуем токенайзер», но ветер переменился, времена изменились… и, чтобы не утонуть в потоке комментариев вида «фыр, а где мой BPE-токенизатор LLama, который вы мне обещали», ограничимся пока лексическим анализом.

Эта статья ориентирована на читателей, только начинающих пробовать свои силы в лексическом анализе Rust. Поэтому, пожалуйста, помните о целевой аудитории, прежде, чем сетовать: «хм, да я тут на коленке набросал поиск в таблице, и он работает в десять раз лучше, чем это недоразумение» и «с такими временами жизни я сам до завершения программы не доживу».

Но конструктивные комментарии и подсказки, как действительно можно было бы сделать лучше, всегда приветствуются.

Длинновато для вводного дисклеймера. Надеюсь, дочитав до этого места, вы уже хотя бы разок вздрогнули. Довольно слов, приступим.

Лексическая токенизация — это преобразование текста в (семантически или синтаксически) значимые лексические единицы (токены), которые распределяются по категориям при помощи программы-«лексера».  

Проще говоря, на вход этой программе подаётся набор символов, а на выход она предлагает набор токенов. Обратите внимание: токены должны иметь смысловую нагрузку именно в вашем контексте, и освежевать кота токенизировать строку можно по-разному. Вот, например, как это можно сделать со строкой «hello world»: 

# Единственный токен


# Два токена, разделённых пробелом
  

# Один токен в обрамлении непробельных символов 
# Интерпретация непробельных символов

В сущности, так токенизатор превращается в функцию вида t:(S^*, T)→T^*, которая принимает список символов из алфавита S и алфавит токенов, после чего производит список токенов из алфавита T. Как минимум, в моём представлении всё именно так.

Определение токенов

В рамках этой статьи реализуем токенизатор для анализа простого выражения Cron. Постараемся работать с такими выражениями, каждое из которых состоит ровно из 5 полей, и в качестве токенов в этом выражении допускаются только 0-9,  *,  /,  ,,  -, а на уровне каждого из полей действуют следующие правила:

Поля

Допустимые значения

Допустимые специальные символы

Минуты

0 — 59

* - ,

Часы

0 — 23

* - ,

День месяца

1 — 31

* - ,

Месяц

1 — 12

* - ,

День недели

0 — 6

* - ,

Теперь можно запустить новый проект Rust. Для этого выполним cargo new cronlexer и перейдём к делу.

Я предпочитаю первым делом определить токены в коде. Поскольку нет двух одинаковых токенов, их максимально удобно выразить в Rust в виде перечисления. Вот пример, демонстрирующий, как можно структурировать токены: 

#[derive(Debug, PartialEq, Clone)]
pub enum Token {
    Whitespace,
    Number(u8),
    Dash,
    Slash,
    Star,
    Comma,
}

Названия вариантов, входящих в перечисление, самоочевидны, и напрямую соответствуют тем токенам, которые нас интересуют. Правда, как вы, возможно, заметили, мы решили реализовать токен-цифру как Number(u8). Так мы принуждаем токенизатор объединить все цифры в число, и только после этого выдавать токен. Но мы могли бы также сделать каждую цифру отдельным токеном, вот так: 

#[derive(Debug, PartialEq, Clone)]
pub enum Token {
    Whitespace,
    Zero,
    One,
    Two,
    Three,
    Four,
    Five,
    Six,
    Seven,
    Eight,
    Nine,
    Dash,
    Slash,
    Star,
    Comma,
}

Можно даже поступить прямо противоположным образом и предусмотреть отдельные токены для дней, недель и года, вот так: 

#[derive(Debug, PartialEq, Clone)]
pub enum Token {
    Whitespace,
    Minutes(u8),
    Hours(u8),
    DayOfMonth(u8),
    Month(u8),
    DayOfWeek(u8),
    Dash,
    Slash,
    Star,
    Comma,
}

В зависимости от того, как будет структурирована эта информация, её синтаксический разбор может пойти проще или сложнее. Пока отвлечёмся от синтаксического разбора и просто примем набор токенов, которые имеют смысл в контексте нашего примера и сочтём, что они (сколько бы их ни было) синтаксически корректны. В результате получим: 

#[derive(Debug, PartialEq, Clone)]
pub enum Token {
    Whitespace,
    Number(u8),
    Dash,
    Slash,
    Star,
    Comma,
}

Проектируем интерфейс токенизатора

Когда я проектирую библиотечный интерфейс, я всегда задумываюсь о конечном пользователе. Как он будет обращаться с моей библиотекой? Каковы будут входные и выходные значения предоставляемых в библиотеке публичных функций, структур и перечислений? Затем, нащупывая, таким образом, как лучше работать с библиотекой, я могу сделать её эргономичнее, и пользователю тоже станет удобнее её применять.

Для начала попробую использовать мою библиотеку следующим образом: 

let source = "*/5 1,2,3 * * *";
let tokenizer = Tokenizer::new(source.as_bytes());
for token in tokenizer {
    println!("token: {:?}", token);
}

Поскольку мы хотим перебирать токены, можно опереться на следующее соглашение: мы вправе реализовать типаж IntoIterator для нашего Tokenizer, и именно в нём возвращать конкретный итератор. В Rust принято, что всякий раз, когда вы хотите вернуть некоторую сущность, реализующую набор типажей, вы обёртываете их в структуру и заставляете эту структуру их реализовать. Такое встречается повсюду, например, столь разные функции, как map,  peek,  iter,  split_whitespaces, все возвращают разнообразные вспомогательные структуры, реализующие необходимые типажи.

Но затем быстро приходит понимание, что при токенизации может быть возвращена ошибка. Например, если попытаться расставить токены в »schedule every day» в нашем Cron-выражении, то грамматика с этим выражением просто не справится.

let source = "schedule every day";
let tokenizer = Tokenizer::new(source.as_bytes());
// Мы ведь не можем перебрать токенизацию, которая прошла неудачно, или можем?
for token in tokenizer {
    println!("token: {:?}", token);
}

Вместо этого воспользуемся методом tokenize, который будет возвращать результат токенизации. В реальной ситуации здесь уже могут возникнуть другие вещи, которые также потребуется делать токенизатору: подсмотреть следующее значение, затем выполнить поиск с возвращением, причём, сделать это быстро (с оптимизацией). Пока давайте не усложнять: мы хотим просто токенизировать данные и перебрать токены. Наша библиотека будет использоваться примерно так: 

let source = "*/5 1,2,3 * * *";
let tokenizer = Tokenizer::new(source.as_bytes());
// обратите внимание на '#' или на сопоставление с ошибкой
let tokens = tokenizer.tokenize()?;
for token in tokenizer {
    println!("token: {:?}", token);
}

Реализация

Сначала давайте заполним наши базовые структуры. Нам понадобится главная структура Tokenizer, а также TokenizerError

// захватить здесь какое-то сообщение, которое затем пригодится пользователю библиотеки 
#[derive(Debug)]
pub struct TokenizerError {
    pub message: String,
}

// вектор токенов
pub type TokenizerResult = Result, TokenizerError>;

pub struct Tokenizer<'a> {
    source: &'a [u8],
    pos: usize,
}

impl<'a> Tokenizer<'a> {
    pub fn new(source: &'a [u8]) -> Self {
        Self { source, pos: 0 }
    }

    pub fn tokenize(&mut self) -> TokenizerResult {
        todo!()
    }
}

Теперь давайте реализуем токенизатор. Он будет просто просматривать токены в направлении слева направо, затем жадно потреблять их и ставить в результирующий вектор токенов.

impl<'a> Tokenizer<'a> {
    // создать новый токенизатор
    pub fn new(source: &'a [u8]) -> Self {
        Self { source, pos: 0 }
    }

    pub fn tokenize(&mut self) -> TokenizerResult {
        let mut tokens = Vec::new();

        while self.pos < self.source.len() {
            // свериться с каждым конкретным токеном и получить как сам токен,
            // так и количество потреблённых байт
            let (token, consumed) = match self.source[self.pos] {
                // жадно потреблять пробелы
                b' ' | b'\t' => {
                    let count = self.peek_while(is_whitespace);
                    (Token::Whitespace, count)
                }

                b'-' => (Token::Dash, 1),
                b',' => (Token::Comma, 1),
                b'/' => (Token::Slash, 1),
                b'*' => (Token::Star, 1),
                b'0' | b'1' | b'2' | b'3' | b'4' | b'5' | b'6' | b'7' | b'8' | b'9' => {
                    // жадно потреблять цифры
                    let count = self.peek_while(is_digit);

                    (
                        Token::Number(to_u8(&self.source[self.pos..(self.pos + count)])),
                        count,
                    )
                }
                ch => {
                    // мы нашли символ, которого нет в нашем алфавите, поэтому
                    // вернём ошибку
                    return Err(TokenizerError {
                        message: format!("Could not parse token: {ch}",),
                    })
                }
            };
            // развить внутреннее состояние
            self.pos += consumed;
            // прикрепить токен
            tokens.push(token);
        }

        Ok(tokens)
    }

    // посмотреть, пока предикат равен true, 
    // не изменяя состояние,
    // после чего возвратить число подсмотренных элементов
    fn peek_while
(&self, pred: P) -> usize
    where
        P: Fn(u8) -> bool,
    {
        let mut consumed = 0;

        while (self.pos + consumed) < self.source.len() && pred(self.source[self.pos + consumed]) {
            consumed += 1;
        }

        consumed
    }
}

// проверить, является ли байт цифрой
fn is_digit(v: u8) -> bool {
    v >= b'0' && v <= b'9'
}

// проверить, является ли байт пробелом
fn is_whitespace(v: u8) -> bool {
    v == b' ' || v == b'\t'
}

// дёшевый и сердитый способ извлечь цифру из байтовой строки 
// напр. b'12' -> 12
fn to_u8(vs: &[u8]) -> u8 {
    let mut result: u8 = 0;
    const RADIX: u8 = 10;
    let len = vs.len();
    for i in 0..len {
        result = result + (RADIX.pow((len - i - 1) as u32) * (vs[i] - b'0'));
    }
    result
}

Некоторые интересные замечания и наблюдения:

  • tokenize принимает mut self, так как изменяет внутреннее состояние и не является идемпотентным (если вызвать tokenize дважды, то это приведёт к ошибке). Так очень удобно просигнализировать клиенту, что вызывать tokenize по несколько раз не разрешается и принудительно обеспечить соблюдение этого условия во время компиляции.

  • Наш Tokenizer принимает source по ссылке. Когда требуется прочитать эту информацию в простых случаях, например, таких, как мы разбираем сейчас, нужно продумать, как долго должна оставаться действительной ссылка на Tokenizer? В общем, ссылка source должна пережить Tokenizer (или прожить столько же, сколько и он). В противном случае у нас не будет допустимой точки, из которой мы могли бы считать данные.

  • Во внутреннем состоянии мы ведём актуальный индекс pos, жадно продвигая его по мере синтаксического разбора токенов. Синтаксический разбор токенов — это просто одна гигантская операция match (которую можно было бы вынести в отдельную функцию). В рамках этой операции мы возвращаем сам токен, а также число потреблённых байт.

  • Наша грамматика Cron поддаётся недвусмысленной токенизации. Поэтому весь процесс получается довольно тривиальным упражнением: нужно просто аккуратно наращивать индекс и сопоставлять токены, пока мы не исчерпаем запас байт.

Тестирование

Напишем несколько тестов: 

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn basic_tokenization() {
        let source = "*/12";
        let tokenizer = Tokenizer::new(source.as_bytes());
        let tokens = tokenizer.tokenize();
        assert!(tokens.is_ok());
        assert_eq!(
            tokens.unwrap(),
            vec![Token::Star, Token::Slash, Token::Number(12)]
        );
    }

    #[test]
    fn failed_tokenization() {
        let source = "why cant't I just say 'every hour'";
        let tokenizer = Tokenizer::new(source.as_bytes());
        let tokens = tokenizer.tokenize();
        assert!(tokens.is_err());
    }
}

100% покрытие тестами. Именно так я и пишу в проде.

p/s идет Черная пятница в издательстве «Питер»

© Habrahabr.ru