Таблица символов и области видимости

Сценарий: два разработчика написали функции `process()` в разных файлах проекта. Как компилятор понимает, какую именно функцию вызывает каждая строчка кода? Ответ - таблица символов. Без неё компилятор слеп: он видит имена, но не знает, что за ними стоит.

• **TypeScript compiler** хранит 400+ тысяч символов при компиляции крупного monorepo - именно из этой таблицы VS Code берёт автодополнение и 'Go to Definition' за ~1ms.
• **GCC** с `-g` включает отладочную информацию на основе таблицы символов - без неё `gdb` не смог бы показать имена переменных, только адреса в памяти.
• **Линковщик (ld/lld)** - это тоже resolver символов: он сшивает таблицы символов из разных `.o`-файлов, разрешая cross-file references и сообщая 'undefined symbol' когда что-то не найдено.

Symbol Table

Таблица символов (symbol table) - центральная структура данных семантического анализатора. Она отображает имена идентификаторов на их атрибуты: тип, область видимости, адрес, смещение в стеке. Без неё компилятор не может различить переменную `x` из одной функции и `x` из другой.

GCC хранит символы в хэш-таблице `binding_level`, Clang использует `DeclContext` - иерархию контекстов объявлений. Rustc строит таблицу символов в фазе name resolution (passes `resolve::Resolver`) до проверки типов. TypeScript compiler собирает символы в `SymbolTable` - это буквально `Map<string, Symbol>`, где `Symbol` хранит флаги (variable, function, class), тип и список объявлений.

Таблица символов строится за один (или несколько) проходов по AST. В C++ из-за шаблонов и ADL (argument-dependent lookup) компилятор вынужден делать многопроходный анализ - именно это делает Clang значительно сложнее, чем компиляторы более простых языков.

Scope Stack

Вложенные области видимости реализуются стеком скоупов. При входе в блок (`{`) компилятор делает push нового скоупа, при выходе - pop. Поиск символа начинается с вершины стека и идёт вглубь до глобального скоупа.

GCC реализует это через `binding_level` - связный список с указателем `level_chain` на родительский скоуп. Clang использует `Sema::PushFunctionScope()` / `PopFunctionScope()` - пара вызовов оборачивает каждый новый контекст. В Rust `Resolver` хранит `Rib` (ребро) для каждого вложенного скоупа: `fn_item_ribs`, `label_ribs`, `lifetime_ribs` - разные стеки для разных namespace.

Python реализует LEGB rule (Local, Enclosing, Global, Builtin) - это ровно тот же стек скоупов, но с фиксированными четырьмя уровнями поиска. JavaScript до ES6 имел только function-scoped переменные (`var`), что упрощало стек; `let`/`const` добавили block-scoping и сделали поведение ближе к C/Java.

Name Resolution

Name resolution - процесс связывания каждого использования имени с конкретным объявлением. Это происходит раньше type checking: сначала компилятор выясняет, что именно обозначает `foo` в данной точке кода, и только потом проверяет типы.

В простых языках resolution - линейный поиск по стеку скоупов. В C++ всё значительно сложнее: есть qualified lookup (`std::vector`), ADL (Koenig lookup), template-dependent name lookup (имена внутри шаблонов резолвятся дважды - при определении и при инстанциации). Именно из-за двухфазного lookup `template <typename T> void f() { g(T{}); }` - `g` может быть незнакомой функцией в момент определения шаблона.

TypeScript compiler делает name resolution в `binder.ts` (фаза bind), производя `Symbol` для каждого объявления. Затем в `checker.ts` каждое использование имени через `resolveEntityName()` связывается с символом. Это позволяет IDE (через Language Server Protocol) мгновенно показывать 'Go to Definition' - просто переход по уже готовой карте.

Shadowing

Shadowing происходит, когда переменная во внутреннем скоупе объявляется с тем же именем, что и переменная во внешнем. Внутренняя 'затеняет' внешнюю - name resolution возвращает внутренний символ, внешний становится временно недоступен.

Shadowing - гибкий инструмент в Rust: позволяет 'трансформировать' переменную через несколько шагов, меняя тип без введения новых имён. Паттерн `let x = x.parse::<i32>()?.abs();` широко используется в production-коде. В отличие от мутации, каждый `let x` создаёт новую переменную - старая дропается при выходе из скоупа.

Ключевые идеи

• **Таблица символов** - структура данных, связывающая имена с их атрибутами (тип, скоуп, смещение). Строится при обходе AST до type checking.
• **Стек скоупов** - механизм вложенных областей видимости: push при входе в блок, pop при выходе. Поиск идёт от вершины вглубь.
• **Name resolution** связывает каждое использование имени с конкретным объявлением (DefId в Rust, Symbol в TypeScript). Ошибки resolution - 'undefined variable' и 'ambiguous reference'.
• **Shadowing** - легальное объявление переменной с уже занятым именем во внутреннем скоупе. В Rust это идиоматично; в C++ компилятор предупреждает с `-Wshadow`.

Связанные темы

Таблица символов - фундамент, на котором строятся все последующие фазы компилятора:

• Проверка типов — Type checker читает типы из таблицы символов и записывает выведенные типы обратно
• Семантические ошибки — Большинство семантических ошибок (use-before-define, redeclaration) обнаруживаются при построении таблицы символов
• Линковка — Линковщик объединяет таблицы символов из разных объектных файлов, решая cross-module references

Вопросы для размышления

• Python ищет имена по LEGB rule при каждом обращении в runtime, а не при компиляции. Какие преимущества и недостатки это даёт по сравнению со статическим name resolution?
• В C++ функция может быть объявлена после использования (forward declaration). Как это влияет на построение таблицы символов - нужен ли дополнительный проход по AST?
• Rust запрещает использование переменной до её объявления в одной функции, но позволяет функциям вызывать друг друга рекурсивно. Как resolver обрабатывает эту асимметрию?

Связанные уроки

• ds-06-hash-intro