Привет, Хабр!
Сегодня мы рассмотрим одну из тем систем компиляции — генерацию абстрактного синтаксического дерева или просто 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».