Минимальная реализация Lua на Rust

После того, как вы освоите это руководство, в вашем распоряжении окажется минимальная реализация Lua (парсер, компилятор, виртуальная машина), написанная на Rust с чистого листа. Этот проект получил название Lust, его код можно найти на GitHub.



С его помощью, кроме прочих, можно запустить такую программу:

function fib(n)
   if n < 2 then
      return n;
   end

   local n1 = fib(n-1);
   local n2 = fib(n-2);
   return n1 + n2;
end

print(fib(30));

Это — мой второй Rust-проект. А выдумыванием набора инструкций я занимаюсь лишь в третий раз. Поэтому прошу не принимать мой стиль программирования за истину в последней инстанции. Полагаю, этот материал может быть интересен тем, кто, как и я, смотрел другие руководства по парсингу команд в Rust и счёл их неоправданно сложными. Надеюсь, моя статья окажется проще тех руководств.

Начало работы

Команда cargo init создаст шаблонный пакет Cargo, который послужит отправной точкой нашего проекта. В коде файла src/main.rs мы принимаем имя файла из параметров командной строки и выполняем лексический анализ находящегося в нём текста программы, выделяя токены. Далее — выполняем грамматический анализ токенов и формируем древовидную структуру. После этого компилируем полученное дерево в линейный набор инструкций виртуальной машины. А в итоге мы интерпретируем инструкции виртуальной машины.

mod eval;
mod lex;
mod parse;

use std::env;
use std::fs;

fn main() {
    let args: Vec<String> = env::args().collect();
    let contents = fs::read_to_string(&args[1]).expect("Could not read file");

    let raw: Vec<char> = contents.chars().collect();

    let tokens = match lex::lex(&raw) {
        Ok(tokens) => tokens,
        Err(msg) => panic!("{}", msg),
    };

    let ast = match parse::parse(&raw, tokens) {
        Ok(ast) => ast,
        Err(msg) => panic!("{}", msg),
    };

    let pgrm = eval::compile(&raw, ast);

    eval::eval(pgrm);
}

Как видите, пока всё очень просто. Реализуем теперь лексический анализатор.

Лексический анализ

В ходе лексического анализа убирают пробельные символы (они, за исключением тех, что разделяют имена и ключевые слова, Lua безразличны) и разбивают все символы исходного кода на минимальные имеющие смысл фрагменты, вроде запятых, чисел, идентификаторов, ключевых слов и прочих подобных элементов.

Для того чтобы у нас была бы возможность выдавать осмысленные сообщения об ошибках, мы храним сведения о том, с чем именно в файле мы работаем, пользуясь структурой Location, реализующей increment и debug. Следующий код будет в файле src/lex.rs.

#[derive(Copy, Clone, Debug)]
pub struct Location {
    col: i32,
    line: i32,
    index: usize,
}

Функция increment отвечает за обновление номеров строк и столбцов, а так же — за текущее значение индекса, по которому осуществляется работа с содержимым файла.

impl Location {
    fn increment(&self, newline: bool) -> Location {
        if newline {
            Location {
                index: self.index + 1,
                col: 0,
                line: self.line + 1,
            }
        } else {
            Location {
                index: self.index + 1,
                col: self.col + 1,
                line: self.line,
            }
        }
    }

Функция debug выдаёт информацию о текущей строке с указателем на её текущий столбец и с сообщением.

    pub fn debug<S: Into<String>>(&self, raw: &[char], msg: S) -> String {
        let mut line = 0;
        let mut line_str = String::new();
        // Поиск конкретной строки в первоначальном исходном коде
        for c in raw {
            if *c == '\n' {
                line += 1;

                // Выполняем поиск интересующей нас строки
                if !line_str.is_empty() {
                    break;
                }

                continue;
            }

            if self.line == line {
                line_str.push_str(&c.to_string());
            }
        }

        let space = " ".repeat(self.col as usize);
        format!("{}\n\n{}\n{}^ Near here", msg.into(), line_str, space)
    }
}

Наименьший отдельный элемент, который оказывается в нашем распоряжении после лексического анализа кода — это токен. Он может быть ключевым словом, идентификатором, оператором или синтаксической конструкцией. (В этой реализации Lua мы сознательно опускаем множество реальных синтаксических конструкций Lua наподобие строк.)

#[derive(Debug, PartialEq, Eq, Clone)]
pub enum TokenKind {
    Identifier,
    Syntax,
    Keyword,
    Number,
    Operator,
}

#[derive(Debug, Clone)]
pub struct Token {
    pub value: String,
    pub kind: TokenKind,
    pub loc: Location,
}

Функция верхнего уровня lex будет перебирать элементы файла и вызывать вспомогательные функции лексического анализа для токенов разных видов. После успешного завершения работы она возвратит массив, содержащий все найденные токены. В процессе лексического анализа она будет «поглощать пробельные символы».

pub fn lex(s: &[char]) -> Result<Vec<Token>, String> {
    let mut loc = Location {
        col: 0,
        index: 0,
        line: 0,
    };
    let size = s.len();
    let mut tokens: Vec<Token> = vec![];

    let lexers = [
        lex_keyword,
        lex_identifier,
        lex_number,
        lex_syntax,
        lex_operator,
    ];
    'outer: while loc.index < size {
        loc = eat_whitespace(s, loc);
        if loc.index == size {
            break;
        }

        for lexer in lexers {
            let res = lexer(s, loc);
            if let Some((t, next_loc)) = res {
                loc = next_loc;
                tokens.push(t);
                continue 'outer;
            }
        }

        return Err(loc.debug(s, "Unrecognized character while lexing:"));
    }

    Ok(tokens)
}

