Представление множественного прохода Абстрактное синтаксическое дерево (AST) в C++?

Question

В настоящее время я изучаю разработку компилятора, который преобразует его AST в несколько этапов. Идея состоит в том, что, начиная с дерева синтаксического анализа, каждый проход преобразует дерево до тех пор, пока полученный AST не будет оптимизирован и не будет содержать всю необходимую информацию в каждом узле дерева, требуемом для генерации промежуточного кода (в данном случае LLVM IR). Проход по дереву может значительно изменить его структуру, например, изменить список операторов и операндов в иерархию упорядоченных операций через operator precedence parsing. Обратите внимание, что проход может оставить части структуры полностью неизменными.

Итак, мой вопрос в том, как мне лучше всего (читайте: проще всего, с минимальным повторением) представлять AST, который имеет несколько промежуточных представлений в C++? Я хотел бы, чтобы типы узлов из каждой версии АСТ соответствовали их несовместимости во время компиляции. Я считаю, что ключевая проблема заключается в том, как я должен представлять части структуры, которые не меняются между проходами, избегая повторного кода? Я предполагаю, что это проблема, которую много раз решали авторами компилятора в прошлом.

Обратите внимание, что в настоящее время я использую Boost Variant вместо обычного полиморфизма времени выполнения в моем AST и хотел бы, чтобы решение было совместимо с ним.

Answer 1

Ниже приведена краткая характеристика AST-boost::variant.

Я включил простое «преобразование сохранения структуры», которое просто изменяет тип данных, хранящихся в каждом узле AST. Теоретически, однако, вы можете написать произвольный astFunc, который выполняет структурный и основанный на данных преобразование узлов - просто напишите type_list, который содержит допустимые типы в каждом узле до и после.

template<typename... Ts> 
struct type_list {}; 

// specialize data_type to store something special in your AST node: 
// (by default, an entry means "the type of the data") 
tempalte<typename T> 
struct data_type { typedef T type; }; 
template<typename T> 
using DataType = typename data_type<T>::type; 

template<template<typename>class F, typename typelist> 
struct map_types; 
template<template<typename>class F, template<typename...>L, typename... Ts> 
struct map_types<F, L<Ts...>> { 
    typedef L< F<Ts>... > type; 
}; 
template<template<typename>class F, typename typelist> 
using MapTypes = typename map_types<F, typelist>::type; 

template<template<typename...>class F, typename typelist> 
struct apply_list; 
template<template<typename...>class F, template<typename...>class L, typename... Ts> 
struct apply_list<F, L<Ts...>> { 
    typedef F<Ts...> type; 
}; 
template<template<typename...>class F, typename typelist> 
using ApplyList = typename apply_list<F, typelist>::type; 
template<typename typelist> 
using Var = ApplyList< boost::variant, MapTypes<DataType, typelist> >; 

template<typename type_list> 
struct AST_Node { 
    typedef std::unique_ptr<AST_Node> upAST_Node; 
    std::vector<upAST_Node> children; 
    Var<type_list> data; 
    template<typename T> 
    AST_Node(T&& t):data(std::forward<T>(t)) {} 
}; 
template<typename type_list> 
using upAST_Node = typename AST_Node<type_list>::upAST_Node; 

template<typename before_types, typename after_types> 
using typeFunc = std::function< Var<after_types>(Var<before_types>) >; 

template<typename before_types, typename after_types> 
using astFunc = std::function< upAST_Node<after_types>(upAST_Node<before_types>) >; 

template<typename before_types, typename after_types> 
astFunc<before_types, after_types> elementWiseTransform(typeFunc<before_types, after_types> func) { 
    return [func](upAST_Node<before_types> before)->upAST_Nodes<after_types> { 
    upAST_Node<after_types> after(new AST_Node<after_types>(func(before))); 
    after->children.reserve(before->children.size()); 
    for(auto& child: before->children) { 
     after->children.push_back(elementWiseTransform(func)(std::move(child))); 
    } 
    return after; 
    }; 
} 

Теперь это только начало.

Вы можете пойти дальше, и каждый тип узла имеет разные типы типов детей или даже другое число. Просто создайте классы признаков для каждого типа узлов, например, мой data_type, например children_types. Затем используйте аналогичную технику для определения типа ваших детей Var. В принципе, у вас есть variant от std::vector< AST_Node<ChildType<type_list_element>>> через цепочку MapTypes. Черт возьми, вы можете связать std::vector детей и data вместе в один вариант.

Это позволит вам записать отображение для индивидуального AST_Node типа (что делает другой AST_Node типа), агрегировать их всех вместе и создать AST_Node<before, after> функтор, который будет затем ходить по дереву. Некоторые из функторов будут работать с данными только тогда, если родительская логика возьмет на себя роль для детей, некоторые из них преобразуют целые поддеревья, некоторые будут работать с данными и прекратить работу родительской логики над дочерними элементами.

