Абстрактное представление дерева синтаксиса в С++

У меня уже есть интерфейс tokenizer, который создает список токенов. У меня есть рабочий механизм для парсера. Это действительно уникально и работает как шарм. Единственное, что я пропустил, это основная структура АСТ. Как дерево, узлы и операторы должны быть представлены на уровне абстракции. Мне не нужна какая-либо реализация, только быстрая идея, как она должна выглядеть в иерархии классов? Я работаю над объектно-ориентированным языком. Да, я уже понял, что мне потребуются два типа заявлений. Некоторое значение возвращает выражение типа "выражение" и не возвращающий инструкцию для управления потоком команд. Большое вам спасибо.

Ответ 1

Если ваш язык является обязательным /c -like, общий сценарий начинается с того, что верхняя иерархия разделяется на 2 супертипа:

Выражение
Заявление

Программа представляет собой список операторов, который является самим выражением.

Вероятно, вы захотите иметь один класс для типа оператора, который расширяет базовый класс оператора.

Типичный сценарий выглядит так:

блок операторов (список операторов)
ite (если тогда еще)
for (цикл for с его списком инструкций инициализации, выражение проверки, инструкции инкремента и блок
while (похоже, но только проверить выражение
объявление переменной
(включая + = - = ++ - вы можете обернуть все в один класс с помощью поля оператора, lval и rval)
Функциональный вызов (void one)

Для выражений:

Bop (двоичная операция, все, что имеет 2 операнда и 1 оператор i.e. + - */% | и && || == <
Uop (унарная операция, все, что имеет 1 операнд и 1 оператор, т.е. ~!)
Вызов функции (непустые)
Условное выражение (exp? true val: false val)

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

Например, некоторые классы будут выглядеть так (псевдокод):

class Ite extends Statement {
   Expression condition;
   Statement ifBranch;
   Statement elseBranch;
}


class Bop extends Expression {
   BOperator operator;  // +, -. * or whatever
   Expression left;     // Left operand
   Expression right;    // Right operand
}


class StatementBlock extends Statement {
   List<Statement> statements;
}


class Assignment extends Statement {
   AOperator assignOp;  // = += -= etc.
   LVal lvalue;         // The lvalue cannot be an arbitrary expression, you will usually have a specific type for it
   Expression rvalue;   // Right value
}

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

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

enum Type {
   CHAR,
   SHORT,
   INT,
   LONG,
   FLOAT,
   DOUBLE,
   ARRAY
}

class Float extends StaticType {
    final Type type = Type.FLOAT;
}

class Array extends StaticArray {
    final Type type = Type.ARRAY;

    int size;
}

Затем вы создадите экземпляр экземпляра StaticType для каждого типа в AST, например, когда пользователь объявит переменную. Вы также сможете использовать одну и ту же иерархию, если вы планируете также проводить статическую проверку типов в будущем.

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

Абстрактное представление дерева синтаксиса в С++

Ответы

Ответ 1