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

Создание домен‑специфических языков — это интересная и сложная задача. В этой статье рассмотрим, как с помощью 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(),
    }
}

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

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

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