алгоритм — Генерация AST в переполнении стека
Я делаю интерпретатор в C ++, пока у меня есть лексер для генерации токенов. Проблема в том, что я не уверен, как генерировать «обход» дерева разбора.
Я думал о том, чтобы создать дерево разбора с использованием массива массивов, но я не уверен, как на самом деле вставить токены в дерево разбора в правильном порядке.
Я не уверен, стоит ли идти сверху вниз, слева направо или снизу вверх, справа налево.
Может ли кто-нибудь предоставить мне простой алгоритм LALR (1)?
Решение
Я собираюсь пойти вразрез с общепринятым мнением и сказать, что вы должны создать свой AST вручную с помощью структур данных, специфичных для конкретного языка.
Обобщенная «структура данных AST» будет слишком общей, чтобы работать с ней было удобно — код, который использует AST для выполнения чего-либо полезного, будет скрыт обходными путями для доступа к нужным данным. Если вы пойдете этим путем (или воспользуетесь генератором синтаксического анализатора), вы, скорее всего, в конечном итоге создадите слой перевода, чтобы перейти от общей структуры к AST, которая действительно имеет смысл для вашего языка. Почему бы не избежать посредника и напрямую построить окончательную структуру данных?
Я предлагаю написать первый синтаксический проход, который потребляет токены, в которых он нуждается для каждой возможной конструкции (вероятно, при необходимости выглянул вперед на один токен). Этот синтаксический этап создаст AST из связанных экземпляров структур данных, которые представляют каждую возможную конструкцию на вашем языке. Например, если ваша программа может состоять из серии операторов, где каждый оператор может быть либо объявлением функции, либо вызовом функции, вы можете создать следующие структуры данных:
AST (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 ast = parseAST();
где parseAST звонки parseStatement многократно, который потребляет и / или просматривает токены, чтобы определить, является ли оператор определением функции или вызовом функции, затем вызывает parseFunction или же parseCall соответственно. Это называется рукописный синтаксический анализатор с рекурсивным спуском, и, по моему опыту, это самый простой и лучший тип анализатора, который вы можете написать. Да, есть шаблон для написания, но это также очень понятный и гибкий код.
Синтаксическая фаза генерирует синтаксические сообщения об ошибках по мере необходимости, пытаясь восстановить их как можно лучше, когда обнаружена ошибка (это один из аргументов для языков, разделенных точкой с запятой — компиляторы и инструменты часто могут гораздо легче восстанавливаться после ошибок, поскольку часто бывает достаточно перейти к следующей точке с запятой при обнаружении ошибки, прежде чем пытаться проанализировать следующую конструкцию).
Если функции разрешено вызывать до ее определения, это тоже просто для обработки — просто проанализируйте часть вызова, не проверяя, существует ли функция с таким именем в момент первого ее анализа, а затем сопоставьте ее позже.
Второй, семантический, проход через AST аннотирует его с отсутствующими перекрестными ссылками (например, разрешает вызовы функций с именами функций с определениями этих функций или генерирует ошибку, если имя не найдено). Как только это будет сделано, у вас будет полный AST, который гарантированно будет представлять действительную программу (так как вы выполнили всю семантическую проверку ошибок на этом этапе), и к ней могут быть применены оптимизации, затем фаза генерации кода (и дополнительные оптимизации вдоль путь).
Обратите внимание, что я полностью исключил любое упоминание парсеров LL или LR и т. Д. Теоретическая нотация и категоризация вашего языка важны (поскольку это может доказать, что он не является неоднозначным, например), но с точки зрения реализации, это далеко важнее иметь чистый, понятный и прежде всего легко модифицируемый код, чем придерживаться определенного механизма синтаксического анализа. Примеры других компиляторов, которые используют рукописные парсеры, включают GCC, Clang и Google V8, среди других.
С точки зрения эффективности, AST, как правило, повторяется несколько раз после его создания, и ему нужно оставаться в памяти до поздней стадии процесса (возможно, до самого конца, в зависимости от того, как вы выполняете генерацию кода), и поэтому лучше использовать пул объектов для размещения записей для вашего AST, а не для динамического размещения всего отдельно в куче. Наконец, вместо строк, как правило, лучше использовать смещение и длину в исходном исходном коде.
Другие решения
Вы могли бы использовать некоторые генератор парсеров лайк бизон или же ANTLR. У обоих есть хорошая документация с учебной частью. Часть действия ваших правил грамматики bisonили же antlr, который генерирует код C ++ для синтаксического анализа) будет строить абстрактное синтаксическое дерево.
Мы не можем помочь больше, не зная больше синтаксис (и семантика) формального языка, который вы хотите разобрать и интерпретировать.
Если ваш язык — инфиксный калькулятор, у бизона такой пример.
Вы, вероятно, должны подумать об иерархии классов, чтобы представить узлы вашего АСТ. У вас будет класс для листьев (например, чисел), класс для узла сложения (с двумя сыновьями как умные указатели в другие узлы) и т. д …
например
class ASTNode {
/// from http://stackoverflow.com/a/28530559/841108
///... add some things here, e.g. a virtual print method
};
class NumberNode : public ASTNode {
long number;
/// etc...
};
class BinaryOpNode : public ASTNode {
std::unique_ptr<ASTNode> left;
std::unique_ptr<ASTNode> right;
/// etc....
};
class AdditionNode : public BinaryOpNode {
/// etc....
};
class CallNode : public ASTNode {
std::shared_ptr<Function> func;
std::vector<std::unique_ptr<ASTNode>> args;
};
для узлов вариационной арности (то есть любого количества сыновей) вам понадобится вектор умных указателей, например args выше.
Чтобы пройти по дереву, вы будете выполнять рекурсивный обход, чтобы лучше использовать умные указатели. Читайте также о шаблон посетителя. И с C ++ 11 станд :: функция-s и анонимные закрытия -i.e лямбды— , Вы могли бы иметь visit виртуальная функция (которой вы даете замыкание, посещая каждый узел). Unix nftw (3) функция, которая посещает деревья файлов, может быть вдохновляющей.
Люди строят AST как деревья, выделенные из кучи. (Да, вы можете сделать это массивом, но это не так удобно). Я предлагаю вам ПРОЧИТАТЬ документацию зубров; он объяснит вам, как строить деревья, и вы можете следовать этому стилю.
Догадываясь на уровне своего опыта, основанного на вашем вопросе, я бы на вашем месте построил бы парсер / сборщик AST на основе flex / bison хотя бы один раз, чтобы получить хороший опыт, прежде чем вы вернетесь к самому созданию.