Кодирование AST

ast.md

Связь AST и парсера

• Абстрактное синтаксическое дерево (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();

Error Recovery

Кроме создания AST, на стадии синтаксического анализа при наличии в исходном коде ошибок надо

• сгенерировать сообщения об ошибках
• постараться восстановиться после ошибок

В языках, где точка с запятой или конец строки служат разделителями, компилятору проще восстановиться после ошибок: он может просто сообщить об ошибке, проигнорировать все символы до следующего разделителя и продолжить разбор.

Постобработка дерева

Если язык разрешает разместить вызов функции до её определения, это легко обработать:

• распарсим весь файл, включая вызовы функций, без проверки имён функций
• после окончания разбора обойти дерево и найти все вызовы необъявленных функций
• подобные шаги постобработки дерева называются "процедурами семантической проверки"

Роль AST и семантического анализа в компиляторе

Процедуры семантической проверки дополняют AST недостающими кросс-ссылками между ветвями дерева:

• ссылками от узла вызова функции к узлу её объявления
• ссылками от узла переменной в выражении к узлу объявления локальной переменной, глобальной переменной или параметра функции
• ссылками от объявления переменной к узлу пользовательского типа данных, использованному в объявлении
• при отсутствии обязательной ссылки создаётся новое сообщение об ошибке
• также семантический анализ проверяет соответствие типов в выражениях

После семантического анализа мы получаем одно из двух:

• либо неполное AST и список ошибок в программе
• либо завершённое AST, гарантированно представляющее правильно написанную программу

После этого можно генерировать трёхадресный код, а затем отдавать его оптимизатору и кодогенератору под конкретную аппаратную платформу:

• Обычно оптимизатор и платформо-зависимый кодогенератор объединяют в "бекенд компилятора"
• Задача фронтенда компилятора — создать AST и сгенерировать из него трёхадресный код для бекенда.
• Таким образом, лексический, синтаксический и семантический анализ вместе с генератором трёхадресного кода попадают во фронтенд.

Производительность AST

Обычно AST обходится несколько раз уже после создания. Если AST очень велико, то для приемлемой скорости узлы дерева должны располагаться в соседних областях памяти.

• Это можно реализовать с помощью применения Memory Pool (или Object Pool) для размещения в памяти узлов дерева.
• Для простых языков и небольших файлов такой подход может оказаться преждевременной оптимизацией.

Способы обхода AST

• в глубину слева направо

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)

• в ширину справа налево (лишний расход памяти)

Проблема расширяемости кода:

• программы манипулируют данными с помощью операций.
• в процессе эволюции программы добавляются новые типы данных и новые операции
  • новая операция должна работать с существующими типами данных
  • новый тип данных совместим с существующими операциями
• по-настоящему расширяемый код не требует модификации существующих модулей
  • модулем может считаться один файл, один класс, одна функция
  • новое расширение попадает в отдельный модуль
  • при расширении надо сохранить существующие абстрации
  • следует сохранить типобезопасность

Expression problem

• проблема: как реализовать гибкое добавление типов и операций в некотором языке программирования?
• типовые решения реализуют двойную диспетчеризацию: выбор ветви исполнения кода в зависимости и от типа, и от операции

Решение 1: case-распознавание

Подходит для процедурных и функциональных языков. Варианты: 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)

Решение 2: полиморфные методы

Подходит для объектно-ориентированных и некоторых функциональных языков. Нужно наследование или утиная типизация, плюс иерархия классов.

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

Решение 3: Visitor (Посетитель)

Объектно-ориентированные языки не имеют встроенного решения, но зато есть паттерн проектирования Visitor (Посетитель).

• отношения классов и методов повёрнуты на 90°: новые операции становятся классами, тип данных с точки зрения операции (PrintVisitor, EvaluationVisitor) определяется методами (visitAddOperator, visitNotOperator или просто перегруженный/шаблонный visit)

Реализовать паттер Visitor в C++ можно с помощью полиморфизма (virtual-методы и классы) или с помощью шаблонов (Curiously recurring template pattern).

Реализация на CRTP (Curiously recurring template pattern):

• шаблоны Visitor и Visitable
• пример использования

Вывод

ООП не снимает Expression Problem, но позволяет выбирать, что будет простым: добавление новых типов данных или новых операций

• если AST создан без паттерна Visitor (решение №2), проще будет добавлять новые типы данных;
• если AST создан с паттерном Visitor (решение №3), проще будет добавлять новые операции.

Решение 4: Обход дерева и case-распознавание

Псевдокод:

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;
};

Как создавать узлы AST

• выбирайте баланс между увеличением иерархии классов и 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.