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

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

Процесс генерации AST

Итак, абстрактное синтаксическое дерево — это структура данных, которая описывает синтаксическую структуру исходного кода в виде дерева. Узлы дерева представляют синтаксические конструкции: операторы, переменные, выражения и т.д.

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

Определение структуры AST в Rust

Для начала нужно создать структуру данных, которая будет представлять узлы дерева. В Rust удобнее всего использовать enum для представления разных типов узлов дерева:

#[derive(Debug, Clone)]
enum Expr {
    Number(i32),
    Variable(String),
    Add(Box<Expr>, Box<Expr>),
    Subtract(Box<Expr>, Box<Expr>),
    Multiply(Box<Expr>, Box<Expr>),
    Divide(Box<Expr>, Box<Expr>),
    FunctionCall(String, Vec<Expr>),
}

Здесь Expr — это перечисление, которое описывает узлы дерева для выражений. Используем Box<Expr> для рекурсивных структур, таких как арифметические операции, чтобы избежать проблем с определением размера структур на этапе компиляции. Почему используется Box? В Rust для рекурсивных структур размер типа должен быть известен на этапе компиляции. Box указывает на данные в куче и имеет фиксированный размер.

Создание простого парсера

Теперь займемся созданием простого парсера, который будет обрабатывать строки с арифметическими выражениями, переменными и вызовами функций и преобразовывать их в наше дерево. Для этого воспользуемся библиотекой nom. Это мощная библиотека парсер-комбинаторов, которая позволяет строить парсеры на основе небольших компонентов. Парсер-комбинаторы — это функции, которые принимают строку на вход и возвращают результат парсинга или ошибку. Их можно комбинировать для построения сложных парсеров.

Добавим в проект зависимость:

[dependencies]
nom = "7.0"

Теперь начнем писать парсер:

use nom::{
    IResult,
    character::complete::{alpha1, digit1, char},
    branch::alt,
    combinator::map_res,
    sequence::tuple,
    multi::fold_many0,
    multi::separated_list0,
    bytes::complete::tag,
};

fn parse_number(input: &str) -> IResult<&str, Expr> {
    let (input, num) = map_res(digit1, |s: &str| s.parse::<i32>())(input)?;
    Ok((input, Expr::Number(num)))
}

fn parse_variable(input: &str) -> IResult<&str, Expr> {
    let (input, var) = alpha1(input)?; // Переменные начинаются с букв
    Ok((input, Expr::Variable(var.to_string())))
}

fn parse_function_call(input: &str) -> IResult<&str, Expr> {
    let (input, (func_name, _, args, _)) = tuple((
        alpha1,          // имя функции
        char('('),       // открывающая скобка
        separated_list0(char(','), parse_expr), // аргументы функции
        char(')')        // закрывающая скобка
    ))(input)?;
    Ok((input, Expr::FunctionCall(func_name.to_string(), args)))
}

fn parse_factor(input: &str) -> IResult<&str, Expr> {
    alt((
        parse_number,
        parse_variable,
        parse_function_call,
    ))(input)
}

fn parse_term(input: &str) -> IResult<&str, Expr> {
    let (input, initial) = parse_factor(input)?;

    fold_many0(
        tuple((alt((tag("*"), tag("/"))), parse_factor)),
        initial,
        |acc, (op, val)| match op {
            "*" => Expr::Multiply(Box::new(acc), Box::new(val)),
            "/" => Expr::Divide(Box::new(acc), Box::new(val)),
            _ => unreachable!(),
        },
    )(input)
}

fn parse_expr(input: &str) -> IResult<&str, Expr> {
    let (input, initial) = parse_term(input)?;

    fold_many0(
        tuple((alt((tag("+"), tag("-"))), parse_term)),
        initial,
        |acc, (op, val)| match op {
            "+" => Expr::Add(Box::new(acc), Box::new(val)),
            "-" => Expr::Subtract(Box::new(acc), Box::new(val)),
            _ => unreachable!(),
        },
    )(input)
}

Что мы сделали:

• Добавили parse_variable для парсинга переменных, состоящих из букв.

• Добавили parse_function_call, чтобы парсить вызовы функций с аргументами.

• Функция parse_factor теперь может парсить числа, переменные и вызовы функций.

Парсинг всегда может завершиться ошибкой, особенно когда на вход подаются некорректные данные, поэтому добави обработку ошибок:

