Skip to content

Latest commit

 

History

History
139 lines (95 loc) · 5.96 KB

04-symbol-tables.md

File metadata and controls

139 lines (95 loc) · 5.96 KB

4. Symbol Table

Перед разработчиком компилятора (пока что интерпретатора) стоит следующая задача:

Где хранить и как обращаться с переменными и функциями?

Рассмотрим пример:

fun f x = 2 * x;

fun main argc argv = f(0);

Попытаемся представить себе, какое поведение мы бы ожидали от такого кода (пока что считаем, что вызывать можно только по имени).

    =========        ================
    | f | x |        | main | argc, |
    +++++++++        |      | argv  |
    |   *   |        ++++++++++++++++
    |  / \  |        |              |
    | 2   x |        |   CALL `f`   |
    =========        |      |       |
                     |      0       |
                     |              |
                     ================

В зависимости от задачи можно представить себе что-то такое:

Typechecker Interpreter
Найти тип f Найти тело f
x ← 0
compare(f_ty, f_args) eval(f->body)

Сформулируем задачу: необходимо по идентификатору находить информацию о символе. В компиляторе этой задачей занимается таблица символов.

API

Какие операции мы бы хотели от таблицы символов?

Method Type Description
lookup Name -> Symbol* Достать символ из таблицы
bind Name -> Symbol -> () Положить символ в текущий scope
enter -> () Создать новый слой таблицы символов, подвесить его к текущему
exit -> () Вернутся в предыдущий scope

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

Symbol Table Builder

Чтобы поддерживать семантику языка Étude, вам предлагается сделать построение таблицы символов отдельным проходом компилятора. Это будет иметь эффект того, что все символы в программе оживают одновременно. Тогда в языке нет необходимости иметь forward declaration, как в Си или OCaml.

Shadowing

Поддерживайте shadowing переменных — переопределение переменных с тем же именем во вложенном scope.

    fun f x y z = {              # <<------ 0:f (x | y | z)

        var x = y + z;           # <<------ 0:f:0 (x)

        {
            var z = x + y;
        };      # <<------ 0:f:0:0 (z)

        {
            var y = x + z;
        };      # <<------ 0:f:0:1 (y)

    };

Что произойдет в вашей реализации при исполнении подобного кода?

    var a = 1;

    {
        var a = a + 2;
        print(a);
    }

Related: Let Expression

Задание

  1. Прочитайте часть главы про scope Crafting Interpreters: Scope
  2. Придумайте как и что хранить в структуре Symbol.
  3. Реализуйте древесную структуру Scope-ов c указателями на родителей.
  4. Создайте SymbolTableBuilder—visitor

Playground

  1. Используя похожие идеи поддержите в интерпретаторе state и функции

В слудующей главе интерпретатор превратится в Typecheker.

Реализация

Будьте осторожны и избегайте циклических зависимостей между Symbol, Context, ScopeLayer

Комментарии

Типы определяемых выражений x: Int и их тела f → x + 2 хранятся в таблице символов. С другой стороны, для кодогенерации тоже удобно знать, какого типа является выражение, поэтому я также храню указатель на тип прямо в AST. Related: Trees That Grow

В таком простом языке как Étude даже нет необходимости для каких-то сложных манипуляций. В большинстве случаев мы хотим от binding-a только его тело. Прочитайте, например, как хранят информацию в компиляоре язка Haskell GHC: No Symbol Table

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

Ключевые слова: lexical scope, shadowing, symbol table, lookup, binding, cactus stack.