Проверка типов данных / структур в парсере

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

int x = 5
int x = 5

И это будет правильно, так будет ли парсер проверять, был ли x уже определен? Если так, я бы использовал hashmap? И какую информацию мне нужно хранить, например, как я могу обрабатывать область видимости переменной, поскольку x может быть определен в функции в локальной и глобальной области видимости:

int x = 5;
void main() {
    int x = 2;
}

И наконец, когда я сохраняю в hashmap, как я могу различать типы? Например, я мог бы иметь переменную с именем fooи структура также называется foo, Поэтому, когда я ставлю foo в hashmap это, вероятно, вызовет некоторые ошибки. Я думаю, что я мог бы префикс это, как хранение этого в качестве ключа хеш-карты для структуры struct_xyz где xyz это имя структуры, а для переменных int_xyz? Спасибо:)

Источник

3 ответа

Решение

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

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

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

Символы хранятся в структуре, которая выглядит примерно так:

typedef struct symbol {
    char  *name;
    Type  *type;
    Scope *scope; // Points to the scope in which the symbol was defined.
} Symbol;

И что это Scope вещь? Язык, который я компилирую, имеет лексическую область, и каждое определение функции, блок и т. Д. Вводит новую область видимости. Области действия образуют стек, нижний элемент которого является глобальной областью действия. Вот структура:

typedef struct scope {
    struct scope *parent;
    Symbol *buckets;
    size_t  nbuckets;
} Scope;

buckets а также nbuckets поля представляют собой хэш-карту идентификаторов (строк) Symbol указатели. Следуя parent С помощью указателей можно пройтись по стеку при поиске идентификатора.

При наличии структур данных легко написать синтаксический анализатор, который разрешает имена в соответствии с правилами лексической области видимости.

  1. При обнаружении оператора или объявления, которое вводит новую область видимости (например, объявление функции или оператор блока), синтаксический анализатор выдвигает новую Scope в стек. Новая сфера parent поле указывает на старую область видимости.
  2. Когда анализатор видит идентификатор, он пытается найти его в текущей области видимости. Если поиск не выполняется в текущей области, он рекурсивно продолжается в parent объем и т. д. Если не соответствует Symbol может быть найдена ошибка. Если поиск успешен, парсер создает узел AST с указателем на символ.
  3. Наконец, когда встречается объявление переменной или функции, оно привязывается к текущей области.

Некоторые языки используют более одного пространства имен. Например, в Erlang функции и переменные занимают разные пространства имен, что требует неудобного синтаксиса, такого как fun foo:bar/1 чтобы получить значение функции. Это легко реализуется в модели, которую я изложил выше, сохраняя несколько Scope стеки - по одному для каждого пространства имен.

Источник

Если мы определим "область действия" или "контекст" как отображение имен переменных на типы (и, возможно, некоторую дополнительную информацию, такую ​​как глубина области действия), то естественной реализацией будет либо hashmap, либо какое-то дерево поиска. При достижении любого определения переменной компилятор должен вставить имя с соответствующим типом в эту структуру данных. Когда встречается какой-то оператор "конечной области", у нас уже должно быть достаточно информации для "возврата" изменений в этом отображении в его предыдущее состояние.

Для реализации hashmap, для каждого определения переменной мы можем сохранить предыдущее отображение для этого имени и восстановить это отображение, когда мы достигли оператора 'end of scope'. Мы должны хранить стек стеков этих изменений (один стек для каждой открытой в данный момент области) и возвращать самый верхний стек изменений в конец каждой области.

Одним из недостатков этого подхода является то, что мы должны либо завершить компиляцию за один проход, либо сохранить отображение для каждого идентификатора в программе где-либо, поскольку мы не можем проверять какую-либо область действия более одного раза или в порядке, отличном от порядка появления в исходном файле. (или АСТ).

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

"Глубина охвата" достаточна для того, чтобы выбрать, что делать в ситуации, когда имя новой переменной конфликтует с именем, уже находящимся в отображении. Просто проверьте old depth < new depth и перезаписать при успехе, или сообщить об ошибке при сбое.

Чтобы различать имена функций и переменных, вы можете использовать отдельные (но похожие или одинаковые) отображения для этих объектов. Если какой-то контекст разрешает только функцию или только имя переменной, вы уже знаете, где искать. Если оба допускаются в каком-то контексте, выполните поиск в обеих структурах и сообщите "ошибку неоднозначности", если имя соответствует функции и переменной одновременно.

Источник

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

Источник
Другие вопросы по тегам