Создание DSL на Rust

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

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

Начнем с создания абстрактного синтаксического дерева, которое будет основой для всех дальнейших операций. В контексте создания DSL, AST представляет собой дерево, в котором каждый узел соответствует элементу языка.

pub enum Expr {     Literal(i32),     Variable(String),     Binary {         op: BinaryOp,         lhs: Box<Expr>,         rhs: Box<Expr>,     },     FunctionCall {         name: String,         args: Vec<Expr>,     }, }  pub enum BinaryOp {     Add,     Subtract,     Multiply,     Divide, }

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

Чтобы создать AST из исходного кода, необходимо разработать парсер. В Rust это можно сделать с помощью nom или pest:

fn parse_literal(input: &str) -> IResult<&str, Expr> {     map(digit1, |s: &str| {         Expr::Literal(s.parse::<i32>().unwrap())     })(input) }  fn parse_variable(input: &str) -> IResult<&str, Expr> {     map(alpha1, |s: &str| {         Expr::Variable(s.to_string())     })(input) }  fn parse_binary_expr(input: &str) -> IResult<&str, Expr> {     let (input, left) = parse_atom(input)?;     let (input, op) = parse_operator(input)?;     let (input, right) = parse_atom(input)?;     Ok((input, Expr::Binary {         op,         lhs: Box::new(left),         rhs: Box::new(right),     })) } 

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

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

impl Expr {     pub fn evaluate(&self, context: &mut Context) -> i32 {         match self {             Expr::Literal(val) => *val,             Expr::Variable(name) => context.get_variable(name),             Expr::Binary { op, lhs, rhs } => {                 let lhs_val = lhs.evaluate(context);                 let rhs_val = rhs.evaluate(context);                 match op {                     BinaryOp::Add => lhs_val + rhs_val,                     BinaryOp::Subtract => lhs_val - rhs_val,                     BinaryOp::Multiply => lhs_val * rhs_val,                     BinaryOp::Divide => lhs_val / rhs_val,                 }             },             Expr::FunctionCall { name, args } => {                 let func = context.get_function(name);                 let arg_vals: Vec<i32> = args.iter().map(|arg| arg.evaluate(context)).collect();                 func(&arg_vals)             },         }     } }  struct Context {     variables: HashMap<String, i32>,     functions: HashMap<String, Box<dyn Fn(&[i32]) -> i32>>, }  impl Context {     fn get_variable(&self, name: &str) -> i32 {         *self.variables.get(name).expect("Variable not found")     }      fn get_function(&self, name: &str) -> Box<dyn Fn(&[i32]) -> i32> {         self.functions.get(name).expect("Function not found").clone()     } }

Реализовали простой интерпретатор, который поддерживает переменные и вызовы функций. Контекст хранит переменные и функции, доступные во время выполнения.

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

Компилиция на структуре AST:

enum Instruction {     LoadLiteral(i32),     LoadVariable(String),     Add,     Subtract,     Multiply,     Divide,     CallFunction(String), }  fn compile_expr(expr: &Expr, bytecode: &mut Vec<Instruction>) {     match expr {         Expr::Literal(val) => bytecode.push(Instruction::LoadLiteral(*val)),         Expr::Variable(name) => bytecode.push(Instruction::LoadVariable(name.clone())),         Expr::Binary { op, lhs, rhs } => {             compile_expr(lhs, bytecode);             compile_expr(rhs, bytecode);             bytecode.push(match op {                 BinaryOp::Add => Instruction::Add,                 BinaryOp::Subtract => Instruction::Subtract,                 BinaryOp::Multiply => Instruction::Multiply,                 BinaryOp::Divide => Instruction::Divide,             });         },         Expr::FunctionCall { name, args } => {             for arg in args {                 compile_expr(arg, bytecode);             }             bytecode.push(Instruction::CallFunction(name.clone()));         },     } }

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

При создании интерпретатора и компилятора важно учитывать производительность.

1. Свертка констант: вычисление выражений, которые содержат только константы, на этапе компиляции, чтобы уменьшить нагрузку во время выполнения.

2. Вывод типов: использование системы типов для оптимизации вызовов функций и доступа к переменным.

3. JIT‑компиляция: использование Just‑In‑Time компиляции для генерации машинного кода.

Пример сверстки констант:

fn optimize_expr(expr: &Expr) -> Expr {     match expr {         Expr::Binary { op, lhs, rhs } => {             let lhs = optimize_expr(lhs);             let rhs = optimize_expr(rhs);             if let (Expr::Literal(lhs_val), Expr::Literal(rhs_val)) = (&lhs, &rhs) {                 return Expr::Literal(match op {                     BinaryOp::Add => lhs_val + rhs_val,                     BinaryOp::Subtract => lhs_val - rhs_val,                     BinaryOp::Multiply => lhs_val * rhs_val,                     BinaryOp::Divide => lhs_val / rhs_val,                 });             }             Expr::Binary { op: *op, lhs: Box::new(lhs), rhs: Box::new(rhs) }         },         _ => expr.clone(),     } }

Здесь компилятор свертывает константные выражения в единичные значения, уменьшая количество вычислений во время выполнения.

Всем вдохновения и поменьше багов!

Подробнее про архитектуру приложений вы можете узнать в рамках онлайн-курсов от практикующих экспертов отрасли. Подробности в каталоге.