Как стать автором
Поиск
Написать публикацию
Обновить
513.08
OTUS
Развиваем технологии, обучая их создателей

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

Уровень сложностиПростой
Время на прочтение4 мин
Количество просмотров3.5K

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

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

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


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

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

Теги:
Хабы:
Всего голосов 12: ↑8 и ↓4+9
Комментарии1

Публикации

Информация

Сайт
otus.ru
Дата регистрации
Дата основания
Численность
101–200 человек
Местоположение
Россия
Представитель
OTUS