Создание интерпретатора языка игрушек, переменных и областей AST

Question

как и в названии, я недавно начал работать с парсером / интерпретатором в c ++ с другом, который позже будет интегрирован в более крупный проект (если он будет работать);мы решили начать создавать классы, которые мы будем использовать для абстрактного синтаксического дерева, и позже мы будем работать над соответствующей стороной синтаксического анализатора.Мы начали с понятий области и переменной.Выполнив некоторый поиск, мы нашли пример, в котором каждая область имеет таблицу символов и ссылку на предыдущую область, поэтому, если переменная не найдена в текущей области, она будет выглядеть в верхней и так далее.Первое, на что я должен был обратить внимание в этом примере, это то, что попытка получить доступ к переменной, которая имеет много областей действия в стеке или даже не существует, будет иметь высокую стоимость (в худшем случае сценарий достигает глубины стека).Я был как ... нет, мы можем добиться большего успеха.

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

map<string, stack<variable>> table;

тогда каждая область будет содержать набор строк, которые будут теми, которые выделены в этой области

set<string> allocated;

Когда переменная "a" размещена, добавляется строка ее именив этот локальный набор областей действия, то новая переменная помещается в таблицу e (таблица ["a"]. push ()).Чтобы получить доступ к этой переменной для редактирования или чтения, нужно выполнить чтение верхней части той же позиции (таблица ["a"]. Top ()) И, наконец, деструктор области действия будет циклически перебирать все расположенные элементы и извлекать их из стеков карты.

for(variable_name in allocated)
    {
    table[variable_name].pop();
    }

Этот способ будет делать выделение, чтение и запись O (1) в любом случае.Вот два моих вопроса:

1) Нужно ли сохранять строки для каждой переменной как в таблице, так и в области видимости, вместе с необходимостью проходить через все из них в конце области видимости, неэффективно, по сравнениюк системе с множеством таблиц, которая должна была бы просто удалить массив?

2) Пример, который я нашел, был не очень эффективным, потому что он был очень уроком для начинающих, или есть кое-что, что яне хватает того, что делает его более ценным, чем идея, предложенная мной и моим другом?

Answer 1

Здесь нет абсолютного ответа;это зависит от конкретной области видимости в вашем языке, а также от вашего стиля программирования.Мой совет - сначала запустите его, а затем посмотрите, нужно ли его улучшить.Что бы вы ни выбрали в качестве реализации таблицы символов, убедитесь, что скрыли детали реализации за прототипом ADT, который определит поведение таблицы символов.Тогда вы можете легко заменить другую реализацию, если вам нужно.

В любом случае, вот несколько точек данных:

1. Вложение области обычно не очень глубокое.Действительно, для большинства языков области с глубоким вложением считаются плохим стилем.

2. В любом случае ваше предложение предусматривает создание хеш-таблицы для каждой области.Это не совсем необходимо;Вы можете сделать все это с помощью одной хеш-таблицы для всех поисков и стека, чтобы отметить границы области видимости.Таблица символов представляет собой unordered_map<name, definition>, а стек области действия - stack<pair<name, definition>>.(Я предполагаю, что C ++. Здесь name может быть просто псевдонимом для std::string, но см. Ниже. definition содержит метаданные, которые вам нужно хранить для каждого символа. Не нужно хранить их отдельно, вот так; выможет использовать один тип, а затем использовать set вместо map.) definition в стеке области действия - это определение некоторой внешней области или указание на то, что во внешней области переменная не определена.Также должно быть значение часового (для имени или определения), которое указывает начало области.

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

3. Существует множество различных видов областей действия вТипичный язык.Вот несколько примеров:

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

   • Глобальная область действия и / или модульприцелы.

   • Области имен составного объекта ("класса").Они не вкладываются так, как это делают блочные области, но, в зависимости от алгоритма поиска имени вашего языка, они все равно могут быть частью поиска по цепочке имен.

4. Очевидно, проще создавать имена std::string объектов, но в итоге вы создадите очень много дублирующих строк, которые должны быть строками по сравнению с другими строками.Современные компьютеры достаточно быстры, чтобы ничего не значило, но вы все равно можете подумать об их оптимизации.Я предпочитаю «интернировать» строки, помещая их в std::set<std::string> (или эквивалентный), а затем используя указатели элементов вместо самой строки.Это имеет два преимущества:

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

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