Сердце современных фронтендов компиляторов — абстрактное синтаксическое дерево (Abstract Syntax Tree, AST). Оно создаётся на стадии синтаксического разбора, обрабатывается путём обхода при проверке семантических правил и проверке/определении типов, а затем также путём обхода AST выполняется генерация кода.

Зачем нужен AST

AST - это Abstract Syntax Tree, то есть дерево, которое в абстрактном виде представляет структуру программы. AST создаётся парсером по мере синтаксического разбора программы. В современных компиляторах AST и список диагностик (ошибок, предупреждений) - это два результата вызова модуля синтаксического разбора.

AST содержит полную синтаксическую модель программы без лишних деталей (таких, как пробельные символы или комментарии). Чтобы понять, как это работает, рассмотрим, из чего состоит типичный язык программирования.

Типовой императивный язык программирования (такой как C, C++, PASCAL, Java, JavaScript, C#) состоит из трёх синтаксических элементов:

• Выражения (expressions)
• Инструкции (statements)
• Объявления (declarations)

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

Выражения

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

• Доступ к переменной (variable access): например, x
• Литерал (literal): например, 5.18 или "some meaningful string"
• Унарный оператор (unary operator): например, -x
• Бинарный оператор (binary operator): например, x + 5.18 или x == 5.18
  • Разные бинарные операторы обычно имеют разный приоритет и могут группироваться скобками, но в функциональных языках (LISP, Haskell) операторы бывают неотличимы от функций
  • Типовой набор операторов: арифметические, логические, сравнения; такой набор уже позволяет создавать полноценные программы
• Вызов функции (function call): например, sqrt(pow(a, 2.0) + pow(b, 2.0))

Инструкции

Инструкции - это действия в исходном коде. Инструкция всегда имеет побочный эффект (печать, присваивание переменной, смена потока управления и т.д.), поэтому в некоторых языках инструкций не существует - например, в LISP или Haskell.

Примеры инструкций, характерных для процедурных языков:

• Объявление переменной с опциональной/обязательной инициализацией, например, let value = ...; или int x = 500;
  • В языке Python объявлений переменных нет
• Присвоение переменной, например, velocity = velocity + acceleration * dt;
• Специальные инструкции, например, печать print x+1 или проверка контракта assert isinstance(x, int) в языке Python
• Условные инструкции, такие как if, switch
• Циклы, такие как while, do/while, repeat/until, for, foreach
• Инструкции потока управления, например, возвраты из функций return x+5; или прерывания циклов break;
  • Возвраты требуются не во всех языках - иногда функция просто возвращает последнее вычисленное выражение
• Блоки кода, такие как { doA(); doB(); return 5; }

Объявление

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

Спорные вопросы

Некоторые сущности трудно отнести к той или иной категории. Например:

• Объявление анонимной функции (лямбды) можно считать объявлением без имени либо выражением
• Объявление переменной можно считать как просто инструкцией, так и полноценным объявлением

Спорные вопросы обычно решаются в сторону удобства для создателя языка или компилятора.

Что такое AST?

AST - это Abstract Syntax Tree, т.е. представление структуры программы в виде дерева объявлений, инструкций и выражений.

• AST не является бинарным деревом: например, у унарного оператора будет один дочерний узел
• AST является гетерогенным деревом, состоящим из узлов разного типа
  • В этом AST похож на DOM-представление документа HTML/XML
• В каждом поддереве дочерними узлами становятся лексически вложенные сущности: например, для узла объявления функции дочерними узлами являются инструкции, составляющие тело функции, а также объявления параметров функции (если они выделены в отдельные узлы AST волей автора компилятора)

Удобный способ реализовать AST в коде - это иерархия классов и интерфейсов. Например, можно ввести три базовых интерфейса:

• ExpressionAST - интерфейс, который реализуется всеми выражениями
• StatementAST - интерфейс, который реализуется всеми инструкциями
• DeclarationAST - аналогичный интерфейс для объявлений функций и типов
  • В компилируемых языках всю программу целиком можно считать списком DeclarationAST, в скриптовых - списком StatementAST
  • Альтернативно, можно ввести специальный узел ProgramAST или ModuleAST

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

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

Суть дерева - в возможности обойти его (слева направо в глубину или другим способом). При обходе можно выполнять осмысленные действия, при этом возникает проблема двойной диспетчеризации: мы должны выбирать действие в зависимости как от алгоритма, которым мы обрабатываем дерево, так и от типа узла дерева, который мы сейчас обходим. Рассмотрим пути решения проблемы:

• Можно избежать проблемы: например, добавляем полиморфный метод Evaluate в интерфейс ExpressionAST и реализуем его по-разному в классах LiteralAST, VariableAST, BinaryOperatorAST, CallAST - на выходе получаем возможность вычислить выражение
• Можно решить проблему с помощью шаблона проектирования Visitor (Посетитель)
• Можно решить проблему с помощью сопоставления шаблона (pattern matching) по типу, если язык это поддерживает
  • Например, в Go можно использовать type switch
  • В C++ можно было бы использовать std::variant, но он не поддерживает рекурсию в собственном определении

Конструирование AST в парсере

Для конструирования узлов AST потребуется выделять память, а затем запоминать указатель в стеке парсера. Напомним, что любой реальный язык содержит рекурсивные синтаксические правила (например, выражения всегда определяются рекурсивно), значит, парсер языка не может быть реализован без стека или без рекурсии (которая эквивалентна стеку). Поэтому способ работы с AST зависит от метода создания парсера.

Рекурсивный спуск

Если вы используете рекурсивный спуск, то вы скорее всего

• Пишете по одной функции/методу парсинга на каждое правило формальной грамматики: например, методы Parser::parseExpr, Parser::parseCallExpr, Parser::parseAssignment
• В случае ошибки разбора бросаете исключение или добавляете объект, описывающий ошибку, в возвращаемое значение каждой функции парсера

Таким образом, типичная функция парсинга выглядит примерно так:

bool Parser::parseExpr()
{
    // Если следующий токен - ID, то это вызов функции или обращение к переменной
    if (NextToken().type == Token.ID)
    {
        if (NextToken(2).type == Token.OpenParen)
        {
            return parseCallExpr();
        }
        return parseVariableAccess();
    }

    // ... разбираем иные варианты ...

    // Ожидалось выражение, но его нет
    throw ParseException("expected expression, got " + NextToken().ToString(), NextToken());
}

Для добавления конструирования AST следуйте простым правилам:

• на каждое правило грамматики создавайте узлы AST с помощью оператора new, а в языке C++ - с помощью std::make_unique
• сохраняйте указатели на узлы в локальные переменные
• возвращайте из каждой функции парсинга указатель на узел AST, полученный при разборе по соответствующему правилу грамматики
  • в случае ошибки - бросайте исключение

Восходящий разбор методом свёртки (LL, LR, SLR, LALR)

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

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

Пример декларативного описания правила грамматики с конструированием AST (для генератора парсеров Lemon):

statement ::= PRINT expression(A).
{
    auto stmt = pParse->MakeAST<CPrintAst>(A.expr);
    pParse->AddStatement(stmt);
}

Обработка готового AST

Путём обработки готового AST можно

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

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

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

function visit(node) {
    actionBeforeVisit(node)
    for child in node.children()
        child.accept(this)
    actionAfterVisit(node)
}

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

function visit(node) {
    actionBeforeVisit(node)
    for child in reverse(node.children())
        child.accept(this)
    actionAfterVisit(node)
}

В ширину слева направо (влечёт значительный расход памяти):

function visit(node_list) {
    new_node_list = []
    for node in node_list {
        actionOnVisit(node)
        for child in node.children()
            new_node_list << child
    }
    visit(new_node_list)
}

В ширину справа налево (влечёт значительный расход памяти).

Expression problem

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

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

Подходит для процедурных и функциональных языков. Варианты: if/elseif/else, switch/case или pattern matching.

// Печатает поддерево, начиная с узла node
function print(node) {
  case node of {
    AddOperator => print(node.left) + '+' + print(node.right)
    NotOperator => '!' + print(node)
    Variable    => print(variables.get(node.name).value)
    Literal     => print(node.value)
  }
}

// Вычисляет значение, начиная с узла node
function eval(node) {
  case node of {
    AddOperator => return eval(node.left) + eval(node.right)
    NotOperator => return !eval(node)
    Variable    => return variables.get(node.name).value
    Literal     => return node.value
  }
}

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

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

class AddOperator extends Node {
  let left: Node = null
  let right: Node = null

  function print() {
    left.print()
    print(' + ')
    right.print()
  }

  function eval() {
    return left.eval() + right.eval()
  }
}

class NotOperator extends Node {
  let child: Node = null

  function print() {
    print('!')
    child.print()
  }

  function eval() {
    return not child.eval()
  }
}

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

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

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

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

Реализация на виртуальных методах:

struct VaribleAst;
struct LiteralAst;

struct IVisitor
{
    virtual ~IVisitor() = default;
    virtual void visit(VaribleAst &ast) = 0;
    virtual void visit(LiteralAst &ast) = 0;
};

struct IExpressionAst
{
    virtual ~IExpressionAst() = default;
    virtual void accept(IVisitor &visitor) = 0;
}

struct VariableAst : IExpressionAst
{
    void accept(IVisitor &visitor) override {
        visitor.visit(*this);
    }
}

struct LiteralAst : IExpressionAst
{
    void accept(IVisitor &visitor) override {
        visitor.visit(*this);
    }
}

Реализация на CRTP (Curiously recurring template pattern), которую не рекомендуется использовать из-за бессмысленной сложности:

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

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

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

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

Псевдокод:

function (this *EvaluationVisitor) visit(node) {
  case node of:
    AddOperator => print(node.left) + '+' + print(node.right)
    NotOperator => '!' + print(node)
}

function eval(ast) {
  var visitor EvaluationVisitor
  ast.walk(visitor)
}

• Решение хорошо работает в языках с поддержкой ООП и pattern matching, таких как Golang.
• Пример для Golang (github.com)
• В C++ 2011 можно сделать pattern matching на уровне библиотеки: библиотека Mach7 (github.com)

Семантическая постобработка дерева

Семантическая постобработка дерева позволяет добавить в язык правила, выходящие за рамки контекстно-свободных грамматик.

Например, путём постобработки можно:

• проверить корректность всех выражений с точки зрения типов
• добавить в язык возможность размещать вызов функции до её объявления в исходном коде (как в языке JavaScript)
• проверить корректность использования break; и continue; - должны использоваться только внутри циклов

Подобные шаги постобработки дерева называются “процедурами семантической проверки”, их часто выделяют в собственный модуль - модуль семантики языка.

Генерация кода по AST

О методах генерации кода на базе собранного AST вы можете прочитать в статье Стековые и регистровые машины.