Абстрактное синтаксическое дерево
Абстрактное синтаксическое дерево (АСД) – это представление исходного кода программы, написанного на формальном языке, в виде структуры данных дерева.
В разработанном проекте представление программы в виде АСД используется на стадиях синтаксического, семантического и оптимизирующего анализа. Для синтаксического анализатора структура в виде дерева является выходом, а для семантического и оптимизирующего – как входом, так и выходом.
Использование АСД для представления структуры программы в компиляторах дает ряд преимуществ, полезных для следующих стадий компиляции:
АСД содержит дополнительную полезную информацию о программе, например, количество вызовов определенной функции, номер строки, в которой допущена ошибка;
В отличие от исходного кода, АСД не содержит таких несущественных частей, как знаков пунктуации, отступов;
АСД включает в себя полную информацию о программе в удобном для представления и обработки формате.
Программная реализация
В представленной реализации синтаксическое дерево разбора представляется как множество отдельных узлов, каждый из которых хранит ссылки на родительский узел и на все дочерние (в виде двусвязного списка). Каждый из узлов хранит, во-первых, свой тип (или род содержимого) и значащее содержимое. В каком-то смысле структуру узлов можно назвать похожей на структуру описанных в п. 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
– таблица функций