▍Пробельные символы

Поглощение пробельных символов — это всего лишь увеличение значения переменной, хранящей позицию в файле при нахождении пробела, символа табуляции, символа перехода на новую строку и прочих подобных.

fn eat_whitespace(raw: &[char], initial_loc: Location) -> Location {
    let mut c = raw[initial_loc.index];
    let mut next_loc = initial_loc;
    while [' ', '\n', '\r', '\t'].contains(&c) {
        next_loc = next_loc.increment(c == '\n');
        if next_loc.index == raw.len() {
            break;
        }
        c = raw[next_loc.index];
    }

    next_loc
}

▍Числа

Лексический анализатор чисел проходится по исходному коду начиная с определённой позиции и до того места, где заканчивается последовательность десятичных цифр (в этой реализации Lua поддерживаются лишь целые числа).

fn lex_number(raw: &[char], initial_loc: Location) -> Option<(Token, Location)> {
    let mut ident = String::new();
    let mut next_loc = initial_loc;
    let mut c = raw[initial_loc.index];
    while c.is_digit(10) {
        ident.push_str(&c.to_string());
        next_loc = next_loc.increment(false);
        c = raw[next_loc.index];
    }

Если цифр в строке нет — значит — это не число.

    if !ident.is_empty() {
        Some((
            Token {
                value: ident,
                loc: initial_loc,
                kind: TokenKind::Number,
            },
            next_loc,
        ))
    } else {
        None
    }
}

▍Идентификаторы

Идентификатор — это произвольный набор алфавитных символов, цифр и знаков подчёркивания.

fn lex_identifier(raw: &Vec<char>, initial_loc: Location) -> Option<(Token, Location)> {
    let mut ident = String::new();
    let mut next_loc = initial_loc;
    let mut c = raw[initial_loc.index];
    while c.is_alphanumeric() || c == '_' {
        ident.push_str(&c.to_string());
        next_loc = next_loc.increment(false);
        c = raw[next_loc.index];
    }

Но идентификатор не может начинаться с цифры.

    // Первый символ не должен быть цифрой
    if ident.len() > 0 && !ident.chars().next().unwrap().is_digit(10) {
        Some((
            Token {
                value: ident,
                loc: initial_loc,
                kind: TokenKind::Identifier,
            },
            next_loc,
        ))
    } else {
        None
    }
}

▍Ключевые слова

Ключевые слова состоят из алфавитных символов, что роднит их с идентификаторами, но программист не может использовать их в качестве имён переменных.

fn lex_keyword(raw: &[char], initial_loc: Location) -> Option<(Token, Location)> {
    let syntax = ["function", "end", "if", "then", "local", "return"];

    let mut next_loc = initial_loc;
    let mut value = String::new();
    'outer: for possible_syntax in syntax {
        let mut c = raw[initial_loc.index];
        next_loc = initial_loc;
        while c.is_alphanumeric() || c == '_' {
            value.push_str(&c.to_string());
            next_loc = next_loc.increment(false);
            c = raw[next_loc.index];

            let n = next_loc.index - initial_loc.index;
            if value != possible_syntax[..n] {
                value = String::new();
                continue 'outer;
            }
        }

        // Неполное совпадение
        if value.len() < possible_syntax.len() {
            value = String::new();
            continue;
        }

        // Если мы добрались до этого места - значит — совпадение найдено и можно выполнить ранний выход из функции.
        // Нам не нужно совпадение с более длинной последовательностью символов.
        break;
    }

    if value.is_empty() {
        return None;
    }

Помимо выполнения сравнений фрагментов кода со списком строк, нам нужно ещё убедиться в том, что перед нами — полное совпадение с нужным словом. Например, function1 — это не ключевое слово. Это — допустимый идентификатор. И хотя function 1 — это правильная последовательность токенов (ключевое слово function и число 1), она не относится к допустимым грамматическим конструкциям Lua.

    // Если следующий символ будет частью допустимого идентификатора, тогда
    // это - не ключевое слово.
    if next_loc.index < raw.len() - 1 {
        let next_c = raw[next_loc.index];
        if next_c.is_alphanumeric() || next_c == '_' {
            return None;
        }
    }

    Some((
        Token {
            value: value,
            loc: initial_loc,
            kind: TokenKind::Keyword,
        },
        next_loc,
    ))
}

▍Синтаксические конструкции

Синтаксические конструкции (в этом контексте) — это просто фрагменты кода, не являющиеся операторами. Это нечто вроде запятых, скобок и так далее.

fn lex_syntax(raw: &[char], initial_loc: Location) -> Option<(Token, Location)> {
    let syntax = [";", "=", "(", ")", ","];

    for possible_syntax in syntax {
        let c = raw[initial_loc.index];
        let next_loc = initial_loc.increment(false);
        // TODO: это не будет работать с многосимвольными синтаксическими конструкциями вроде >= или ==
        if possible_syntax == c.to_string() {
            return Some((
                Token {
                    value: possible_syntax.to_string(),
                    loc: initial_loc,
                    kind: TokenKind::Syntax,
                },
                next_loc,
            ));
        }
    }

    None
}

▍Операторы

Операторы — это нечто вроде плюса, минуса и знака «меньше». Операторы — это синтаксические конструкции, но выделение их в отдельную группу токенов пригодится нам в дальнейшей работе.

