Абстрактный синтаксический вопрос дерева - PullRequest
Новая
       13

Абстрактный синтаксический вопрос дерева

4 голосов
/ 26 декабря 2009

В настоящее время я работаю над компилятором под C, и я теряюсь в той части, где мы строим структуру данных для AST, особенно для той части, где мы создаем структуру для идентификаторов, она называется «Запись таблицы символов» *

Я вижу структуры по сети, такие как: 

struct ste {
  struct id   *name;  /* pointer into hash table for assoc. id */
  struct decl *decl;  /* pointer into symbol table for its decl */
  struct ste  *prev;  /* pointer to previous entry in symbol table */
};

Это похоже на связанный список, так как содержит указатель на предыдущую запись (* prev), но какая логика стоит за этим?

Ответы [ 3 ]

8 голосов
/ 26 декабря 2009

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

{
int x;
  {
   int x;
  }
}

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

2 голосов
/ 26 декабря 2009

Вы давно видите остатки пагубной привычки от программистов на C: предполагается, что символы будут в некоторых списках, и вместо того, чтобы размещать структуры списков отдельно, указатели списков включаются как часть структуры символов. Этот трюк экономит одно выделение на элемент списка, но с затратами: набор списков, в котором может быть символ, является фиксированным, и эта структура сбивает с толку программистов. Если приложение является компилятором, нет причин использовать этот трюк больше. Гораздо понятнее иметь отдельную структуру списка, которая определяется примерно так: 

struct ste_list {
    struct ste *symbol_table_entry;
    struct str_list *next;
};

Вы можете иметь столько их, сколько захотите, и никто не станет мудрее. И внутренние указатели, которые вы находите смущающими, исчезают.

Вы спрашиваете

какая логика стоит за этим?

Часть ответа просто в том, что полезно иметь символы в выделенном списке. Я не могу ответить на вопрос окончательно, не зная больше о конкретном компиляторе. Мое лучшее предположение состоит в том, что запись prev будет использоваться для реализации вложенных областей (скобки { ... } в C), но это предположение основано на компиляторах, которые я видел или работал над ними. Так что, возможно, логика заключается в том, что когда встречается закрывающая фигурная скобка, компилятор может следовать по этой ссылке, пока не достигнет ste во вложенной области видимости. Люди с чуть большим опытом, чем автор изучаемого вами компилятора, обычно помещают эту логику в «абстракцию таблицы символов», которая будет включать такие функции, как enterscope() и exitscope(), и детали этих операций будут скрыт от внутреннего представления отдельных записей таблицы символов.

1 голос
/ 26 декабря 2009

Моя первая мысль об использовании связанного списка в обратном направлении была бы для тех языков, которые поддерживают переопределение имен переменных, таких как: 

int main (void) {
    int x = 1;
    int y = 1;
    if (x == 1) {
        int y = 2;
        printf ("y = %d\n", y);
    }
    return 0;
}

В этом случае вам нужен доступ к переменной с самой внутренней областью (последней определенной). Это можно найти, пройдя назад по списку (при условии, что вы строите список, конечно, продвигаясь вперед).

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

Конечно, вы могли бы достичь того же эффекта, вставляя перед текущей головой, а не добавляя в конец списка (что выглядит концептуально , что делается, просто с указателем prev вместо next).

...