конструкция компилятора — Представление абстрактного синтаксического дерева (AST) в C ++ с несколькими проходами?
В настоящее время я изучаю проект компилятора, который преобразует свой AST в несколько этапов. Идея состоит в том, что, начиная с дерева разбора, каждый проход преобразует дерево, пока результирующий AST не будет оптимизирован и содержит всю необходимую информацию в каждом узле дерева, необходимую для генерации промежуточного кода (в этом случае LLVM ИК). Передача по дереву может значительно изменить его структуру, например, путем изменения списка операторов и операндов в иерархию упорядоченных операций с помощью разбор приоритетов операторов. Обратите внимание, что проход может оставить части структуры полностью без изменений.
Итак, мой вопрос заключается в том, как мне лучше всего (читай: проще всего, с как можно меньшим количеством повторений) представлять AST, который имеет несколько промежуточных представлений в C ++? Я хотел бы, чтобы типы узлов из версии AST каждой фазы учитывали их несовместимость во время компиляции. Я считаю, что ключевой вопрос заключается в том, как мне представить части структуры, которые не меняются между проходами, избегая при этом повторяющегося кода? Я полагаю, что эта проблема решалась много раз в прошлом авторами компилятора.
Обратите внимание, что я в настоящее время использую Boost Variant вместо обычного полиморфизма во время выполнения в моем AST, и хотелось бы, чтобы решение было совместимо с ним.
Решение
Узлы AST сами по себе не требуют огромного количества сложности. Я думаю, что все это оборудование узла AST просто излишне.
Проблема с AST не в безопасности типа узла; его форма дерева безопасность. AST представляет (предположительно) некоторый действительный экземпляр некоторого языка L. В идеале вы хотите, чтобы преобразования в AST производили другие действительные AST (экземпляры языка L). Вы не собираетесь гарантировать это, гарантируя, что у любого узла есть допустимый тип; Вы можете сделать это, только гарантировав, что любой патч дерева создаст действительный дерево. И это очень трудно сделать, если операции с деревом являются атомарными (например, «изменить узел», «заменить дочерний», «заменить родительский») и применяются отдельно; Что вы можете сказать о дереве после нескольких таких шагов?
Это лучше сделать с помощью своего рода транзакции перезаписи дерева, например, преобразований источник-источник, грамматическая структура которых допустима для языка L, и которые применяются в местах, которые действительны для этого преобразования.
Самый стандартный системы трансформации программ сделай это. Они достигают этого, держа модель грамматики для L и проверяя, что предложенные преобразования хорошо напечатаны. Это гарантирует, что преобразования языка L в язык L остаются корректными.
Это сложнее понять, если преобразования отображаются с одного языка A на другой язык B; если применяются некоторые такие преобразования, вы обычно получаете дерево со смешанными типами, которое недопустимо ни на одном языке. С осторожностью можно определить набор преобразований, которые отображают все поддеревья языка A на язык B, и применяют их исчерпывающе; затем вы хотите, чтобы результирующее дерево было правильно сформировано для B. Вы можете убедиться, настаивая на том, чтобы всякий раз, когда B-патч вставлялся в смешанное дерево, если он был смежен с другим B-патчем, результирующий составной B-патч был хорошо формируется. Это вы можете сделать, используя тот же стиль проверки грамматики.
Используя эти идеи, вы можете построить систему, которая отображает AST через серию «представлений» (языков A, B, C, ….) и верит, что результирующее дерево имеет правильную форму. Эта идея обобщает граф переписывает.
Другие решения
Вот быстрый удар по типу сейфа 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> функтор, который затем будет ходить по дереву. Некоторые из функторов будут работать с данными только тогда, когда родительская логика заменит дочерние элементы, некоторые преобразуют целые поддеревья, другие будут работать с данными и не позволять родительской логике работать над дочерними элементами.
Эта техника становится хитрой, потому что вы должны синтезировать посетителей с расширенными вариантами из ваших индивидуальных функций таким образом, чтобы не требовалось объединять их все вместе. Если вы посмотрите Вот вы увидите несколько приемов о том, как взять кучу std::function<T(U)> и превратить их в один функтор, который принимает любой из U, Бросить в какую-то работу, чтобы вычислить объединение возвращаемых типов (простой type_list с удаленными дубликатами, затем закачанными в boost::variant, может сделать это) — такой «объединенный функтор» был бы действительным посетителем.
И теперь вы можете написать «переназначить функторы узла AST типа operator_add» и «переназначить узел AST типа operator_mult», а также несколько других, связать их вместе в мега-функтор, бросить их в алгоритм обхода AST и сделать так, чтобы оно извергало дерево AST с некоторыми типами, преобразованными в другие типы …
Но это было бы много работы.
О, и мы могли бы хотеть «маркировку фазы», где AST фазы 1 и фазы 2 являются различными типами. Мы могли бы пометить каждый тип в type_list с его фазой, или мы могли бы просто пометить AST само дерево. Черт, мы могли бы назвать фазы для AST используя в противном случае неиспользованный structs, и определите прохождение фаз как функтор типа к типу, который применяется и применяется в сигнатуре astFunc<before_phase, before_types, after_phase, after_types>,
Так что это не плохо. Мы создаем type_list типов узлов. Эти типы не обязательно должны быть фактическими данными. Но это может быть.
Мы создаем data_type класс признаков, который отображает каждый тип узла на сохраненные данные. Мы создаем child_types класс traits, который отображает каждый тип узла в список type_list дочерних AST.
каждый AST_Node хранит variant<AST_Concrete_Node<Ts>...>, AST_Concrete_Node содержит DataType<T> data; и MapTypes< std::vector, MapTypes< AST_Node, ChildTypes<T> > > children; (Он же, std::vector< AST_Node<ChildrenTypes...> >, но вы не можете сказать это прямо легко).
Следующий, AST_Concrete_Node<T> Функции трансформации соединяются друг с другом в хитросплетении метапрограммирования шаблонов в расширенные варианты посетителей. Этот шаг действительно сложный, но я думаю выполнимый. Дополнительная работа выполняется для того, чтобы не упомянутые типы были пропущены, поэтому нам не нужно постоянно говорить «о, и мы не хотим преобразовывать узел X», а нужно сказать «если мы нажмем на узел Y, не превратить своих детей «.
На данный момент, я собираюсь сказать, что я болтаю — не сделав этого раньше, проблемы, возникающие при конкретной реализации этого беспорядка в типовой гимнастике, перевесят мою способность абстрактно рассуждать об этом. Но идея, надеюсь, полезна — у нас есть типобезопасные преобразования типа узла, которые мы собираем вместе и генерируем типобезопасное преобразование дерева. Дерево — это не просто абстрактное дерево универсальных вариантов, а дерево, в котором каждый узел знает, какие типы допустимы в его дочерних элементах, и которые рекурсивно знают то же самое. Мы могли бы даже обработать «это должно быть ровно 3 детей, первый из которых является intВторое Bobи третий double«Если бы мы зашли достаточно далеко вниз по кроличьей норе.