Привет, Хабр!
В статье я хочу рассказать как создать свой язык программирования с нуля на Rust. Ориентируюсь я на тех, кто еще не писал свои языки и знает Rust, нужно уже хорошо в нем разбираться. Этот язык для написания я выбрал, потому что в нем очень удобная система типов, что позволяет писать гибкий код, ну и просто потому что он мне нравится)
Также я не являюсь профессионалом в написании языков, и в статье я могу применять не самые эффективные практики, так как это является сугубо моим опытом. Буду рад, если напишите об ошибках в статье, если увидите таковые.
Конкретно в этой части мы напишем лексический анализатор, ниже будет написано подробнее, после заголовка «О моем опыте».
Также еще общий совет чайникам: если не понимаете на лету, пытайтесь вникнуть. Просто я раньше часто когда не понимал, просто забивал на то, что изучал. Сейчас я представляю картину сложного в голове до тех пор, пока не пойму. И как по — это очень эффективно, просто не надо бросать. Можно визуализировать на бумаге или в пеинте, но я просто смотрю на код, и вникаю, вскоре впадаю в «поток», и уже все становится понятно.
О моем опыте
Я один из тех людей, которые не любят читать книги и изучение теории, поэтому начинал изучать создания языков с того самого OwnLang от Animmon’а, а не с чтения книг или поиска статей.
И еще есть одна интересная деталь, до сих пор пока ни один из моих языков не был доведен до ума, так как если я узнавал, что код мог быть лучше, я шел и писал язык с нуля, уже с новыми знаниями.
Цель
Тут быстро пройдемся по пути написания языка и его синтаксиса.
Синтаксис языка будет Python-подобным, чтобы не добавлять лишних сложностей. Также язык, как уже понятно, будет интерпритируемым. Интерпритация будет работать методом обхода синтаксического дерева (AST). Язык будет с динамической слабой типизацией, то есть у нас можно будет смешивать разные типы и переменные могут менять тип во время выполнения.
Также я думал на счет ошибок. И пришел в простому выводу, мы сделам ошибки через панику, чтобы лишний раз не отвлекаться на них и сосредоточиться на написании языка. В серьезных проектах ни в коем случае так не делайте! Лучше обрабатывать ошибки через Result, но для наброска языка, и нашего гайда сойдет.
Ну и сами типы, изначально у нас будет несколько стандартных типов: String, Boolean, Number. В будущем, возможно, добавим списки и т.д., но пока-что нам хватит этого.
Мы реализуем if-elif-else, функции, цикл while, присвоение переменных, а также встроеные функции по типу print и input.
Код будет выглядеть примерно так:
fn add(a, b) { return a + b}n = num(input("Enter n: "))a = add(num, 5 )if a < 10 { print("a < 10")} elif a > 10 { print("a > 10")} else { print("a = 10")}
Сам путь написания будет таковым:
1) Токенизация — тут разбираем текст на токены, в обьекте токена мы будем хранить несколько полей: номер строки, отступ от насала строки, длинну токена и позицию в тексте, это нам понадобится для поиска и показа ошибок в коде. Также в токене будет храниться его тип, это может быть как просто символ, например Plus, Minus, так и идентификатор, строка, число или ключевое слово.
2) Парсинг — тут, думаю, самое сложное для чайников. Создаем AST (Abstract Syntax Tree). Я сам долго не мог зашарить за это (По понятным причинам), но если не разбираетесь, лучше все-таки гляньте книгу, например «Engeneering A Compiler», или просто поищите статьи на эту тему. Я сам лично пытался разобраться сам, на своем опыте, но вам лучше все-таки просто погуглить) Ну и теперь про сам парсинг.
Изначально мы должны научить парсер парсить выражения: бинарные операции (+-*/), сравнения (<, >, >=, <=, ==, !=) и логические операции (&& (и), || (или)), также скобки. Приоритет операторов будет строиться на рекурсивном спуске:
-
primary — определение типа токена, если токен не может быть в выражении, то паникуем
-
unary — проверка на операторы типа ! (не) и — (отрицательное значение)
-
multiplicative — считаем всё умножение и деление
-
additive — считаем сложение и вычитание по порядку
Сравнение (comparison) и логические операции (logical) будет легко добавить позже, пока-что нам хватит этого. Также, после этого, нам предстоит парсить конструкции — это if-elif-else, return (это тоже отдельный стейтмент), вызов функций, определение функций и т.д.. Подругому их называют Стейтментами (Statement).
3) Пришло время интерпритатора! У нас будет перечисление — Stmt, там будут храниться все типы стейтментов, присвоение, определение функции и тд. У каждого типа будет своя реализация метода exec(&self, rt: &mut Runtime). Также, в будущем, мы легко сможем добавить комптляцию в байткод или промежуточный язык (например, QBE и LLVM).
Начинаем писать!
Создадии 3 файла в пакете lexer: mod.rs, token.rs и lexer.rs.
Для начала разберем token.rs.
TokenKind — эти тип токена, он может быть оператором, ключевым словом или любым другим символом языка. Ниже я написал enum с всем тем, что нам понадобится в ближайшее время. Для удобства, я сделал псевдоним TKind.
Идентификаторы (Имена переменных, функций) хранятся как строки. Для чисел и строк в enum, есть постфикс «Lit» — Literal, то есть значение записаное непременно в коде, это могут быть, в нашем случае, строки и числа.
Кейворды, для простоты, все хранятся в также как отдельные токены, включая встроенные функции: print, input, num, str.
lexer/token.rs: TokenKind
pub type TKind = TokenKind;#[derive(Debug, Clone)]pub enum TokenKind { Plus, // + Minus, // - Slash, // / Star, // * LBrace, // { RBrace, // } LParen, // ( RParen, // ) Comma, // , Assign, // = Bang, // ! Gt, // > Lt, // < Ge, // >= Le, // <= Eq, // == Ne, // != And, // && Or, // || Id(String), StrLit(String), NumLit(f64), Bool(bool), // Keywords Fn, If, Elif, Else, While, Break, Continue, Return, // Functions Print, Input, Num, Str, Eof,}
lexer/token.rs: Token
#[derive(Debug, Clone)]pub struct Token { pub kind: TKind, pub len: usize, pub pos: usize, pub line: usize, pub offset: usize,}
В токене, как я писал ранее, мы храним его тип, и 2 вида позиции в тексте: абсолютную (pos), и относительно строки (line, offset), также len для показа длинных ошибок.
line и offset нам понадобится для показа ошибок, чтобы взять всю строку из текста, показать номер строки, и позицию с ошибкой. pos и len нужны для показа ошибок уже в рантайме интерпритатора или в кодогенераторе (Если говорим про компилятор)
Пример ошибки
Error in 0:20 - Unknown char0 | + - * / ! () {} , = ; | ^
Теперь начнем писать лексер. Это будет структура Lexer. В ней мы храним: pos, line, offset, lines, chars, tokens.
pos и chars нужны для итерации по тексту, чтобы просто переберать символы.
line и offset — их считаем для токенов, чтобы токены получали свои ползиции.
lines — нужен для ошибок, отсюда берем строку, и показываем, например, не коректный токен.
tokens — сдесь будем хранить токены, сдесь, потому-что я выделю метод для более удобного добавления токенов, позже об этом расскажу.
lexer/lexer.rs: Lexer
pub struct Lexer<'a> { pos: usize, chars: Vec<char>, lines: Vec<&'a str>, line: usize, offset: usize,}impl<'a> Lexer<'a> { pub fn new(source: &'a str) -> Self { let lines = source.lines().collect(); let chars = source.chars().collect(); Self { lines, chars, pos: 0, line: 0, offset: 0, } }}
Пишем вспомогательные методы
error(msg, line_num, offset, len) -> String: метод которые форматирует переданные данные, и возвращает нам строку с ошибкой. Позже просто будем вызывать панику передаваяту строку.
fn error(&self, msg: &str, line_num: usize, offset: usize, len: usize) -> String { let line = self.lines[line_num]; let header = format!("Error in {line_num}:{offset} - {msg}"); let err_line = format!("{line_num} | {line}"); let point = format!( "{} | {}{}", " ".repeat(line_num.to_string().len()), " ".repeat(offset), "^".repeat(len), ); format!("{header}\n{err_line}\n{point}\n")}
peek(offset) -> char: берет символ из self.chars с индексом self.pos + offset, в случае невалидного символа (Ну или выход за границы строки) вызовет панику, в случае успеха вернет char.
fn peek(&self, offset: i8) -> char { let idx = self.pos + offset as usize; let c = self.chars.get(idx); match c { Some(ch) => *ch, None => panic!( "{}", self.error("Out of bounds index", self.line, self.offset, 1) ), }}
advance(offset): Прибавляем переданный offset к self.offset и self.pos. Тоесть метод для пропуска символов.
fn advance(&mut self, offset: u8) { self.offset += offset as usize; self.pos += offset as usize;}
push(kind, line_num, offset, len, pos): просто создает токен м добавляет его в self.tokens
fn push(&mut self, kind: TKind, line: usize, offset: usize, len: usize, pos: usize) { self.tokens.push(Token { kind, line, offset, len, pos, });}
Токенизация
lexer/lexer.rs: Lexer
impl Lexer<'_> { pub fn tokenize(&mut self) -> Vec<Token> { while self.pos < self.chars.len() { let current = self.peek(0); let line = self.line; let offset = self.offset; let pos = self.pos; match current { c if c.is_whitespace() => { if c == '\n' { self.line += 1; self.offset = 0; } else { self.advance(1); } } '+' => { self.push(TKind::Plus, line, offset, 1, pos); self.advance(1); } '-' => { self.push(TKind::Plus, line, offset, 1, pos); self.advance(1); } '*' => { self.push(TKind::Plus, line, offset, 1, pos); self.advance(1); } '/' => { self.push(TKind::Plus, line, offset, 1, pos); self.advance(1); } '(' => { self.push(TKind::LParen, line, offset, 1, pos); self.advance(1); } ')' => { self.push(TKind::RParen, line, offset, 1, pos); self.advance(1); } '{' => { self.push(TKind::LBrace, line, offset, 1, pos); self.advance(1); } '}' => { self.push(TKind::RBrace, line, offset, 1, pos); self.advance(1); } ',' => { self.push(TKind::Comma, line, offset, 1, pos); self.advance(1); } '=' => { self.push(TKind::Assign, line, offset, 1, pos); self.advance(1); } '!' => { self.push(TKind::Assign, line, offset, 1, pos); self.advance(1); } _ => panic!("{}", self.error("Unknown char", line, offset, 1)), } } self.push(TKind::Eof, self.line, self.offset, 1, self.pos); self.tokens.clone() }}
Тут перебераем символы до тех пор, пока self.pos будет меньше чем длинна переданного текста. В цикле мы сохраняем текущие: self.line, self.offset, self.pos и получаем текущий символ. сохранение позиций нам понадобится для символов длиннее 1, например «==».
После этого, в match проверяем что такое наш текущий символ.
c if c.is_whitespace() => { if c == '\n' { self.line += 1; self.advance(1); self.offset = 0; } else { self.advance(1); }}
Сразу проверяем не является ли текущий символ пробелом, если это пробел, и еще к этому перенос строки, то прибавляем 1 к self.line, пропцскаем символ с помощью self.advance(1) и присваиваем 0 к self.offset (Так как advance прибавляет 1 к оффсету, мы должно его обнулить, чтобы показать начало строки). Если мы любой другой символ пробела, просто вызываем self.advance(1).
Далее проверяем все возможные одиночные символы.
'+' => { self.push(TKind::Plus, line, offset, 1, pos); self.advance(1);}
Если мы встретили этот символ, то вызываем self.push, указываем что за токен мы нашли, и пеоедаем сохраненные line, offset и pos. В len передаем 1, так как это длинна 1-го символа. После пропускаем текущий символ. По такому-же алгоритму пишем проверки на каждый одиночный символ. В случае ошибки или неизвестного символа просто паникуем.
После цикла добавляем токен TKind::Eof, это символ окончания строки, расшифровывается как «End Of File». Он нам поможет парсить выражения в будущем.
Теперь напишем тест для лексера. Создаем папку tests в корне проекта, и в этой папке файл с расширением «.rs», у меня это будет «lexert.rs».
tests/lexert.rs
use guidzy::lexer::Lexer;#[test]fn main() { let tokens_str = "+ - * / ! () {} , ="; let tokens = Lexer::new(tokens_str).tokenize(); println!("Source: {}\nTokens:", tokens_str); for tkn in tokens { println!("{:?}", tkn); }}
Чтобы запустить тест в видимым выводом, используем эту комманду в терминале:
cargo test -- --nocapture
Если в строке найдется неизвестный символ, нам выдаст ошибку.
Теперь научим лексер токенизировать токены из 2-х символов.
'=' => {if self.pos + 1 < chars_len && self.peek(1) == '=' { self.push(TKind::Eq, line, offset, 1, pos); self.advance(2); } else { self.push(TKind::Assign, line, offset, 1, pos); self.advance(1); }}
В примере будем читать токен «==». Сначало проверяем, если текущая позиция + 1 (следующий символ) меньше, чем длинна текста, проверяем с помощью self.peek(1), не является ли следующий токен также «=». Если да, то пушим в список токенов TKind::Eq, в len указываем длинну 2, и в self.advance также пропускаем 2 текущих символа. По такой же логике парсим такие токены как «<=», «>=», «!=» и тд.
Также рассмотрим кейс, когда символ может быть только двойным на примере «&&»
'&' => { if self.pos + 1 < chars_len && self.peek(1) == '&' { self.push(TKind::And, line, offset, 2, pos); self.advance(2); } else { panic!("{}", self.error("Expected &&", line, offset, 1)); }}
Тут также как ранее проверяем следующий символ, но тут, в случае, когда следующий символ не может быть любым, а только «&», выдаем ошибку «Exprected» (С англ. «Ожидалось»). Тоже самое применяем к «||»>
lexer/lexer.rs:Lexer (весь блок с tokenize)
impl Lexer<'_> { pub fn tokenize(&mut self) -> Vec<Token> { let chars_len = self.chars.len(); while self.pos < chars_len { let current = self.peek(0); let line = self.line; let offset = self.offset; let pos = self.pos; match current { c if c.is_whitespace() => { if c == '\n' { self.line += 1;self.advance(1);self.offset = 0; } else { self.advance(1); } } '+' => { self.push(TKind::Plus, line, offset, 1, pos); self.advance(1); } '-' => { self.push(TKind::Minus, line, offset, 1, pos); self.advance(1); } '*' => { self.push(TKind::Star, line, offset, 1, pos); self.advance(1); } '/' => { self.push(TKind::Slash, line, offset, 1, pos); self.advance(1); } '(' => { self.push(TKind::LParen, line, offset, 1, pos); self.advance(1); } ')' => { self.push(TKind::RParen, line, offset, 1, pos); self.advance(1); } '{' => { self.push(TKind::LBrace, line, offset, 1, pos); self.advance(1); } '}' => { self.push(TKind::RBrace, line, offset, 1, pos); self.advance(1); } ',' => { self.push(TKind::Comma, line, offset, 1, pos); self.advance(1); } '=' => { if self.pos + 1 < chars_len && self.peek(1) == '=' { self.push(TKind::Eq, line, offset, 2, pos); self.advance(2); } else { self.push(TKind::Assign, line, offset, 1, pos); self.advance(1); } } '!' => { if self.pos + 1 < chars_len && self.peek(1) == '=' { self.push(TKind::Ne, line, offset, 2, pos); self.advance(2); } else { self.push(TKind::Bang, line, offset, 1, pos); self.advance(1); } } '>' => { if self.pos + 1 < chars_len && self.peek(1) == '=' { self.push(TKind::Ge, line, offset, 2, pos); self.advance(2); } else { self.push(TKind::Gt, line, offset, 1, pos); self.advance(1); } } '<' => { if self.pos + 1 < chars_len && self.peek(1) == '=' { self.push(TKind::Le, line, offset, 2, pos); self.advance(2); } else { self.push(TKind::Lt, line, offset, 1, pos); self.advance(1); } } '&' => { if self.pos + 1 < chars_len && self.peek(1) == '&' { self.push(TKind::And, line, offset, 2, pos); self.advance(2); } else { panic!("{}", self.error("Expected &&", line, offset, 1)); } } '|' => { if self.pos + 1 < chars_len && self.peek(1) == '|' { self.push(TKind::Or, line, offset, 2, pos); self.advance(2); } else { panic!("{}", self.error("Expected ||", line, offset, 1)); } } _ => panic!("{}", self.error("Unknown char", line, offset, 1)), } } self.push(TKind::Eof, self.line, self.offset, 1, self.pos); self.tokens.clone() }}
Обновляем тест tests/lexert.rs
use guidzy::lexer::Lexer;#[test]fn main() { let tokens_str = "+ - * / ! () {} , = && || < > <= >= == !="; let tokens = Lexer::new(tokens_str).tokenize(); println!("Source: {}\nTokens:", tokens_str); for tkn in tokens { println!("{:?}", tkn); }}
Токенизация литералла строки
fn tokenize_string(&mut self) { let mut buffer = String::new(); let line = self.line; let offset = self.offset; let pos = self.pos; self.advance(1); loop { let current = self.peek(0); self.advance(1); if current == '"' { break; } else { buffer.push(current); } } self.push( TKind::StrLit(buffer.clone()), line, offset, buffer.len() + 2, pos, );}
Тут создаем буффер для содержимого строки, сохраняем текущий номеи строки, отступ от начала строки и позицию. Пропускаем первую кавычку с помощью self.advance(1).
В бесконечном цикле берем текущий символ, и сразу проускаем его, проверяем: если этот символ кавычка, то выходим из цикла. Мы до этого пропустили символ, так что вторая кавычка также пропущена. Если это любой другой символ, то просто добавляем его в буффер.
Когда мы нашли всю строку, мы просто пушим ее как литерал строки. В длинне указываем длинну буффера + 2. Зачем еще 2? При токенизации строки, мы не берем 2 кавычки в значение, но строка, включая эти кавычки — это 1 токен. Это нам позволит в ошибках выделять весь литерал.
Добавляем в match новое условие:
c if c == '"' => self.tokenize_string(),
Добавляем строку в тест tests/lexert.rs
use guidzy::lexer::Lexer;#[test]fn main() { let tokens_str = "+ - * / ! () {} , = && || < > <= >= == !=\"my string\"".trim(); let tokens = Lexer::new(tokens_str).tokenize(); println!("Source: {}\nTokens:", tokens_str); for tkn in tokens { println!("{:?}", tkn); }}
Токенизация идентификаторов и кейвордов
lexer/lexer.rs: Lexer
fn tokenize_ident(&mut self) { let mut buffer = String::new(); let line = self.line; let offset = self.offset; let pos = self.pos; loop { if self.pos >= self.chars.len() { break; } let current = self.peek(0); if current.is_alphabetic() || current.is_digit(10) || current == '_' { buffer.push(current); self.advance(1); } else { break; } } let kind = match buffer.as_str() { "true" => TKind::Bool(true), "false" => TKind::Bool(false), "print" => TKind::Print, "input" => TKind::Print, "str" => TKind::Str, "num" => TKind::Num, "fn" => TKind::Fn, "while" => TKind::While, "break" => TKind::Break, "continue" => TKind::Continue, "if" => TKind::If, "elif" => TKind::Elif, "else" => TKind::Else, "return" => TKind::Return, _ => TKind::Id(buffer.clone()), }; self.push(kind, line, offset, buffer.len(), pos);}
Логика похожа на токенизацию строки. Создаем буффер и сохраняем позицию.
Емли не вышли, то берем текущий символ и провряем. В идентификаторе или кейворде могут быть: буквы, числа и знак «_», если этот символ соответсвует этому, пушим его в буффер и пропускаем 1 символ, иначе завершаем цикл.
После мы проверяем буффер на кейворды. Если это true, то возвращаем TKind::Bool(true), если это кейворд или встроеная функция, возвращаем соответствующий тип. Если это не true/false, не кейворд, и не встроеная функция, то возвращаем это как идентификатор.
Потом просто пушим его в токены. В tokenize добавляем новое условие:
c if c.is_alphabetic() => self.tokenize_ident(),
Обновим тест tests/lexert.rs
use guidzy::lexer::Lexer;#[test]fn main() { let tokens_str = "+ - * / ! () {} , = && || < > <= >= == !=\"my string\"my_ident12 true false print" .trim(); let tokens = Lexer::new(tokens_str).tokenize(); println!("Source: {}\nTokens:", tokens_str); for tkn in tokens { println!("{:?}", tkn); }}
Токенизация чисел
lexer/lexer.rs: Lexer
fn tokenize_number(&mut self) { let mut buffer = String::new(); let line = self.line; let offset = self.offset; let pos = self.pos; loop { if self.pos >= self.chars.len() { break; } let current = self.peek(0); if current.is_digit(10) || current == '.' { buffer.push(current); self.advance(1); } else if current == '_' { self.advance(1); } else { break; } } self.push( TKind::NumLit(buffer.parse::<f64>().expect("Failed parse number")), line, offset, buffer.len(), pos, );}
Тут создаем буффер и сохраняем позицию. В цикле проверяем, не вышли ли мы за границу, в случае выхода завершаем цикл.
После цикла мы пушим его в токены. Парсим строку buffer как f64, и выбрасываем ошибку, если не удалось спарсить.
Обновим тест tests/lexert.rs
use guidzy::lexer::Lexer;#[test]fn main() { let tokens_str = "+ - * / ! () {} , = && || < > <= >= == !=\"my string\"my_ident12 true false print3.14 45 100_000" .trim(); let tokens = Lexer::new(tokens_str).tokenize(); println!("Source: {}\nTokens:", tokens_str); for tkn in tokens { println!("{:?}", tkn); }}
Итог
Я не ожидал, что получится такая длинная статься 🙂 Я попытался рассказать про каждую строчку, что писал, и обьяснил работу лексера.
Наш лексер умеет токенизировать числа, кейворды, идентификаторы, одиночные символы и литералы строк. Также в некоторых случаях выбрасывать ошибки.
Код можете глянуть на гитхабе в этом репозитории.
В следующей части мы уже будем писать парсер для выражений. Всем пока!
ссылка на оригинал статьи https://habr.com/ru/articles/1044358/