fn lex_operator(raw: &[char], initial_loc: Location) -> Option<(Token, Location)> {
    let operators = ["+", "-", "<"];

    for possible_syntax in operators {
        let c = raw[initial_loc.index];
        let next_loc = initial_loc.increment(false);
        // TODO: это не будет работать с многосимвольными синтаксическими конструкциями вроде >= или ==
        if possible_syntax == c.to_string() {
            return Some((
                Token {
                    value: possible_syntax.to_string(),
                    loc: initial_loc,
                    kind: TokenKind::Operator,
                },
                next_loc,
            ));
        }
    }

    None
}

На этом мы завершили создание системы лексического анализа!

Грамматический анализ

В ходе парсинга выполняется поиск грамматических (древовидных) паттернов в плоском списке токенов. То, что получается, называется синтаксическим деревом или абстрактным синтаксическим деревом (AST, Abstract Syntax Tree).

Тут нам предстоит решить одну скучную задачу, которая заключается в определении дерева. В общем случае (и, конкретно, в этом проекте), синтаксическое дерево — это список инструкций. Инструкция может быть объявлением функции или выражением. Она может быть представлена инструкцией if или return. Это может быть объявление локальной переменной.

Следующий код размещён в файле src/parse.rs.

#[derive(Debug)]
pub enum Statement {
    Expression(Expression),
    If(If),
    FunctionDeclaration(FunctionDeclaration),
    Return(Return),
    Local(Local),
}

pub type Ast = Vec<Statement>;

В остальном определение дерева не содержит практически ничего особенного.

#[derive(Debug)]
pub enum Literal {
    Identifier(Token),
    Number(Token),
}

#[derive(Debug)]
pub struct FunctionCall {
    pub name: Token,
    pub arguments: Vec<Expression>,
}

#[derive(Debug)]
pub struct BinaryOperation {
    pub operator: Token,
    pub left: Box<Expression>,
    pub right: Box<Expression>,
}

#[derive(Debug)]
pub enum Expression {
    FunctionCall(FunctionCall),
    BinaryOperation(BinaryOperation),
    Literal(Literal),
}

#[derive(Debug)]
pub struct FunctionDeclaration {
    pub name: Token,
    pub parameters: Vec<Token>,
    pub body: Vec<Statement>,
}

#[derive(Debug)]
pub struct If {
    pub test: Expression,
    pub body: Vec<Statement>,
}

#[derive(Debug)]
pub struct Local {
    pub name: Token,
    pub expression: Expression,
}

#[derive(Debug)]
pub struct Return {
    pub expression: Expression,
}

Работа над AST завершена!

▍Вспомогательные механизмы

Теперь, прежде чем мы перейдём к самому интересному, нам надо определить несколько вспомогательных функций для проверки токенов разного вида.

fn expect_keyword(tokens: &[Token], index: usize, value: &str) -> bool {
    if index >= tokens.len() {
        return false;
    }

    let t = tokens[index].clone();
    t.kind == TokenKind::Keyword && t.value == value
}

fn expect_syntax(tokens: &[Token], index: usize, value: &str) -> bool {
    if index >= tokens.len() {
        return false;
    }

    let t = tokens[index].clone();
    t.kind == TokenKind::Syntax && t.value == value
}

fn expect_identifier(tokens: &[Token], index: usize) -> bool {
    if index >= tokens.len() {
        return false;
    }

    let t = tokens[index].clone();
    t.kind == TokenKind::Identifier
}

А теперь пришло время интересных дел. Займёмся работой с  деревьями!

▍Парсинг верхнего уровня

Функция parse верхнего уровня и её основная вспомогательная функция, parse_statement, очень похожи на функцию lex верхнего уровня. При анализе инструкции из файла выполняется проверка того, является ли она объявлением функции, инструкцией if или return, объявлением локальной переменной или инструкцией-выражением.

fn parse_statement(raw: &[char], tokens: &[Token], index: usize) -> Option<(Statement, usize)> {
    let parsers = [
        parse_if,
        parse_expression_statement,
        parse_return,
        parse_function,
        parse_local,
    ];
    for parser in parsers {
        let res = parser(raw, tokens, index);
        if res.is_some() {
            return res;
        }
    }

    None
}

pub fn parse(raw: &[char], tokens: Vec<Token>) -> Result<Ast, String> {
    let mut ast = vec![];
    let mut index = 0;
    let ntokens = tokens.len();
    while index < ntokens {
        let res = parse_statement(raw, &tokens, index);
        if let Some((stmt, next_index)) = res {
            index = next_index;
            ast.push(stmt);
            continue;
        }

        return Err(tokens[index].loc.debug(raw, "Invalid token while parsing:"));
    }

    Ok(ast)
}

▍Инструкции-выражения

Инструкция-выражение — это всего лишь обёртка для системы типов Rust. Она оборачивает выражение в инструкцию, осуществляет вызов функции parse_expression (которую мы скоро определим), в её конце ожидается наличие точки с запятой.

fn parse_expression_statement(
    raw: &[char],
    tokens: &[Token],
    index: usize,
) -> Option<(Statement, usize)> {
    let mut next_index = index;
    let res = parse_expression(raw, tokens, next_index)?;

    let (expr, next_next_index) = res;
    next_index = next_next_index;
    if !expect_syntax(tokens, next_index, ";") {
        println!(
            "{}",
            tokens[next_index]
                .loc
                .debug(raw, "Expected semicolon after expression:")
        );
        return None;
    }

    next_index += 1; // Пропустить точку с запятой

    Some((Statement::Expression(expr), next_index))
}

▍Выражения

Выражения в этой минимальной реализации Lua могут быть представлены лишь отдельными вызовами функций, литералами (числами, идентификаторами) или операциями с двумя операндами. Для того чтобы ничего не усложнять, тут операции с двумя операндами нельзя комбинировать. То есть, вместо конструкции вроде 1 + 2 + 3 надо воспользоваться конструкцией local tmp1 = 1 + 2; local tmp2 = tmp1 + 3; и так далее.