fn parse_expr_with_errors(input: &str) -> Result<Expr, String> {
    match parse_expr(input) {
        Ok((_, expr)) => Ok(expr),
        Err(nom::Err::Error(e)) | Err(nom::Err::Failure(e)) => Err(format!("Parsing error: {:?}", e)),
        Err(nom::Err::Incomplete(_)) => Err("Input is incomplete".to_string()),
    }
}

Теперь парсер обрабатывает ошибки и выводит их пользователю.

Визуализация AST

Теперь визуализируем AST, чтобы наглядно показать структуру дерева. Уже реализовали функцию pretty_print, которая выводит дерево на экран:

impl Expr {
    fn pretty_print(&self, indent: usize) {
        let padding = " ".repeat(indent);
        match self {
            Expr::Number(n) => println!("{}Number({})", padding, n),
            Expr::Variable(v) => println!("{}Variable({})", padding, v),
            Expr::FunctionCall(name, args) => {
                println!("{}FunctionCall: {}", padding, name);
                for arg in args {
                    arg.pretty_print(indent + 2);
                }
            }
            Expr::Add(lhs, rhs) => {
                println!("{}Add:", padding);
                lhs.pretty_print(indent + 2);
                rhs.pretty_print(indent + 2);
            }
            Expr::Subtract(lhs, rhs) => {
                println!("{}Subtract:", padding);
                lhs.pretty_print(indent + 2);
                rhs.pretty_print(indent + 2);
            }
            Expr::Multiply(lhs, rhs) => {
                println!("{}Multiply:", padding);
                lhs.pretty_print(indent + 2);
                rhs.pretty_print(indent + 2);
            }
            Expr::Divide(lhs, rhs) => {
                println!("{}Divide:", padding);
                lhs.pretty_print(indent + 2);
                rhs.pretty_print(indent + 2);
            }
        }
    }
}

Вывод:

Add:
  Number(5)
  Multiply:
    Variable(x)
    Number(3)

Этот вывод демонстрирует следующее:

• Корневой узел — это операция сложения Add.

• Левый операнд — это число 5 Number(5), оно отображается с отступом в 2 пробела.

• Правый операнд — это операция умножения Multiply, которая в свою очередь состоит из переменной x и числа 3.

  • Переменная x выводится как Variable(x) с отступом в 4 пробела.

  • Число 3 выводится как Number(3) с тем же отступом в 4 пробела, так как это правая часть операции умножения.

Этот вывод показывает структуру AST, соответствующую выражению 5 + (x * 3).

Оптимизация: свертка констант и устранение мёртвого кода

На этапе компиляции можно выполнять оптимизации, такие как свёртка констант и устранение мёртвого кода:

impl Expr {
    fn optimize(&self) -> Expr {
        match self {
            Expr::Add(lhs, rhs) => {
                let left = lhs.optimize();
                let right = rhs.optimize();
                if let Expr::Number(l) = left {
                    if let Expr::Number(r) = right {
                        return Expr::Number(l + r); // Оптимизация констант
                    }
                }
                if let Expr::Number(0) = right {
                    return left; // x + 0 => x
                }
                if let Expr::Number(0) = left {
                    return right; // 0 + x => x
                }
                Expr::Add(Box::new(left

), Box::new(right))
            }
            Expr::Multiply(lhs, rhs) => {
                let left = lhs.optimize();
                let right = rhs.optimize();
                if let Expr::Number(l) = left {
                    if let Expr::Number(r) = right {
                        return Expr::Number(l * r); // Оптимизация констант
                    }
                }
                Expr::Multiply(Box::new(left), Box::new(right))
            }
            Expr::FunctionCall(_, _) => self.clone(), // В будущем можно добавить интерпретацию вызовов функций
            _ => self.clone(),
        }
    }
}

Функция optimize автоматически упрощает выражения и вычисляет константы на этапе компиляции.

Заключение

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

Archi против всех: как бесплатный архитектурный инструмент покоряет сердца миллионов? Обсудим на открытом уроке 23 сентября. На уроке мы:

• Рассмотрим критерии для выбора архитектурных инструментов в компании

• Сделаем обзор ведущих мировых и российских инструментов

• Затронем основные фичи бесплатного инструмента Archi

• Смоделируем простой кейс

Записаться на урок можно настранице курса «Archimate. Basic».