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

Question

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

т.е.

int x = 5 
int x = 5 

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

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

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

Answer 1

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

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

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

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

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, чтобы получить значение функции. Это легко реализовать в модели I, описанной выше, путем хранения нескольких стеков Scope - по одному для каждого пространства имен.

Answer 2

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

Answer 3

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

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

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

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

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

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