Увлекательный лексический анализ языка Rust

Введение

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

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

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

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

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

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

# Единственный токен <HELLO_WORLD>  # Два токена, разделённых пробелом <HELLO> <WHITESPACE> <WORLD>  # Один токен в обрамлении непробельных символов  # Интерпретация непробельных символов <NON_WHITESPACE> <SPACE> <NON_WHITESPACE>

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

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

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

Теперь можно запустить новый проект 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<Vec<Token>, 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<P>(&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 идет Черная пятница в издательстве «Питер»