AST: абстрактное синтаксическое дерево

Каждый раз когда VS Code подсвечивает ошибку типов, предлагает автодополнение, или переименовывает переменную во всём проекте - это работает TypeScript Language Server на AST. Миллиарды строк JavaScript кода в Facebook мигрировали с jQuery на React через один codemod, работающий на AST. AST - скрытый движок современной разработки.

• Babel transforms: JSX -> React.createElement через AST visitor - каждое приложение на React
• ESLint: 200+ стандартных правил - каждое это visitor на AST узлах
• Prettier: форматирование через AST - убирает все оригинальные пробелы и генерирует новые
• TypeScript: проверка типов - два прохода через AST: parsing + type checking

AST vs CST: что выбросить и почему

**CST (Concrete Syntax Tree)** - дерево точно соответствующее грамматике. Каждый токен - узел. `1 + 2 * 3` с CST включает скобки, точки с запятой, ключевые слова как отдельные узлы. **AST (Abstract Syntax Tree)** выбрасывает всё что несущественно для семантики. Остаётся только структура программы.

**Babel, TypeScript, ESLint** используют AST для трансформации и анализа JavaScript. Babel transforms: JSX -> React.createElement, TypeScript types -> JavaScript. ESLint rules: обходят AST и проверяют паттерны. Prettier: форматирует код через AST (print через printer).

Узлы AST: типы и структура

Каждый узел AST имеет тип (discriminated union в TypeScript) и специфичные поля. Стандарт **ESTree** определяет структуру AST для JavaScript - его используют Acorn, Esprima, Babel parser. Это позволяет инструментам (ESLint, Prettier, Babel) работать с любым парсером.

Visitor Pattern: обход и трансформация AST

**Visitor Pattern** позволяет добавлять операции над AST без изменения самих узлов. Каждый узел вызывает `visitor.visit(this)`, visitor знает как обрабатывать каждый тип узла. Babel плагины - это именно visitor'ы: каждый плагин регистрирует обработчики типов узлов.

AST в инструментах: Babel, ESLint, codemods

**ast-grep** - новый инструмент (2023) для структурного поиска по коду через AST паттерны. Как grep, но понимающий синтаксис. `$X.map($Y)` найдёт все вызовы .map() независимо от форматирования. Используется в крупных codemod'ах (Facebook Codemod, ReactMods).

**Language Server Protocol (LSP)** - IDE функции (go-to-definition, rename, autocomplete) работают на AST. TypeScript Language Server строит полный AST с типами для каждого файла и обновляет его инкрементально при каждом нажатии клавиши. Весь VS Code TypeScript support - это один LSP сервер работающий на AST.

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

• AST vs CST: AST выбрасывает пунктуацию и промежуточные грамматические узлы
• ESTree: стандарт структуры AST для JavaScript - один формат для Babel, ESLint, Prettier
• Visitor Pattern: добавляем операции без изменения узлов - каждый плагин это visitor
• Codemod: AST-based рефакторинг надёжнее regex - знает синтаксис и контекст
• LSP: IDE features работают на непрерывно обновляемом AST с типами

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

AST - центральная структура данных компилятора, на которой строится весь последующий анализ.

• Pratt Parser — Pratt Parser строит AST выражений через led/nud обработчики
• Таблица символов — Symbol table строится при обходе AST - первый семантический анализ
• Проверка типов — Type checker - visitor по AST, аннотирующий узлы типами

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

• Как реализовать инкрементальное обновление AST при редактировании файла в IDE (не перепарсировать весь файл)?
• Что такое 'source maps' и как AST transform поддерживает маппинг позиций в исходном коде?
• Как ast-grep и структурный поиск отличается от regexp в применении к больших codebase миграциям?

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

• comp-15-pratt-parser — Pratt Parser строит AST - этот урок его изучает
• comp-17-symbol-table — Таблица символов заполняется при обходе AST
• comp-18-type-checking — Проверка типов работает на AST через type visitor
• comp-11-recursive-descent — Recursive descent - первый парсер, строящий AST
• plt-26-ast