Привет!
В статье я хочу рассказать как создать свой язык программирования с нуля на Rust. Ориентируюсь я на тех, кто еще не писал свои языки и знает Rust, нужно уже хорошо в нем разбираться. Этот язык для написания я выбрал, потому что в нем очень удобная система типов, что позволяет писать гибкий код, ну и просто потому что он мне нравится)
Также я не являюсь профессионалом в написании языков, и в статье я могу применять не самые эффективные практики, так как это является сугубо моим опытом. Буду рад, если напишите об ошибках в статье, если увидите таковые.
Конкретно в этой части мы напишем лексический анализатор, ниже будет написано подробнее, после заголовка «О моем опыте».
Также еще общий совет чайникам: если не понимаете на лету, пытайтесь вникнуть. Просто я раньше часто когда не понимал, просто забивал на то, что изучал. Сейчас я представляю картину сложного в голове до тех пор, пока не пойму. И как по - это очень эффективно, просто не надо бросать. Можно визуализировать на бумаге или в пеинте, но я просто смотрю на код, и вникаю, вскоре впадаю в «поток», и уже все становится понятно.
О моем опыте
Я один из тех людей, которые не любят читать книги и изучение теории, поэтому начинал изучать создания языков с того самого OwnLang от Annimon'а, а не с чтения книг или поиска статей.
И еще есть одна интересная деталь, до сих пор пока ни один из моих языков не был доведен до ума, так как если я узнавал, что код мог быть лучше, я шел и писал язык с нуля, уже с новыми знаниями.
Цель
Тут быстро пройдемся по пути написания языка и его синтаксиса.
Синтаксис языка будет 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 char
0 | + - * / ! () {} , = ;
| ^Теперь начнем писать лексер. Это будет структура 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 print
3.14 45 100_000
"
.trim();
let tokens = Lexer::new(tokens_str).tokenize();
println!("Source: {}nTokens:", tokens_str);
for tkn in tokens {
println!("{:?}", tkn);
}
}
Итог
Я не ожидал, что получится такая длинная статься :) Я попытался рассказать про каждую строчку, что писал, и обьяснил работу лексера.
Наш лексер умеет токенизировать числа, кейворды, идентификаторы, одиночные символы и литералы строк. Также в некоторых случаях выбрасывать ошибки.
Код можете глянуть на гитхабе в этом репозитории.
В следующей части мы уже будем писать парсер для выражений. Всем пока!
Автор: kiquarsl
