Создание DSL на Rust
Привет, Хабр!
Создание домен‑специфических языков — это интересная и сложная задача. В этой статье рассмотрим, как с помощью Rust создать интерпретатор и компилятор для DSL на основе абстрактного синтаксического дерева.
Начнем с создания абстрактного синтаксического дерева, которое будет основой для всех дальнейших операций. В контексте создания DSL, AST представляет собой дерево, в котором каждый узел соответствует элементу языка.
pub enum Expr {
Literal(i32),
Variable(String),
Binary {
op: BinaryOp,
lhs: Box,
rhs: Box,
},
FunctionCall {
name: String,
args: Vec,
},
}
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::().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 = args.iter().map(|arg| arg.evaluate(context)).collect();
func(&arg_vals)
},
}
}
}
struct Context {
variables: HashMap,
functions: HashMap 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 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) {
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 преобразуется в одну или несколько инструкций, которые добавляются в конечный список команд.
При создании интерпретатора и компилятора важно учитывать производительность.
Свертка констант: вычисление выражений, которые содержат только константы, на этапе компиляции, чтобы уменьшить нагрузку во время выполнения.
Вывод типов: использование системы типов для оптимизации вызовов функций и доступа к переменным.
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(),
}
}Здесь компилятор свертывает константные выражения в единичные значения, уменьшая количество вычислений во время выполнения.
Всем вдохновения и поменьше багов!
Подробнее про архитектуру приложений вы можете узнать в рамках онлайн-курсов от практикующих экспертов отрасли. Подробности в каталоге.