Эта техника становится сложной, потому что вам нужно синтезировать посетителей с расширенным вариантом из ваших индивидуальных функций таким образом, чтобы они не собирали их вместе. Если вы посмотрите here, вы увидите несколько методов о том, как взять кучу std::function<T(U)> и превратить их в один функтор, который принимает любой из объединений U. Бросьте в некоторых работах, чтобы вычислить объединение типов возврата (простой type_list с дублирующимися типами, удаленный, затем перекачиваемый в boost::variant, может это сделать) - такой «объединенный функтор» будет действительным посетителем.

И теперь вы можете написать «переназначить узел АСТ типа operator_add» и «переназначить узел AST типа operator_mult» и еще несколько других, связать их вместе в мега-функтор, бросить их в АСТ алгоритм обхода и вывести из него дерево АСТ с некоторыми типами, преобразованными в другие типы ...

Но это было бы очень много работы.

О, и нам может понадобиться «фазовая маркировка», где фазы 1 и фаза 2 AST являются разными типами. Мы могли бы пометить каждый тип в type_list своей фазой или просто пометить дерево AST. Heck, мы могли бы назвать фазы для AST, используя в противном случае неиспользованные struct s, и определить прогрессию по фазам в качестве типа типа функтора, который применяется и применяется в сигнатуре astFunc<before_phase, before_types, after_phase, after_types>.

Так что это не плохо. Мы создаем типы узлов type_list. Эти типы не обязательно должны быть сохранены. Но это может быть так.

Мы создаем класс признаков data_type, который сопоставляет каждый тип узла хранящимся данным. Мы создаем класс признаков child_types, который сопоставляет каждый тип узла с типом_list дочерних АСТ.

Каждый AST_Node хранит variant<AST_Concrete_Node<Ts>...>. AST_Concrete_Node содержит DataType<T> data; и MapTypes< std::vector, MapTypes< AST_Node, ChildTypes<T> > > children; (aka, std::vector< AST_Node<ChildrenTypes...> >, но вы не можете сказать это напрямую легко).

Next, AST_Concrete_Node<T> Функции преобразования объединены в сложный бит метапрограммирования шаблонов в посетителях с форсированным вариантом. Этот шаг действительно сложный, но я думаю, что это выполнимо. Дополнительная работа выполняется так, что неперечисленные типы пропускаются, поэтому нам не нужно постоянно говорить «о, и мы не хотим преобразовывать узел X», а скорее должны сказать «если мы нажмем узел Y, не будем превратить своих детей ".

На этом этапе я собираюсь сказать, что я не хочу этого делать, проблемы, возникающие при конкретной реализации этого беспорядка в виде гимнастики, будут подавлять мою способность абстрактно рассуждать об этом , Но идея, мы надеемся, полезна - у нас есть безопасные типы типа, которые мы объединяем вместе и генерируем безопасное дерево. Дерево - это не просто абстрактное дерево универсальных вариантов, а дерево, в котором каждый узел знает, какие типы допускаются в его дочерних элементах, которые рекурсивно знают то же самое. Мы могли бы даже справиться с «этим, должно быть, ровно 3 ребенка, первый из которых - int, второй - Bob, а третий - double« если мы пройдем достаточно далеко вниз по кроличьей дыре.

Answer 2

Узлы AST сами по себе не нуждаются в огромной сложности. Я думаю, что все это оборудование АСТ-узлов просто переборщило.

Проблема с АСТ не является безопасностью типа узла; его форма дерева безопасность. AST представляет (предположительно) некоторый действительный экземпляр некоторого языка L. То, что вы в идеале хотите, это преобразования в AST для создания других действующих АСТ (экземпляры языка L). Вы не будете гарантировать это, гарантируя, что какой-либо один узел имеет допустимый тип; вы можете сделать это, гарантируя, что любой патч дерева создает действительное дерево . И это очень сложно сделать, если операции дерева являются атомарными (например, «изменить узел», «заменить ребенка», «заменить родителя») и применяться отдельно; после нескольких таких шагов, что именно вы можете сказать о дереве?

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

Большинство стандартных program transformation systems сделайте это. Они достигают этого, держа модель грамматики для L и проверяя, что предлагаемые преобразования хорошо типизированы. Это гарантирует, что преобразования языка L на язык L остаются хорошо сформированными.

Это сложнее получить, если карта преобразований с одного языка A на другой язык B; если некоторые такие преобразования применяются, вы обычно получаете дерево со смешанными типами, которое не является законным ни на одном из языков. С осторожностью можно определить набор преобразований, которые отображают все поддеревья языка A на язык B и применяют их исчерпывающе; то вы хотите, чтобы полученное дерево было хорошо сформировано для B. Вы можете убедиться, что, настаивая всякий раз, когда B-patch вставлен в смешанное дерево, если он смежн с другим B-патчем, то получающийся в результате составной B-патч хорошо формируется. Это можно сделать, используя один и тот же стиль проверки грамматики.

Используя эти идеи, вы можете создать систему, которая отображает AST через серию «представлений» (langauges A, B, C, ....) и верит, что результирующее дерево имеет хорошую форму. Эта идея обобщает на переписывание графа.