Представление абстрактного дерева синтаксиса в C

Я реализую компилятор для простого игрушечного языка в C. У меня есть рабочий сканер и парсер, и разумный фон для концептуальной функции/построения АСТ. Мой вопрос связан с конкретным способом представления AST в C. Я часто встречал три стиля в разных текстах/ресурсах в Интернете:

Одна структура для типа node.

У этого есть базовый node "class" (struct), который является первым полем во всех дочерних структурах. База node содержит перечисление, которое хранит тип node (постоянный, двоичный оператор, назначение и т.д.). Доступ к элементам структуры осуществляется с помощью набора макросов с одним набором для каждой структуры. Это выглядит примерно так:

struct ast_node_base {
    enum {CONSTANT, ADD, SUB, ASSIGNMENT} class;
};

struct ast_node_constant {
    struct ast_node_base *base;
    int value;
};

struct ast_node_add {
    struct ast_node_base *base;
    struct ast_node_base *left;
    struct ast_node_base *right;
};

struct ast_node_assign {
    struct ast_node_base *base;
    struct ast_node_base *left;
    struct ast_node_base *right;
};

#define CLASS(node) ((ast_node_base*)node)->class;

#define ADD_LEFT(node) ((ast_node_add*)node)->left;
#define ADD_RIGHT(node) ((ast_node_add*)node)->right;

#define ASSIGN_LEFT(node) ((ast_node_assign*)node)->left;
#define ASSIGN_RIGHT(node) ((ast_node_assign*)node)->right;

Одна структура на макет node.

Похоже, что это в основном такое же, как в приведенном выше макете, за исключением того, что вместо ast_node_add и ast_node_assign у него будет атрибут ast_node_binary для представления обоих, поскольку макет двух структур одинаковый, и они отличаются только содержимым базы → класс. Преимуществом этого является более равномерный набор макросов (LEFT (node) для всех узлов с левым и правым, а не с одной парой макросов на), но недостатком кажется, что проверка типа C не будет (не было бы способа обнаружить ast_node_assign, где, например, должен быть только ast_node_add).

Одна общая структура, с объединением для хранения различных типов данных node.

Лучшее объяснение этого, чем я могу дать, можно найти здесь. Используя типы из предыдущего примера, это будет выглядеть так:

struct ast_node {
  enum { CONSTANT, ADD, SUB, ASSIGNMENT } class;
  union { int                                 value;
          struct { struct ast_node* left;    
                   struct ast_node* right;  } op;
};

Я склонен больше любить третий вариант, потому что он делает рекурсивный обход намного проще (в том, что многие литья указателей избегают в пользу объединения), но он также не использует проверку типа C. Первый вариант кажется самым опасным в том, что он полагается на указатели на структурированные объекты, чтобы получить доступ к члену любого node (даже разные члены одного и того же node, требующие доступа к различным случаям (базовые и левые)), но эти приведения проверяются по типу, поэтому могут быть спорными. Второй вариант для меня кажется худшим из обоих миров, хотя, может быть, я чего-то не хватает.

Какие из этих трех схем являются лучшими и почему? Есть ли лучший четвертый вариант, с которым я еще не сталкивался? Я предполагаю, что ни один из них не является решением "одного размера подходит всем", поэтому, если он имеет значение для языка, который я реализую, это статически типизированный императив язык, почти небольшое подмножество C.

Конкретный вопрос, который у меня есть о третьем (объединении) макете. Если я использую только поле значений, будет ли пустое пространство, следующее за значением, чтобы разместить возможность записи op на?

Ответ 1

Вы можете сделать любую из этих работ.

Я предпочитаю макет объединения, потому что тогда все узлы имеют один и тот же макет.

[Возможно, вам будет полезно иметь опцию "дочерний подписок", например, и достаточно большой динамический массив дочерних элементов, вместо списков слева или справа.]

Вы обнаружите, что проблема не в том, что делает ваш компилятор сложным. Скорее, он имеет таблицы символов, выполняет различные виды анализов, выбирает IR на машинный уровень, создает генератор кода и выполняет оптимизацию кода. Затем вы столкнетесь с реальными пользователями, и вы обнаружите, что вы действительно ошибались: -}

Я бы выбрал один и запускал его, чтобы у вас была возможность приблизиться к другим проблемам.

Ответ 2

Ира Бакстер дала вам хороший простой и перспективный ответ , особенно отметим проблемы, с которыми вы столкнетесь в будущем, поэтому я остановлюсь на этом вопросе:

Есть ли лучший четвертый вариант, с которым я еще не сталкивался?

Вы используете императивный язык для написания компилятора и проблем с проектированием структуры данных для концепции node в AST. В мире функциональных языков, таких как ML, OCaml, Haskell, F # one, можно использовать Tagged union для хранения всех разных node типы в одной структуре данных, которые в основном вы создали.

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