Абстрактное синтаксическое дерево

Абстрактное синтаксическое дерево (АСД) – это представление исходного кода программы, написанного на формальном языке, в виде структуры данных дерева.

В разработанном проекте представление программы в виде АСД используется на стадиях синтаксического, семантического и оптимизирующего анализа. Для синтаксического анализатора структура в виде дерева является выходом, а для семантического и оптимизирующего – как входом, так и выходом.

Использование АСД для представления структуры программы в компиляторах дает ряд преимуществ, полезных для следующих стадий компиляции:

  • АСД содержит дополнительную полезную информацию о программе, например, количество вызовов определенной функции, номер строки, в которой допущена ошибка;

  • В отличие от исходного кода, АСД не содержит таких несущественных частей, как знаков пунктуации, отступов;

  • АСД включает в себя полную информацию о программе в удобном для представления и обработки формате.

Программная реализация

В представленной реализации синтаксическое дерево разбора представляется как множество отдельных узлов, каждый из которых хранит ссылки на родительский узел и на все дочерние (в виде двусвязного списка). Каждый из узлов хранит, во-первых, свой тип (или род содержимого) и значащее содержимое. В каком-то смысле структуру узлов можно назвать похожей на структуру описанных в п. 4.1.1 токенов. Описательная часть объявления на языке C++ представлена ниже.

struct Node {
    using Ptr = std::shared_ptr<Node>;

    std::list<Ptr> children;
    Ptr parent;

    NodeType type;
    std::variant<long int, double, std::string, TypeId, BinaryOperation, UnaryOperation> value;
};

Для упрощения контроля памяти при реализации алгоритмов по работе с деревьями все узлы хранятся в виде «умных» указателей, доступных в стандартной библиотеке C++. Для удобства объявлен синоним типа для указателя Node::Ptr. Таким образом, каждый узел хранит:

  • двусвязный список std::list указателей на дочерние узлы children;

  • родительский узел parent;

  • тип (род содержимого) узла type как одно из значений некоторого перечисления NodeType;

  • значащее содержимое узла value как объединение типов std::variant.

Для наглядности на этапе синтаксического разбора дерево, характеризуемое своим корневым узлом, представлено классом SyntaxTree:

class SyntaxTree {
  public:
    Node::Ptr root;
    FunctionsTable functions;
};

Описание полей:

  • root – указатель на узел, определенный как корень дерева;

  • functions – таблица функций

Назад