Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Кодирование AST

Связь 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):

Вывод

ООП не снимает 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)

Проблема рекурсии заголовочных файлов и её решение

В примерах ниже виртуальный деструктор, спецификаторы доступа 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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment