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

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

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

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

Ответ 1

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

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

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

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

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

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

Ответ 2

Вот быстрый удар в безопасном типе boost::variant на основе AST.

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

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

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

Вы можете пойти дальше, и каждый тип node имеет другой набор типов детей или даже другое число. Просто создайте классы признаков для каждого типа node, например my data_type, например children_types. Затем используйте аналогичную технику, как я определил Var, чтобы определить тип ваших детей. В принципе, у вас есть variant of 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 node типа operator_add" и "переназначить AST node типа operator_mult" и еще несколько других, связать их вместе в мега-функтор, бросить их в алгоритме обхода AST, и вывести его из дерева AST с некоторыми типами, преобразованными в другие типы...

Но это будет много работы.

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

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

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

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

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

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