Привет, Хабр!

В статье я хочу рассказать как создать свой язык программирования с нуля на 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», или просто поищите статьи на эту тему. Я сам лично пытался разобраться сам, на своем опыте, но вам лучше все-таки просто погуглить) Ну и теперь про сам парсинг.

Изначально мы должны научить парсер парсить выражения: бинарные операции (+-*/), сравнения (<, >, >=, <=, ==, !=) и логические операции (&& (и), || (или)), также скобки. Приоритет операторов будет строиться на рекурсивном спуске:

1. primary - определение типа токена, если токен не может быть в выражении, то паникуем

2. unary - проверка на операторы типа ! (не) и - (отрицательное значение)

3. multiplicative - считаем всё умножение и деление

4. 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.

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,
}

#[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 - здесь будем хранить токены, потому что я выделю метод для более удобного добавления токенов, позже об этом расскажу.

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,
    });
}

Токенизация

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.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».

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));
    }
}

Тут также как ранее проверяем следующий символ, но тут, в случае, когда следующий символ не может быть любым, а только «&», выдаем ошибку «Expected» (С англ. «Ожидалось»). Тоже самое применяем к «||»>

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()
    }
}

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(),

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);
    }
}

Токенизация идентификаторов и кейвордов

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(),

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);
    }
}

Токенизация чисел

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, и выбрасываем ошибку, если не удалось спарсить.

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);
    }
}

Итог

Я не ожидал, что получится такая длинная статья :) Я попытался рассказать про каждую строчку, что писал, и обьяснил работу лексера.

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

Код можете глянуть на гитхабе в этом репозитории.

В следующей части мы уже будем писать парсер для выражений. Всем пока!