Привет, Хабр!
Сегодня мы рассмотрим одну из тем систем компиляции — генерацию абстрактного синтаксического дерева или просто 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».
ссылка на оригинал статьи https://habr.com/ru/articles/844120/
Добавить комментарий