Добро пожаловать! В прошлом посте я рассказал о своей цели создать язык программирования и описал, какие языки программирования работают. В этом посте я начну с создания лексера, который берет исходный код и превращает его в токены, которые будут читаться другими частями языка.
Мы начнем с малого: сейчас мы просто хотим создать простой калькулятор, способный поддерживать целочисленное сложение, вычитание, умножение и деление. Мы также разрешим использование скобок, но это все. Пока я расскажу о Lexer, я также расскажу о некоторых особенностях Rust, так как этот проект также предназначен для изучения Rust. Весь исходный код этого проекта можно найти в этом репозитории Github.
Начиная
После создания проекта rust мы создаем новый файл lexer.rs. Начнем с создания структуры для токенов, а также некоторых других наработок:
pub struct Token
{
pub token_type: TokenType,
// For error handling.
pub line: usize,
pub col: usize,
start: usize,
length: usize
}
#[derive(PartialEq, Eq)]
pub enum TokenType
{
// Single character tokens.
Plus, Minus, Star, Slash,
LeftParen, RightParen,
// Literals
IntLiteral(u32),
EOF, // End of file.
Error, // To be used when an invalid token is found.
}
impl Token
{
pub fn to_string<'a>(&'a self, source: &'a str) -> &str
{
if self.token_type == TokenType::EOF
{
"EOF"
}
else
{
&source[self.start..(self.start+self.length)]
}
}
}
Структура Token содержит TokenType, а также целые числа без знака для строки и столбца, в которых находится токен. Он также содержит начало и длину, которые используются в методе to_string. Тип usize хранит целое число без знака, размер которого зависит от аппаратной архитектуры, что делает его подходящим для индексации.
Некоторые уникальные функции Rust уже используются. Перечисление TokenType похоже на перечисления в других языках, но есть несколько отличий. Атрибут #[derive()] функционирует аналогично наследованию в других языках, поэтому я не буду подробно его обсуждать, но основное отличие состоит в том, что с одним из значений, IntLiteral, связано другое значение. В Rust есть алгебраическая система типов, которая перечисляет варианты, чтобы с ними были связаны другие значения. Хорошим примером этого является тип Result<T, E>, который имеет два варианта: вариант Ok, который содержит значение типа T, и вариант Err, который содержит значение типа E. Это позволяет Rust избегать генерации исключений и нулевых указателей, а они часто проявляются при использовании языка.
Ссылки и время жизни
В методе to_string тоже происходит что-то странное: <'a>. В Rust & указывает на ссылку на какое-то другое значение. Если это значение удалено, эта ссылка становится недействительной. В Rust нет сборщика мусора; скорее, он удаляет значения, как только они выходят за рамки. Но что произойдет, если значение выйдет из области видимости до того, как это сделает ссылка? Возьмите этот код в качестве примера
fn main() {
let reference: &i32;
{
let value: i32 = 42;
reference = &value;
}
println!("{}", reference);
}
Попытка запустить этот код приводит к следующей ошибке:
error[E0597]: `value` does not live long enough
--> src/main.rs:6:19
|
4 | let value: i32 = 42;
| ----- binding `value` declared here
5 |
6 | reference = &value;
| ^^^^^^ borrowed value does not live long enough
7 | }
| - `value` dropped here while still borrowed
8 | println!("{}", reference);
| --------- borrow later used here
For more information about this error, try `rustc --explain E0597`
Сообщения об ошибках Rust чрезвычайно полезны для исправления ошибок. В этом случае мы пытаемся использовать ссылку после того, как переменная value удалена (т.е. удалена из памяти). Компилятор не позволит нам это сделать, так как ссылка уже недействительна.
Давайте еще раз взглянем на сигнатуру метода:
pub fn to_string<'a>(&'a self, source: &'a str) -> &str
<'a> здесь относится к времени жизни входных аргументов. Это означает, что выходная строка будет действительна только в течение времени жизни обоих аргументов. Если токен или исходная строка удалены из памяти, мы больше не сможем получить доступ к выходной строке. Это не проблема для нас, так как ни один из них не будет удален из памяти, пока компилятор не завершит работу, но мы должны сообщить компилятору rust, когда объявить вывод недействительным.
Вывод Lexer и обработка ошибок
Теперь, когда у нас есть структура токена, нам нужно определить вывод лексера. Его основная функция — выводить список токенов, но он также должен уметь обрабатывать ошибки. Вот как выглядит выходное перечисление:
pub enum LexerOutput
{
LexInfo
{
file_text: String,
tokens: Vec<Token>,
errors: Vec<String>,
can_compile: bool,
},
Failure(String)
}
Перечисление LexerOutput имеет два случая: обычно создается структура LexInfo. Он содержит текст файла, который используется для преобразования токенов в строки. Вместо того, чтобы хранить сегменты строки с каждым токеном, мы сохраняем здесь весь текст и разрешаем токенам ссылаться на него. Вот почему метод to_string требует дополнительного строкового аргумента. Здесь также хранится список токенов, а также список строк, представляющих ошибки. В какой-то момент я хотел бы сделать лучший обработчик ошибок, но пока этого достаточно. Наконец, у нас есть логическое значение, указывающее, должен ли компилятор пытаться вывести байт-код для этого файла.
Также есть кейс Failure, созданный для случаев, когда лексер даже не может открыть файл. В этом случае нет текста файла или списка токенов, поэтому нам просто нужна строка, содержащая ошибку.
Наша функция lex начинается следующим образом:
pub fn lex() -> LexerOutput
{
let input: thread::Result<Vec<String>> = catch_unwind(||{args().collect()});
if input.is_err()
{
return LexerOutput::Failure(String::from("error: could not read command line arguments"));
}
let input: Vec<String> = input.ok().expect("should be valid as error handled earlier");
if input.len() > 2
{
return LexerOutput::Failure(String::from("error: too many command line arguments"));
}
if input.len() == 1
{
return LexerOutput::Failure("error: not enough command line arguments".to_string());
}
let file_path: &String = &input[1];
let file_text: Result<String, Error> = read_to_string(file_path);
if file_text.is_err()
{
return LexerOutput::Failure(String::from(format!("error: could not open file \"{file_path}\"")));
}
Первое, что мы делаем, это пытаемся прочитать аргументы из командной строки, что и делает args().collect(). Если аргументы не соответствуют Unicode, это приведет к сбою. Этого никогда не должно происходить, но на всякий случай использование catch_unwind позволяет остановить эту ошибку и вернуть сообщение об ошибке. Методы .ok().expect() предоставляют информацию об отсутствии ошибок из командной строки, ожидая, что ошибки нет, что является безопасным ожиданием теперь, когда мы обработали ошибку.
Затем мы проверяем наличие ровно одного аргумента командной строки. Имя программы часто рассматривается как первый аргумент, поэтому мы должны проверить, что длина равна 2. Если нет, мы снова возвращаем ошибку. Наконец, мы должны убедиться, что ввод командной строки является путем к файлу, из которого можно прочитать. Если нет, мы снова возвращаем ошибку.
Жетоны с одним персонажем
Далее мы начнем лексировать токены, начиная с самых простых: с одним символом. Начнем с создания переменных как для вывода, так и для отдельных токенов:
let file_text: String = file_text.ok().expect("should be valid as error handled earlier");
let mut tokens: Vec<Token> = Vec::new();
let mut errors: Vec<String> = Vec::new();
let mut can_compile: bool = true;
let mut index: usize = 0;
let mut line: usize = 1;
let mut col: usize = 1;
Затем мы начинаем перебирать символы файла. Если символа нет, добавляем токен EOF и выходим из цикла.
loop
{
let c: Option<char> = file_text.chars().nth(index);
if let None = c
{
tokens.push(Token{token_type: TokenType::EOF, line, col, start: index, length: 0});
return LexerOutput::LexInfo{file_text, tokens, errors, can_compile};
}
let c: char = c.expect("should be valid as error handled earlier");
Тип Option похож на тип Result, но вместо того, чтобы содержать ошибки, он просто возвращает None в случае отсутствия значения. Мы используем это, чтобы знать, когда нужно нажать токен EOF и вернуть LexInfo. В случае, если остались символы, мы преобразуем c из Option в char, снова используя .expect().
После получения персонажа мы можем его обработать. Ниже приведены операторы if-else, которые добавляют токен в список в зависимости от персонажа. Переменные index и col также увеличиваются. Чтобы не повторяться, я покажу оператор if только для токена Plus, но то же самое было сделано для Minus, Star, Slash, LeftParen и RightParen.
if c == '+'
{
tokens.push(Token{token_type : TokenType::Plus, line, col, start : index, length : 1});
index += 1;
col += 1;
}
// More code not shown
Нам также нужно обработать пустое пространство:
else if c == ' ' || c == '\t' || c == '\n'|| c == '\r'
{
if c == '\r' || c == '\n'
{
line += 1;
col = 1;
if c == '\r' && file_text.chars().nth(index + 1) == Some('\n')
{
index += 1;
}
}
else if c == '\t'
{
col += 4 - ((col - 1) % 4);
}
else
{
col += 1;
}
index += 1;
}
Пустое пространство бывает трех типов: обычные пробелы, вкладки и новые строки. Код начинается с новых строк. В зависимости от ОС новая строка представлена либо символом новой строки \n, либо символом возврата каретки \r, либо обоими в последовательности \r\n. Первый оператор if обрабатывает все случаи: если какой-либо символ найден, счетчик строк увеличивается, столбец сбрасывается на единицу, а в случае, если символ является возвратом каретки, а следующим является новая строка, мы увеличиваем индекс дополнительное время, чтобы не считать новую строку дважды.
Следующий случай — вкладка. Вкладки раздражают, потому что они не имеют стандартизированного размера, но в большинстве IDE по умолчанию их 4, так что мы пойдем с этим. Вкладки также не всегда перемещают курсор на 4 пробела. Вместо этого они переходят к следующему 4-му столбцу. Поскольку столбцы начинаются с 1, столбцы, выровненные по табуляции, имеют номера 1, 5, 9 и т. д. Итак, мы добавляем 4 к количеству столбцов, а затем вычитаем разницу, которая находится с помощью оператора модуля.
Наконец, в случае обычного пробела мы добавляем только 1 к количеству столбцов. Во всех случаях мы увеличиваем индекс, чтобы перейти к следующему символу.
На данный момент мы закончили с простыми токенами. Далее нам нужно сохранить токены.
Целые литералы
Код для преобразования числа в токены выглядит следующим образом:
else if c >= '0' && c <= '9'
{
let mut length: usize = 1;
while is_digit_option(&file_text.chars().nth(index + length))
{
length += 1;
}
let int_literal: Result<u32, ParseIntError> = file_text[index..(index+length)].parse::<u32>();
let token_type: TokenType = get_int_literal_token_type(int_literal);
let token: Token = Token{token_type, line, col, start: index, length};
if let TokenType::Error = token.token_type
{
can_compile = false;
errors.push(String::from(format!("error ({file_path}:{line}:{col}): int literal \"{}\" must be at most {}",
token.to_string(&file_text), 0x8000_0000u32)));
}
tokens.push(token);
index += length;
col += length;
}
Мы начинаем с создания новой переменной length, присваивая ей значение 1, а затем увеличивая переменную до тех пор, пока не будет найдена нецифра. Функция is_digit_option выглядит следующим образом:
fn is_digit_option(c_option: &Option<char>) -> bool
{
match c_option
{
None => false,
Some(c) => c >= &'0' && c <= &'9'
}
}
Если символа нет (то есть мы дошли до конца файла), возвращаем false. В противном случае возвращаем true, если символ цифра, и false в противном случае.
После того, как мы находим нецифру, мы берем фрагмент текста файла, состоящий из найденных нами цифр, и пытаемся преобразовать его в 32-битное целое число без знака. Если это не удается, это означает, что число слишком велико. Однако, даже если это удастся, число может быть слишком большим, чтобы поместиться в целое число со знаком. Мы используем следующую функцию, чтобы проверить, так ли это:
fn get_int_literal_token_type(int_literal: Result<u32, ParseIntError>) -> TokenType
{
if let Err(_) = int_literal
{
return TokenType::Error;
}
let value: u32 = int_literal.expect("should be valid as error handled earlier.");
if value > 0x8000_0000u32
{
return TokenType::Error;
}
else
{
return TokenType::IntLiteral(value);
}
}
Сначала мы разбираемся с возможной ошибкой синтаксического анализа: если литерал вызвал ошибку, мы возвращаем тип токена Error. В противном случае проверяем значение: если оно больше 0x8000_0000, возвращаем тип Error. В противном случае мы возвращаем тип IntLiteral со значением литерала. Значение 0x8000_0000 эквивалентно 2³¹, а 32-разрядные целые числа со знаком могут содержать значения от -2³¹ до 2³¹-1. Поскольку у нас нет отрицательных литералов, нам нужен токен, который может содержать значение 2³¹. Мы займемся предотвращением сохранения положительного 2³¹ позже.
Получив тип токена, мы создаем сам токен. В случае ошибки мы устанавливаем can_compile в false и добавляем сообщение в список ошибок. Мы добавляем токен в список и увеличиваем индекс и столбец на нужную величину. Обратите внимание, что когда мы добавляем токен в список, мы теряем право собственности на него. Из-за этого мы делаем все необходимое, прежде чем добавить его в список. Этого можно было бы избежать, внедрив трейт Copy, но я сделаю это только в том случае, если это станет проблемой.
Недействительные токены
Наконец, мы должны иметь дело со случаем недопустимых символов. Позже это будет заменено переменными и другими пользовательскими конструкциями, но сейчас их у нас нет, поэтому лексер может сразу указать на наличие ошибки.
else
{
let mut length: usize = 1;
while !is_token_separator(&file_text.chars().nth(index + length))
{
length += 1;
}
let token: Token = Token{token_type: TokenType::Error, line, col, start: index, length};
errors.push(String::from(format!("error ({file_path}:{line}:{col}): unrecognized token \"{}\"",
token.to_string(&file_text))));
tokens.push(token);
can_compile = false;
index += length;
col += length;
}
Мы начинаем так же, как и с целыми числами, увеличивая значение длины до тех пор, пока не будет найден разделитель токенов. Разделитель токенов — это символ, который всегда является собственным токеном, независимо от соседних символов. На данный момент это включает в себя все пробелы и круглые скобки, а также конец файла.
fn is_token_separator(c_option: &Option<char>) -> bool
{
match c_option
{
None => true,
Some(c) => c == &' ' || c == &'\t' || c == &'\n' || c == &'\r'
|| c == &'(' || c == &')'
}
}
Наконец, мы создаем токен, добавляем ошибку и токен в соответствующие списки и увеличиваем строку и столбец. После этого цикл будет продолжаться до тех пор, пока не останется символов для чтения.
Тестирование и завершение
Мы можем протестировать наш лексер без необходимости писать другие части языка. Вот наш основной файл ржавчины:
mod lexer;
fn main() {
let lex_output: lexer::LexerOutput = lexer::lex();
match lex_output
{
lexer::LexerOutput::Failure(fail) =>
{
eprintln!("{}", fail);
}
lexer::LexerOutput::LexInfo{file_text, tokens, errors, ..} =>
{
for token in tokens
{
print!("\"{}\", ", token.to_string(&file_text))
}
println!();
for error in errors
{
eprintln!("{}", error);
}
}
}
}
Первый блок соответствия срабатывает только в том случае, если файл не читается должным образом. Второй блок гораздо важнее: он выводит все токены в списке, а затем выводит все ошибки. Мы проверим это с помощью следующего файла с именем «test.txt».
-1+22 *(3000000000
/ test3)
К сожалению, символ табуляции не отображается правильно в кодовых блоках, поэтому придется использовать пробелы. Сам файл использует вкладку, так что он проверяет все. Мы ожидаем следующее поведение:
- Токены должны быть следующими: -, 1, +, 22, *, (, 3000000000, /, test3, ), EOF
Каждый арифметический оператор и скобка должны быть своим токеном, как и каждое число. Пробелы следует игнорировать. Нераспознанный символ должен начинать токен, который не прерывается до скобки. Наконец, список должен заканчиваться токеном EOF. - Должно быть 2 ошибки: одна для 3000000000 слишком велика для хранения в целочисленном литерале, а другая для «test3» является нераспознаваемым токеном.
Когда мы запускаем cargo run test.txt в терминале, мы получаем следующий результат:
Это именно то, что мы ожидаем! И он также правильно считает строки и столбцы! Наш лексер будет меняться по мере развития нашего языка, но он будет идеально работать для нашего языка калькулятора.
Если вы не возражаете, я был бы очень признателен, если бы вы оставили комментарий, сообщив мне, как вы хотите, чтобы будущие блоги были структурированы. Я новичок в этом, и я не уверен в таких вещах, как количество кода, которое я должен показать. Ваша помощь будет принята с благодарностью.
Спасибо за чтение. В следующий раз мы создадим синтаксический анализатор и сгенерируем абстрактное синтаксическое дерево!
