[Перевод] Минимальная реализация 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 = env::args().collect();
let contents = fs::read_to_string(&args[1]).expect("Could not read file");
let raw: Vec = 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>(&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, String> {
let mut loc = Location {
col: 0,
index: 0,
line: 0,
};
let size = s.len();
let mut tokens: Vec = 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, 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;
В остальном определение дерева не содержит практически ничего особенного.
#[derive(Debug)]
pub enum Literal {
Identifier(Token),
Number(Token),
}
#[derive(Debug)]
pub struct FunctionCall {
pub name: Token,
pub arguments: Vec,
}
#[derive(Debug)]
pub struct BinaryOperation {
pub operator: Token,
pub left: Box,
pub right: Box,
}
#[derive(Debug)]
pub enum Expression {
FunctionCall(FunctionCall),
BinaryOperation(BinaryOperation),
Literal(Literal),
}
#[derive(Debug)]
pub struct FunctionDeclaration {
pub name: Token,
pub parameters: Vec,
pub body: Vec,
}
#[derive(Debug)]
pub struct If {
pub test: Expression,
pub body: Vec,
}
#[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) -> Result {
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 = 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 = 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 = 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 = 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,
instructions: Vec,
}
В компиляции нет ничего особенного. Она, как и парсинг, заключается в вызове вспомогательной функции compile_statement для каждой инструкции из AST.
pub fn compile(raw: &[char], ast: Ast) -> Program {
let mut locals: HashMap = 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,
locals: &mut HashMap,
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,
fd: FunctionDeclaration,
) {
// Перейти к концу функции для защиты конструкций верхнего уровня
let done_label = format!("function_done_{}", pgrm.instructions.len());
pgrm.instructions
.push(Instruction::Jump(done_label.clone()));
Далее — мы реализуем ещё одно ограничение/упрощение, заключающееся в том, что локальные переменные доступны только в области видимости текущей функции.
При обработке параметров мы копируем каждый из них в стек, размещая перед указателем кадра. Это позволяет обойти ограничения системы адресации нашей виртуальной машины.
let mut new_locals = HashMap::::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,
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,
lit: Literal,
) {
match lit {
Literal::Number(i) => {
let n = i.value.parse::().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,
locals: &mut HashMap,
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,
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,
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, 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,
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 = 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 тоже никаких сложностей не вызывает. Она