fn parse_expression(raw: &[char], tokens: &[Token], index: usize) -> Option<(Expression, usize)> {
    if index >= tokens.len() {
        return None;
    }

    let t = tokens[index].clone();
    let left = match t.kind {
        TokenKind::Number => Expression::Literal(Literal::Number(t)),
        TokenKind::Identifier => Expression::Literal(Literal::Identifier(t)),
        _ => {
            return None;
        }
    };

Если за первым литералом идёт открытая скобка — значит — мы попытаемся распарсить вызов функции.

    let mut next_index = index + 1;
    if expect_syntax(tokens, next_index, "(") {
        next_index += 1; // Пропустить открытую скобку

        // Вызов функции
        let mut arguments: Vec<Expression> = vec![];

Для каждого из аргументов, переданных функции, нужно рекурсивно вызывать parse_expression.

        while !expect_syntax(tokens, next_index, ")") {
            if arguments.is_empty() {
                if !expect_syntax(tokens, next_index, ",") {
                    println!(
                        "{}",
                        tokens[next_index]
                            .loc
                            .debug(raw, "Expected comma between function call arguments:")
                    );
                    return None;
                }

                next_index += 1; // Пропустить запятую
            }

            let res = parse_expression(raw, tokens, next_index);
            if let Some((arg, next_next_index)) = res {
                next_index = next_next_index;
                arguments.push(arg);
            } else {
                println!(
                    "{}",
                    tokens[next_index]
                        .loc
                        .debug(raw, "Expected valid expression in function call arguments:")
                );
                return None;
            }
        }

        next_index += 1; // Пропустить открытую скобку

        return Some((
            Expression::FunctionCall(FunctionCall {
                name: tokens[index].clone(),
                arguments,
            }),
            next_index,
        ));
    }

Если же открывающей скобки нет, значит нам надо будет распарсить либо литеральное выражение, либо операцию с двумя операндами. Если следующий токен представлен оператором, значит — перед нами операция с двумя операндами.

    // Это может быть литеральное выражение
    if next_index >= tokens.len() || tokens[next_index].clone().kind != TokenKind::Operator {
        return Some((left, next_index));
    }

    // В противном случае это операция с двумя операндами
    let op = tokens[next_index].clone();
    next_index += 1; // Пропустить операнд

    if next_index >= tokens.len() {
        println!(
            "{}",
            tokens[next_index]
                .loc
                .debug(raw, "Expected valid right hand side binary operand:")
        );
        return None;
    }

    let rtoken = tokens[next_index].clone();

Именно тут мы можем (но не будем) рекурсивно вызывать parse_expression. Прямо сейчас мне не хочется связываться с приоритетом операций, поэтому тут мы просто требуем, чтобы правой частью выражения был бы другой литерал.

    let right = match rtoken.kind {
        TokenKind::Number => Expression::Literal(Literal::Number(rtoken)),
        TokenKind::Identifier => Expression::Literal(Literal::Identifier(rtoken)),
        _ => {
            println!(
                "{}",
                rtoken
                    .loc
                    .debug(raw, "Expected valid right hand side binary operand:")
            );
            return None;
        }
    };
    next_index += 1; // Пропустить операнд из правой части выражения

    Some((
        Expression::BinaryOperation(BinaryOperation {
            left: Box::new(left),
            right: Box::new(right),
            operator: op,
        }),
        next_index,
    ))
}

На этом парсинг выражений завершён!

▍Объявления функций

Объявление функции начинается с ключевого слова function, за которым следует токен идентификатора.

fn parse_function(raw: &[char], tokens: &[Token], index: usize) -> Option<(Statement, usize)> {
    if !expect_keyword(tokens, index, "function") {
        return None;
    }

    let mut next_index = index + 1;
    if !expect_identifier(tokens, next_index) {
        println!(
            "{}",
            tokens[next_index]
                .loc
                .debug(raw, "Expected valid identifier for function name:")
        );
        return None;
    }
    let name = tokens[next_index].clone();

После имени функции расположен список аргументов, который может быть пустым, или список идентификаторов, разделённых запятыми.

    next_index += 1; // Пропустить имя
    if !expect_syntax(tokens, next_index, "(") {
        println!(
            "{}",
            tokens[next_index]
                .loc
                .debug(raw, "Expected open parenthesis in function declaration:")
        );
        return None;
    }

    next_index += 1; // Пропустить открывающую скобку
    let mut parameters: Vec<Token> = vec![];
    while !expect_syntax(tokens, next_index, ")") {
        if !parameters.is_empty() {
            if !expect_syntax(tokens, next_index, ",") {
                println!("{}", tokens[next_index].loc.debug(raw, "Expected comma or close parenthesis after parameter in function declaration:"));
                return None;
            }

            next_index += 1; // Пропустить запятую
        }

        parameters.push(tokens[next_index].clone());
        next_index += 1; // Пропустить параметр
    }

    next_index += 1; // Пропустить закрывающую скобку

Далее — мы выполняем парсинг всех инструкций в теле функции, занимаясь этим до тех пор, пока не найдём ключевое слово end.

    let mut statements: Vec<Statement> = vec![];
    while !expect_keyword(tokens, next_index, "end") {
        let res = parse_statement(raw, tokens, next_index);
        if let Some((stmt, next_next_index)) = res {
            next_index = next_next_index;
            statements.push(stmt);
        } else {
            println!(
                "{}",
                tokens[next_index]
                    .loc
                    .debug(raw, "Expected valid statement in function declaration:")
            );
            return None;
        }
    }

    next_index += 1; // Пропустить end

    Some((
        Statement::FunctionDeclaration(FunctionDeclaration {
            name,
            parameters,
            body: statements,
        }),
        next_index,
    ))
}

