Введение
Давайте поговорим о лексическом анализе. Сначала я собирался назвать этот пост «Реализуем токенайзер», но ветер переменился, времена изменились… и, чтобы не утонуть в потоке комментариев вида «фыр, а где мой BPE-токенизатор LLama, который вы мне обещали», ограничимся пока лексическим анализом.
Эта статья ориентирована на читателей, только начинающих пробовать свои силы в лексическом анализе Rust. Поэтому, пожалуйста, помните о целевой аудитории, прежде, чем сетовать: «хм, да я тут на коленке набросал поиск в таблице, и он работает в десять раз лучше, чем это недоразумение» и «с такими временами жизни я сам до завершения программы не доживу».
Но конструктивные комментарии и подсказки, как действительно можно было бы сделать лучше, всегда приветствуются.
Длинновато для вводного дисклеймера. Надеюсь, дочитав до этого места, вы уже хотя бы разок вздрогнули. Довольно слов, приступим.
Лексическая токенизация – это преобразование текста в (семантически или синтаксически) значимые лексические единицы (токены), которые распределяются по категориям при помощи программы-«лексера».
Проще говоря, на вход этой программе подаётся набор символов, а на выход она предлагает набор токенов. Обратите внимание: токены должны иметь смысловую нагрузку именно в вашем контексте, и освежевать кота токенизировать строку можно по-разному. Вот, например, как это можно сделать со строкой "hello world":
# Единственный токен <HELLO_WORLD> # Два токена, разделённых пробелом <HELLO> <WHITESPACE> <WORLD> # Один токен в обрамлении непробельных символов # Интерпретация непробельных символов <NON_WHITESPACE> <SPACE> <NON_WHITESPACE>
В сущности, так токенизатор превращается в функцию вида 
, которая принимает список символов из алфавита 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<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 идет Черная пятница в издательстве «Питер»
