Запись владельца в таблицах символов - PullRequest
Новая
       58

Запись владельца в таблицах символов

2 голосов
/ 08 мая 2020

Я реализую таблицу символов, как описано в книге драконов : 

class SymbolTable {
    std::unordered_map<std::string, Record> table;
    SymbolTable* parent;

public:
    SymbolTable(SymbolTable* p) : parent{p} {}

    const Record* lookUp(const std::string& name) const {
        for (auto* scope = this; scope != nullptr; scope = scope->parent) {
            auto iter = scope->table.find(name);
            if (iter != cend(scope->table))
                return &iter->second;
        }
        return nullptr;
    }

    bool insert(const std::string& name, const Record& record) { 
        return names.insert({name, record}).second; 
    }
};

Однако я не уверен, как хранить данные записи. Кому должна принадлежать информация о типе? Должен ли Record содержать указатель, не являющийся владельцем, на тип, уже сохраненный в AST?

Кроме того, я хотел бы сохранить свою таблицу символов для последующих проходов компилятора. Cooper & Torczon кратко упоминает прямую вставку указателей на соответствующий SymbolTable в узле AST. Это общий подход?

1 Ответ

2 голосов
/ 08 мая 2020

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

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

Наиболее распространенным шаблоном является то, что тип структуры содержит список члены, каждый со своим типом. Этот список элементов, по сути, является таблицей символов, поскольку для анализа ссылки на член, например r.a.b.c, вам нужно найти a в элементах r, а затем b в r.a ' s участников и так далее. Это предполагает, что тип структуры содержит символьную таблицу членов (которая может быть указателем, а может и не быть указателем, в зависимости от вашего дизайна. Обычно списки элементов структуры не являются общими, но в случае отношений подкласса / суперкласса OO поиск элементов может быть более сложным.)

Думаю, я пытаюсь здесь подчеркнуть, что структура вашей таблицы символов во многом зависит от природы вашего языка. По сути, таблица символов содержит список символов, организованный таким образом, чтобы можно было эффективно искать символ по его имени. Таблица символов связывает каждый символ с некоторым объектом данных символа, который может варьироваться от типа таблицы символов к типу таблицы символов (например, с использованием универсальных шаблонов C ++) или может быть согласованным для всех таблиц символов. Часто таблицы символов отличаются от простых таблиц ha sh (или ассоциативных контейнеров) тем, что символы также имеют некоторый линейный порядок, используемый для создания линейного представления во время компиляции. Точные детали могут отличаться, но возможность перебирать символы в последовательном, четко определенном порядке часто является важной особенностью.

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

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

Таблицы символов не всегда связаны между собой простыми способами, которые можно легко выразить как собственность. В этом они похожи на другие внутренние объекты, плавающие в компиляторе. Узел AST может внезапно стать общим узлом в графе, а не узлом дерева, как только вы начнете реализовывать оптимизацию общих подвыражений. (И это только один пример.) Насколько я знаю, большинство компиляторов любой сложности в конечном итоге реализуют своего рода сборку мусора для внутренних объектов, если, конечно, компилятор не написан на языке с общей сборкой мусора.

...