Теперь мы завершили половину работ по созданию парсера.

▍Инструкции return

Выявление инструкции return заключается в нахождении ключевого слова return, выражения и точки с запятой.

fn parse_return(raw: &[char], tokens: &[Token], index: usize) -> Option<(Statement, usize)> {
    if !expect_keyword(tokens, index, "return") {
        return None;
    }

    let mut next_index = index + 1; // Пропустить return
    let res = parse_expression(raw, tokens, next_index);
    if res.is_none() {
        println!(
            "{}",
            tokens[next_index]
                .loc
                .debug(raw, "Expected valid expression in return statement:")
        );
        return None;
    }

    let (expr, next_next_index) = res.unwrap();
    next_index = next_next_index;
    if !expect_syntax(tokens, next_index, ";") {
        println!(
            "{}",
            tokens[next_index]
                .loc
                .debug(raw, "Expected semicolon in return statement:")
        );
        return None;
    }

    next_index += 1; // Пропустить точку с запятой

    Some((Statement::Return(Return { expression: expr }), next_index))
}

▍Объявления локальных переменных

Объявления локальных переменных начинаются с ключевого слова local. Потом идёт имя переменной, затем — знак равенства, выражение и точка с запятой.

fn parse_local(raw: &[char], tokens: &[Token], index: usize) -> Option<(Statement, usize)> {
    if !expect_keyword(tokens, index, "local") {
        return None;
    }

    let mut next_index = index + 1; // Пропустить local

    if !expect_identifier(tokens, next_index) {
        println!(
            "{}",
            tokens[next_index]
                .loc
                .debug(raw, "Expected valid identifier for local name:")
        );
        return None;
    }

    let name = tokens[next_index].clone();
    next_index += 1; // Пропустить имя

    if !expect_syntax(tokens, next_index, "=") {
        println!(
            "{}",
            tokens[next_index]
                .loc
                .debug(raw, "Expected = syntax after local name:")
        );
        return None;
    }

    next_index += 1; // Пропустить =

    let res = parse_expression(raw, tokens, next_index);
    if res.is_none() {
        println!(
            "{}",
            tokens[next_index]
                .loc
                .debug(raw, "Expected valid expression in local declaration:")
        );
        return None;
    }

    let (expr, next_next_index) = res.unwrap();
    next_index = next_next_index;

    if !expect_syntax(tokens, next_index, ";") {
        println!(
            "{}",
            tokens[next_index]
                .loc
                .debug(raw, "Expected semicolon in return statement:")
        );
        return None;
    }

    next_index += 1; // Пропустить точку с запятой

    Some((
        Statement::Local(Local {
            name,
            expression: expr,
        }),
        next_index,
    ))
}

▍Инструкции if

В этой реализации Lua конструкция elseif не поддерживается. Поэтому парсинг инструкции if заключается в простой проверке того, чтобы после ключевого слова if шла бы проверка некоего условия. Затем выполняется проверка на наличие ключевого слова else, а потом обрабатывается тело инструкции if (список выражений). В конце обрабатывается ключевое слово end.

fn parse_if(raw: &[char], tokens: &[Token], index: usize) -> Option<(Statement, usize)> {
    if !expect_keyword(tokens, index, "if") {
        return None;
    }

    let mut next_index = index + 1; // Пропустить if
    let res = parse_expression(raw, tokens, next_index);
    if res.is_none() {
        println!(
            "{}",
            tokens[next_index]
                .loc
                .debug(raw, "Expected valid expression for if test:")
        );
        return None;
    }

    let (test, next_next_index) = res.unwrap();
    next_index = next_next_index;

    if !expect_keyword(tokens, next_index, "then") {
        return None;
    }

    next_index += 1; // Пропустить then

    let mut statements: Vec<Statement> = vec![];
    while !expect_keyword(tokens, next_index, "end") {
        let res = parse_statement(raw, tokens, next_index);
        if let Some((stmt, next_next_index)) = res {
            next_index = next_next_index;
            statements.push(stmt);
        } else {
            println!(
                "{}",
                tokens[next_index]
                    .loc
                    .debug(raw, "Expected valid statement in if body:")
            );
            return None;
        }
    }

    next_index += 1; // Пропустить end

    Some((
        Statement::If(If {
            test,
            body: statements,
        }),
        next_index,
    ))
}

Работа над системой парсинга на этом окончена.

Компиляция кода для самодельной виртуальной машины

Наша виртуальная машина полностью основана на стеке, за исключением того, что тут используется указатель стека и счётчик команд.

Принятое здесь соглашение о вызовах заключается в том, что вызывающая сторона помещает в стек аргументы, а затем — указатель кадра и счётчик команд. После этого в стек помещают количество аргументов (для целей очистки памяти). Далее — осуществляется изменение счётчика команд и указателя кадра. После этого вызывающая сторона выделяет место в стеке для аргументов и объявлений локальных переменных, сделанных в функции.

Для упрощения применения механизмов адресации объявление функции, как только осуществляется переход к нему, копирует аргументы из места, предшествующего указателю кадра в место, находящееся перед ним (знаю, что выглядит это довольно-таки глупо).

Виртуальная машина поддерживает операции сложения и вычитания, операцию «меньше, чем», а так же — безусловный переход, переход при ненулевом значении, возврат, вызов. Она будет поддерживать немного больше специфических инструкций по работе с памятью для загрузки литералов и идентификаторов, а так же — для управления аргументами.

