- Абстрактное синтаксическое дерево (AST) содержит связанные между собой экземпляры структур данных (узлов).
- При этом узлами AST можно представить все конструкции, допустимые в соответствующем языке программирования.
Допустим, программа состоит из последовательных инструкций. Каждая инструкция — это определение функции или вызов функции. Тогда структура AST может быть такой:
Program (struct)
-> std::vector<Statement*> statements
StatementKind (enum class)
-> Function
-> Call
Statement (struct)
-> StatementKind kind
Function : Statement (struct)
-> std::string name
-> std::vector<Statement*> body
Call : Statement (struct)
-> std::string name
-> Function* called
В этом случае, стадия синтаксического анализа, создающего начальное состояние AST, могла бы выглядеть так:
auto parser = make_unique<Parser>(lexer);
auto ast = parser.parseAST();
Кроме создания AST, на стадии синтаксического анализа при наличии в исходном коде ошибок надо
- сгенерировать сообщения об ошибках
- постараться восстановиться после ошибок
В языках, где точка с запятой или конец строки служат разделителями, компилятору проще восстановиться после ошибок: он может просто сообщить об ошибке, проигнорировать все символы до следующего разделителя и продолжить разбор.
Если язык разрешает разместить вызов функции до её определения, это легко обработать:
- распарсим весь файл, включая вызовы функций, без проверки имён функций
- после окончания разбора обойти дерево и найти все вызовы необъявленных функций
- подобные шаги постобработки дерева называются "процедурами семантической проверки"
Процедуры семантической проверки дополняют AST недостающими кросс-ссылками между ветвями дерева:
- ссылками от узла вызова функции к узлу её объявления
- ссылками от узла переменной в выражении к узлу объявления локальной переменной, глобальной переменной или параметра функции
- ссылками от объявления переменной к узлу пользовательского типа данных, использованному в объявлении
- при отсутствии обязательной ссылки создаётся новое сообщение об ошибке
- также семантический анализ проверяет соответствие типов в выражениях
После семантического анализа мы получаем одно из двух:
- либо неполное AST и список ошибок в программе
- либо завершённое AST, гарантированно представляющее правильно написанную программу
После этого можно генерировать трёхадресный код, а затем отдавать его оптимизатору и кодогенератору под конкретную аппаратную платформу:
- Обычно оптимизатор и платформо-зависимый кодогенератор объединяют в "бекенд компилятора"
- Задача фронтенда компилятора — создать AST и сгенерировать из него трёхадресный код для бекенда.
- Таким образом, лексический, синтаксический и семантический анализ вместе с генератором трёхадресного кода попадают во фронтенд.
Обычно AST обходится несколько раз уже после создания. Если AST очень велико, то для приемлемой скорости узлы дерева должны располагаться в соседних областях памяти.
- Это можно реализовать с помощью применения Memory Pool (или Object Pool) для размещения в памяти узлов дерева.
- Для простых языков и небольших файлов такой подход может оказаться преждевременной оптимизацией.
- в глубину слева направо
func visit(node):
actionBeforeVisit(node)
for child : node.children():
child.accept(this)
actionAfterVisit(node);
- в глубину справа налево
func visit(node):
actionBeforeVisit(node)
for child : reverse(node.children()):
child.accept(this)
actionAfterVisit(node);
- в ширину слева направо (лишний расход памяти)
func visit(node_list):
new_node_list = []
for node : node_list:
actionOnVisit(node)
for child : node.children():
new_node_list << child
visit(new_node_list)
- в ширину справа налево (лишний расход памяти)
- программы манипулируют данными с помощью операций.
- в процессе эволюции программы добавляются новые типы данных и новые операции
- новая операция должна работать с существующими типами данных
- новый тип данных совместим с существующими операциями
- по-настоящему расширяемый код не требует модификации существующих модулей
- модулем может считаться один файл, один класс, одна функция
- новое расширение попадает в отдельный модуль
- при расширении надо сохранить существующие абстрации
- следует сохранить типобезопасность
- проблема: как реализовать гибкое добавление типов и операций в некотором языке программирования?
- типовые решения реализуют двойную диспетчеризацию: выбор ветви исполнения кода в зависимости и от типа, и от операции
Подходит для процедурных и функциональных языков. Варианты: if/elseif/else, switch/case или pattern matching.
func print(node):
case node of:
AddOperator => print(node.left) + '+' + print(node.right)
NotOperator => '!' + print(node)
func eval(node):
case node of:
AddOperator => eval(node.left) + eval(node.right)
NotOperator => !eval(node)
Подходит для объектно-ориентированных и некоторых функциональных языков. Нужно наследование или утиная типизация, плюс иерархия классов.
class AddOperator(left: Node, right: Node) < Node:
meth print:
left.print + '+' + right.print
meth eval
left.eval + right.eval
class NotOperator(expr: Node) < Node:
meth print:
'!' + expr.print
meth eval
not expr.eval
Объектно-ориентированные языки не имеют встроенного решения, но зато есть паттерн проектирования Visitor (Посетитель).
- отношения классов и методов повёрнуты на 90°: новые операции становятся классами, тип данных с точки зрения операции (PrintVisitor, EvaluationVisitor) определяется методами (visitAddOperator, visitNotOperator или просто перегруженный/шаблонный visit)
Реализовать паттер Visitor в C++ можно с помощью полиморфизма (virtual-методы и классы) или с помощью шаблонов (Curiously recurring template pattern).
Реализация на CRTP (Curiously recurring template pattern):
ООП не снимает Expression Problem, но позволяет выбирать, что будет простым: добавление новых типов данных или новых операций
- если AST создан без паттерна Visitor (решение №2), проще будет добавлять новые типы данных;
- если AST создан с паттерном Visitor (решение №3), проще будет добавлять новые операции.
Псевдокод:
func (this *EvaluationVisitor) visit(node):
case node of:
AddOperator => print(node.left) + '+' + print(node.right)
NotOperator => '!' + print(node)
func eval(ast):
var visitor EvaluationVisitor
ast.walk(visitor)
- Решение хорошо работает в языках с поддержкой ООП и pattern matching, таких как Golang.
- Пример для Golang (github.com)
- В C++ 2011 можно сделать pattern matching на уровне библиотеки: библиотека Mach7 (github.com)
В примерах ниже виртуальный деструктор, спецификаторы доступа public/private и другие детили опущены.
Допустим, в AST.h
объявлен класс CNode
:
class CNode
{
virtual void accept(CVisitor & v) { v.visit(*this); }
}
В Visitor.h
объявлен класс CVisitor
:
class CVisitor
{
virtual void visit(StringElement & e) {}
virtual void visit(RealElement & e) {}
virtual void visit(IntegerElement & e) {}
}
В итоге в Visitor.h
нужна информация из AST.h
, и наоборот. Решения проблемы:
- использовать forward declaration для классов
- разделять объявление и определение методов при необходимости
- объявление в h, определение в cpp
- разделять интерфейсы, абстрактные классы, конкретные классы при необходимости
// Предварительное объявление класса (интерфейса) посетителя.
class CVisitor;
// Объявление/определение класса узла AST.
class CNode
{
// В параметрах метода упомянут класс CVisitor.
// мы можем хранить указатель на CVisitor, т.к. размер указателя не зависит от его типа.
// мы можем хранить ссылку, т.к. ссылки в C++ реализованы через указатель.
// но нельзя прямо здесь создавать, удалять, копировать CVisitor или вызывать его методы.
virtual void accept(CVisitor & v) = 0;
};
- выбирайте баланс между увеличением иерархии классов и Case-распознаванием. Например, часто заводят единый класс на все бинарные операции:
enum class BinaryOperation
{
Add,
Multiply,
// ...
}
class CBinaryExpression : CExpression
{
BinaryOperation kind;
CExpression *left;
CExpression *right;
}
- учтите, что есть инструкции с произвольной арностью (то есть произвольным количеством операндов). Пример — вызов функции:
class CCallExpression : CExpression
{
CIdentifier name;
std::vector<CExpression*> arguments;
}
- к бинарным операциям можно отнести также взятие элемента по индексу, оператор "точка", присвоение и другие специальные операции
- не стоит перегружать новый язык программирования поддержкой всех бинарных операций языка C — некоторые редко используемые можно заменить на вызовы функций или вообще убрать. Яркий пример — побитовые операции.
- для решения нетривиальных задач можно изучать существующие библиотеки для разбора промышленных языков программирования: clang AST, пакет go/ast в Golang, модуль ast в Python.