Минимальная реализация 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 медленнее стандартной. А значит — пришло время заняться профилированием программы и, возможно, доработкой фрагментов кода, о неэффективности которых мы говорили выше.

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