Я поясню неочевидные вещи по мере реализации соответствующих инструкций.

use crate::parse::*;
use std::collections::HashMap;

#[derive(Debug)]
enum Instruction {
    DupPlusFP(i32),
    MoveMinusFP(usize, i32),
    MovePlusFP(usize),
    Store(i32),
    Return,
    JumpIfNotZero(String),
    Jump(String),
    Call(String, usize),
    Add,
    Subtract,
    LessThan,
}

Результатом компиляции будет экземпляр Program. Он будет содержать символьную информацию и инструкции, которые планируется выполнить.

#[derive(Debug)]
struct Symbol {
    location: i32,
    narguments: usize,
    nlocals: usize,
}

#[derive(Debug)]
pub struct Program {
    syms: HashMap<String, Symbol>,
    instructions: Vec<Instruction>,
}

В компиляции нет ничего особенного. Она, как и парсинг, заключается в вызове вспомогательной функции compile_statement для каждой инструкции из AST.

pub fn compile(raw: &[char], ast: Ast) -> Program {
    let mut locals: HashMap<String, i32> = HashMap::new();
    let mut pgrm = Program {
        syms: HashMap::new(),
        instructions: Vec::new(),
    };
    for stmt in ast {
        compile_statement(&mut pgrm, raw, &mut locals, stmt);
    }

    pgrm
}

Функция compile_statement, кроме того, прибегает к дополнительным вспомогательным функциям для обработки инструкций разных видов.

fn compile_statement(
    pgrm: &mut Program,
    raw: &Vec<char>,
    locals: &mut HashMap<String, i32>,
    stmt: Statement,
) {
    match stmt {
        Statement::FunctionDeclaration(fd) => compile_declaration(pgrm, raw, locals, fd),
        Statement::Return(r) => compile_return(pgrm, raw, locals, r),
        Statement::If(if_) => compile_if(pgrm, raw, locals, if_),
        Statement::Local(loc) => compile_local(pgrm, raw, locals, loc),
        Statement::Expression(e) => compile_expression(pgrm, raw, locals, e),
    }
}

▍Объявления функций

Для начала разберёмся с самым сложным — с объявлениями функций. Их окружают защитные механизмы, работающие без каких-либо условий, поэтому мы можем начинать их выполнение с нулевой инструкции верхнего уровня. Мы можем сделать так, чтобы вычислялись бы только инструкции, не являющиеся объявлениями функций.

fn compile_declaration(
    pgrm: &mut Program,
    raw: &[char],
    _: &mut HashMap<String, i32>,
    fd: FunctionDeclaration,
) {
    // Перейти к концу функции для защиты конструкций верхнего уровня
    let done_label = format!("function_done_{}", pgrm.instructions.len());
    pgrm.instructions
        .push(Instruction::Jump(done_label.clone()));

Далее — мы реализуем ещё одно ограничение/упрощение, заключающееся в том, что локальные переменные доступны только в области видимости текущей функции.

При обработке параметров мы копируем каждый из них в стек, размещая перед указателем кадра. Это позволяет обойти ограничения системы адресации нашей виртуальной машины.

    let mut new_locals = HashMap::<String, i32>::new();

    let function_index = pgrm.instructions.len() as i32;
    let narguments = fd.parameters.len();
    for (i, param) in fd.parameters.iter().enumerate() {
        pgrm.instructions.push(Instruction::MoveMinusFP(
            i,
            narguments as i32 - (i as i32 + 1),
        ));
        new_locals.insert(param.value.clone(), i as i32);
    }

После этого компилируем тело функции.

    for stmt in fd.body {
        compile_statement(pgrm, raw, &mut new_locals, stmt);
    }

Теперь, когда тело функции скомпилировано, нам известно общее количество локальных переменных. Это позволяет нам правильно заполнить таблицу символов. Значение поля location уже задано, так как это — то место, где находится инструкция, расположенная в самом начале функции.

    pgrm.syms.insert(
        fd.name.value,
        Symbol {
            location: function_index as i32,
            narguments,
            nlocals: new_locals.keys().len(),
        },
    );

И мы, наконец, добавляем символ, связанный с меткой, указывающей на завершение функции. Это, опять же, позволяет пропустить объявление функции при вычислении значений инструкций от 0 до N.

    pgrm.syms.insert(
        done_label,
        Symbol {
            location: pgrm.instructions.len() as i32,
            narguments: 0,
            nlocals: 0,
        },
    );
}

Как видите, не так уж всё и сложно. А то, что нам осталось сделать, будет ещё проще.

▍Объявления локальных переменных

Мы компилируем выражения для объявлений локальных переменных, после чего локальные имена сохраняются в таблице локальных имён, увязанной с текущим количеством локальных объявлений (включая аргументы). Это позволяет компилятору свести поиск токена identifier к использованию смещения относительно указателя кадра.

fn compile_local(
    pgrm: &mut Program,
    raw: &[char],
    locals: &mut HashMap<String, i32>,
    local: Local,
) {
    let index = locals.keys().len();
    locals.insert(local.name.value, index as i32);
    compile_expression(pgrm, raw, locals, local.expression);
    pgrm.instructions.push(Instruction::MovePlusFP(index));
}

И обратите внимание на то, что паттерн обработки инструкции заключается в вычислении выражения и в копировании того, что получилось, обратно, с использованием относительной позиции в стеке.

▍Литералы

Числовые литералы используют инструкцию store для помещения чисел в стек. Литералы-идентификаторы копируются из своих позиций, вычисляемых относительно указателя кадра, в верхнюю часть стека.

fn compile_literal(
    pgrm: &mut Program,
    _: &[char],
    locals: &mut HashMap<String, i32>,
    lit: Literal,
) {
    match lit {
        Literal::Number(i) => {
            let n = i.value.parse::<i32>().unwrap();
            pgrm.instructions.push(Instruction::Store(n));
        }
        Literal::Identifier(ident) => {
            pgrm.instructions
                .push(Instruction::DupPlusFP(locals[&ident.value]));
        }
    }
}

▍Вызовы функций

Тут всё очень просто: компилируем все аргументы и выполняем инструкцию вызова.

fn compile_function_call(
    pgrm: &mut Program,
    raw: &Vec<char>,
    locals: &mut HashMap<String, i32>,
    fc: FunctionCall,
) {
    let len = fc.arguments.len();
    for arg in fc.arguments {
        compile_expression(pgrm, raw, locals, arg);
    }

    pgrm.instructions
        .push(Instruction::Call(fc.name.value, len));
}

▍Операции с двумя операндами

Операции с двумя операндами компилируются так: сначала — их левая часть, потом — правая, а после этого, на основании используемого в них оператора, выполняется соответствующая инструкция. Все операторы являются встроенными. Они работают с двумя верхними элементами стека.

fn compile_binary_operation(
    pgrm: &mut Program,
    raw: &[char],
    locals: &mut HashMap<String, i32>,
    bop: BinaryOperation,
) {
    compile_expression(pgrm, raw, locals, *bop.left);
    compile_expression(pgrm, raw, locals, *bop.right);
    match bop.operator.value.as_str() {
        "+" => {
            pgrm.instructions.push(Instruction::Add);
        }
        "-" => {
            pgrm.instructions.push(Instruction::Subtract);
        }

        "<" => {
            pgrm.instructions.push(Instruction::LessThan);
        }
        _ => panic!(
            "{}",
            bop.operator
                .loc
                .debug(raw, "Unable to compile binary operation:")
        ),
    }
}

▍Выражения

При компиляции выражений соответствующие задачи перенаправляются вспомогательным функциям компиляции. Выбор функции зависит от типа выражения. Эти функции мы уже написали.

fn compile_expression(
    pgrm: &mut Program,
    raw: &[char],
    locals: &mut HashMap<String, i32>,
    exp: Expression,
) {
    match exp {
        Expression::BinaryOperation(bop) => {
            compile_binary_operation(pgrm, raw, locals, bop);
        }
        Expression::FunctionCall(fc) => {
            compile_function_call(pgrm, raw, locals, fc);
        }
        Expression::Literal(lit) => {
            compile_literal(pgrm, raw, locals, lit);
        }
    }
}

▍Инструкции if

Для начала мы компилируем условие, а затем, если получен ненулевой результат, переходим к инструкциям, идущим после if.

fn compile_if(pgrm: &mut Program, raw: &[char], locals: &mut HashMap<String, i32>, if_: If) {
    compile_expression(pgrm, raw, locals, if_.test);
    let done_label = format!("if_else_{}", pgrm.instructions.len());
    pgrm.instructions
        .push(Instruction::JumpIfNotZero(done_label.clone()));

Потом компилируем тело if.

    for stmt in if_.body {
        compile_statement(pgrm, raw, locals, stmt);
    }

И наконец — обеспечиваем размещение символа done в правильном месте после if.

    pgrm.syms.insert(
        done_label,
        Symbol {
            location: pgrm.instructions.len() as i32 - 1,
            nlocals: 0,
            narguments: 0,
        },
    );
}

▍Инструкции return

Последний тип инструкций, который нам осталось обработать, представлен инструкцией return. При обработке таких инструкций мы просто компилируем возвращаемое выражение и выполняем инструкцию return.

fn compile_return(
    pgrm: &mut Program,
    raw: &[char],
    locals: &mut HashMap<String, i32>,
    ret: Return,
) {
    compile_expression(pgrm, raw, locals, ret.expression);
    pgrm.instructions.push(Instruction::Return);
}

Компилятор готов! А теперь — решим самую хитрую задачу. Работа над фрагментом кода, который я опишу ниже, заняла у меня несколько часов, наполненных вознёй с отладчиком и доработкой кода.

Виртуальная машина

Итак, нам на руку то, что тут имеется всего два регистра, счётчик команд и указатель кадра. Имеется тут и стек данных. Указатель кадра указывает на место в стеке данных, которое функции могут использовать как начальную позицию хранения своих локальных сущностей.

Выполнение инструкций начинается с нулевой инструкции и продолжается до последней инструкции.

pub fn eval(pgrm: Program) {
    let mut pc: i32 = 0;
    let mut fp: i32 = 0;
    let mut data: Vec<i32> = vec![];

    while pc < pgrm.instructions.len() as i32 {
        match &pgrm.instructions[pc as usize] {

Каждая инструкция ответственна за инкрементирование счётчика команд или за организацию перехода.

▍Сложение, вычитание, операция «меньше, чем»

Проще всего реализовать выполнение математических операторов. Мы просто вытаскиваем то, что нужно, из стека данных, выполняем операцию и сохраняем результат.

            Instruction::Add => {
                let right = data.pop().unwrap();
                let left = data.pop().unwrap();
                data.push(left + right);
                pc += 1;
            }
            Instruction::Subtract => {
                let right = data.pop().unwrap();
                let left = data.pop().unwrap();
                data.push(left - right);
                pc += 1;
            }
            Instruction::LessThan => {
                let right = data.pop().unwrap();
                let left = data.pop().unwrap();
                data.push(if left < right { 1 } else { 0 });
                pc += 1;
            }

Инструкция store тоже никаких сложностей не вызывает. Она просто помещает числовой литерал в стек.

            Instruction::Store(n) => {
                data.push(*n);
                pc += 1;
            }

▍Различные переходы

Реализовать переходы тоже несложно. Надо просто взять сведения о месте, куда надо перейти, и соответстветствующим образом изменить счётчик команд. Если же речь идёт об условном переходе — сначала надо проверить условие.

            Instruction::JumpIfNotZero(label) => {
                let top = data.pop().unwrap();
                if top == 0 {
                    pc = pgrm.syms[label].location;
                }
                pc += 1;
            }
            Instruction::Jump(label) => {
                pc = pgrm.syms[label].location;
            }

▍Загрузка данных из переменных

Инструкция MovePlusFP копирует значение из стека (смещение по отношению к указателю кадра) в верхнюю часть стека. Это делается для организации обращений к аргументам и к локальным переменным.

            Instruction::MovePlusFP(i) => {
                let val = data.pop().unwrap();
                let index = fp as usize + *i;
                // Рассчитано на локальные переменные верхнего уровня
                while index >= data.len() {
                    data.push(0);
                }
                data[index] = val;
                pc += 1;
            }

▍Хранение локальных переменных

Инструкция DupPlusFP используется функцией compile_locals для сохранения локальных переменных в стеке после компиляции. Позиция их хранения вычисляется относительно указателя кадра.

            Instruction::DupPlusFP(i) => {
                data.push(data[(fp + i) as usize]);
                pc += 1;
            }

▍Дублирование аргументов

Инструкция MoveMinusFP — это, так сказать, «хак», нужный для обхода ограничений адресации нашей минималистичной виртуальной машины. Она копирует аргументы из места, находящегося за указателем кадра, в место, находящееся перед ним.

            Instruction::MoveMinusFP(local_offset, fp_offset) => {
                data[fp as usize + local_offset] = data[(fp - (fp_offset + 4)) as usize];
                pc += 1;
            }

Нам осталось разобраться лишь с двумя инструкциями: call и return.

▍Инструкция call

Инструкция call по-особенному обрабатывает встроенные функции (единственная такая функция — print).

            Instruction::Call(label, narguments) => {
                // Обработка встроенных функций
                if label == "print" {
                    for _ in 0..*narguments {
                        print!("{}", data.pop().unwrap());
                        print!(" ");
                    }
                    println!();
                    pc += 1;
                    continue;
                }

В противном случае она помещает в стек текущий указатель кадра, счётчик команд, и, наконец — количество аргументов (не локальных переменных). Она, таким образом, обеспечивает их сохранность. После этого call задаёт новые значения счётчику команд и указателю кадра, а потом, после нового указателя кадра, выделяет место для локальных переменных и аргументов.

                data.push(fp);
                data.push(pc + 1);
                data.push(pgrm.syms[label].narguments as i32);
                pc = pgrm.syms[label].location;
                fp = data.len() as i32;

                // Выделить место для всех аргументов и локальных переменных
                let mut nlocals = pgrm.syms[label].nlocals;
                while nlocals > 0 {
                    data.push(0);
                    nlocals -= 1;
                }
            }

▍Инструкции return

Инструкция return берёт возвращаемое значение из стека. Потом она извлекает оттуда все локальные переменные и аргументы. Далее — она восстанавливает счётчик команд и указатель кадра, а так же — берёт из стека аргументы, находящиеся перед указателем кадра. В итоге она помещает возвращаемое значение обратно в стек.

            Instruction::Return => {
                let ret = data.pop().unwrap();

                // Очистить локальный стек
                while fp < data.len() as i32 {
                    data.pop();
                }

                // Восстановить счётчик команд и указатель стека
                let mut narguments = data.pop().unwrap();
                pc = data.pop().unwrap();
                fp = data.pop().unwrap();

                // Очистить аргументы
                while narguments > 0 {
                    data.pop();
                    narguments -= 1;
                }

                // Добавить в стек возвращаемое значение
                data.push(ret);
            }

Конечно, эта реализация виртуальной машины будет гораздо эффективнее, если вместо того, чтобы, в буквальном смысле, помещать значения в стек и извлекать их из него, мы бы просто инкрементировали или декрементировали указатель стека.

Вот и всё! Мы завершили работу над простейшими парсером, компилятором и виртуальной машиной, которые рассчитаны на обработку конструкций, являющихся подмножеством Lua. Странноватая система у нас получилась? Да. Простая? Пожалуй, что так. Рабочая? Такое ощущение, что вполне рабочая!

Итоги

Итак, написав менее чем 1200 строк Rust-кода, мы создали нечто такое, что умеет выполнять вполне приличные программы, написанные на Lua. Попробуем запустить следующую программу в нашей системе и в Lua 5.4.3 (это — не LuaJIT). Что у нас получится?

$ cargo build --release
$ cat test/fib.lua
function fib(n)
   if n < 2 then
      return n;
   end

   local n1 = fib(n-1);
   local n2 = fib(n-2);
   return n1 + n2;
end

print(fib(30));
$ time ./target/release/lust test/fib.lua
832040
./target/release/lust test/fib.lua  0.29s user 0.00s system 99% cpu 0.293 total
$ time lua test/fib.lua
832040
lua test/fib.lua  0.06s user 0.00s system 99% cpu 0.063 total

Оказалось, что наша реализация Lua медленнее стандартной. А значит — пришло время заняться профилированием программы и, возможно, доработкой фрагментов кода, о неэффективности которых мы говорили выше.

Занимались ли вы созданием собственных парсеров, компиляторов или виртуальных машин?