Как компьютер читает код

Джон Бэкус и первый настоящий компилятор

В 1957 году команда Джона Бэкуса в IBM выпустила первый FORTRAN-компилятор. До этого все программы писались на ассемблере вручную. Коллеги скептически называли проект 'игрой в слова' - они не верили, что машина может генерировать код не хуже человека. FORTRAN-компилятор опроверг скептиков: сгенерированный код был почти столь же эффективен, как написанный вручную. Бэкус также изобрёл нотацию BNF (Backus-Naur Form) - стандартный способ записи грамматик языков программирования.

Цели урока

• Понимать, что исходный код - это поток байтов, и как кодировка определяет маппинг символов
• Объяснить роль lexer: группировка символов в токены с учётом позиции
• Различать Parse Tree и AST, строить AST для арифметических выражений
• Понимать, как codegen транслирует AST в машинные инструкции, роль линковщика

Каждая строка Python, каждый компонент React, каждый запрос к Rust backend - всё это проходит через один и тот же конвейер. LLVM компилирует 60+ языков. V8 JIT-компилирует JavaScript в нативный код в 100 раз быстрее интерпретации. За этим разнообразием стоит одна архитектура: символы -> токены -> AST -> IR -> машинный код.

• **V8 (Google Chrome, Node.js)** - JIT-компилирует JS через AST -> Ignition bytecode -> TurboFan machine code. Один и тот же pipeline что у GCC
• **LLVM** - backend, который компилирует Rust, Swift, C++, Julia, Kotlin/Native. 60+ frontend-языков, один IR
• **TypeScript compiler (tsc)** - полный pipeline: lexer -> parser -> type checker -> emitter. 100K+ строк TypeScript
• **Python bytecode** - CPython компилирует в .pyc (байткод), который выполняет виртуальная машина. `dis.dis(func)` показывает результат
• **ESLint/Prettier/Babel** - все работают через AST-трансформации. Плагин ESLint - это visitor по узлам AST

Предварительные знания

• Что такое компилятор

Исходный код как поток символов

**LLVM компилирует Rust, C++, Swift, Julia и ещё 60 языков.** Разные синтаксисы, разные семантики - а pipeline один. Потому что все эти языки на входе одинаковые: поток байтов. `x = 42 + y` для компилятора - это `78 20 3D 20 34 32 20 2B 20 79`. Ни переменных, ни операторов - просто числа. Задача первой фазы - восстановить **структуру и смысл** из этого потока.

**Кодировка** определяет, как символы превращаются в байты. ASCII - 1 байт (128 символов). UTF-8 - от 1 до 4 байт (все символы Unicode). Python 3, Rust, Go, Swift работают с UTF-8. GCC поддерживает файлы в других кодировках через `-finput-charset`.

Компилятор читает файл **последовательно**, символ за символом, слева направо, сверху вниз. Поддерживается **позиция** (строка:столбец) для сообщений об ошибках. Когда видно `error at line 42, column 15` - это работа трекера позиции в lexer.

BOM (Byte Order Mark) - невидимый символ `U+FEFF` в начале UTF-8 файла. Некоторые редакторы (Notepad на Windows) добавляют его автоматически. Многие загадочные баги 'код выглядит правильно, но не компилируется' вызваны невидимыми Unicode-символами.

Токены: атомы языка

**Lexical analysis (lexing)** - первая фаза компилятора. Lexer группирует символы в **токены** - минимальные смысловые единицы языка. Clang и GCC пишут lexer вручную через switch/case: регулярные выражения дают правильный результат, но production-компиляторам нужна скорость обработки миллионов строк в секунду. Tree-sitter, который использует VS Code для навигации по коду - incremental lexer: при изменении одной строки перетокенизирует только изменённый фрагмент.

**Порядок правил важен!** Keyword `if` должен проверяться *до* общего паттерна идентификатора `[a-zA-Z_]\w*`, иначе `if` распознается как обычный идентификатор. Используйте `\b` (word boundary) для keywords, чтобы `iffy` не токенизировалось как `if` + `fy`.

AST: дерево выражений

Список токенов - плоский. Он не отражает **структуру**: что `*` выполняется раньше `+`, что `if` управляет блоком кода. **Parser** строит из токенов **AST** (Abstract Syntax Tree) - дерево, которое отражает иерархию выражений. ESLint, Prettier, Babel, TypeScript compiler - все работают через AST-трансформации. Rust proc-macros получают AST на входе и возвращают AST на выходе.

**Приоритет операций** закодирован в структуре дерева: `*` ниже в дереве чем `+`, значит вычисляется первым (от листьев к корню). Скобки `(2 + 3) * 4` меняют структуру: `+` опускается ниже `*`. В Python: `import ast; print(ast.dump(ast.parse('x = 2 + 3 * 4')))` - реальный AST за одну строку.

AST реального кода можно увидеть прямо сейчас: в Python `import ast; ast.dump(ast.parse(...))`, в Rust `cargo expand`, в Clang `clang -Xclang -ast-dump -fsyntax-only file.c`.

От AST к машинному коду

AST - последнее представление, понятное человеку. Дальше компилятор переводит его в **машинный код** - последовательность инструкций, которые процессор выполняет напрямую. GCC тратит ~60% времени компиляции на backend-фазы: register allocation, instruction selection, scheduling. LLVM вынес это в переиспользуемую библиотеку - поэтому Rust, Swift, Julia имеют одинаковое качество оптимизаций.

Реальная генерация кода значительно сложнее: calling conventions (какие аргументы в каких регистрах), alignment памяти, ABI-совместимость, exception handling. GCC тратит ~60% времени компиляции на backend-фазы.

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

• Исходный код - поток байтов. Кодировка (UTF-8) определяет маппинг символов в байты
• **Lexer** группирует символы в **токены** - минимальные единицы языка. Clang/GCC пишут lexer вручную для скорости, Tree-sitter делает его инкрементальным для IDE
• **Parser** строит **AST** из токенов. Структура дерева кодирует приоритет операций. Скобки в AST не нужны - они уже в форме дерева
• **Codegen** переводит AST в машинные инструкции. **Линковщик** собирает object files, разрешая ссылки между модулями
• LLVM вынес весь backend в переиспользуемую библиотеку - 60+ языков получают одинаковое качество оптимизаций
• Parse Tree содержит все грамматические детали, AST - только операции и значения. Компиляторы работают с AST

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

Каждый этап pipeline раскрывается в отдельных уроках:

• Архитектура компилятора — Как организованы passes и pipeline, через которые проходит код
• Основы Lexer — Полная реализация lexer с обработкой ошибок, строк, комментариев
• Context-Free грамматики — Формальные правила, по которым parser строит AST

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

• Lexer разбивает `>=` на один токен (GTE) или два (`>` и `=`)? Как lexer решает, что делать? Подсказка: maximal munch rule.
• Можно ли построить компилятор без AST - генерировать машинный код прямо из токенов? Какие ограничения это создаст?
• Почему реальные компиляторы (GCC, Clang) пишут lexer вручную, а не используют regex? Подсказка: скорость и обработка контекста.

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

• comp-03-compiler-architecture — Passes и pipeline - следующий уровень после базовых фаз
• comp-06-lexer-basics — Полная реализация lexer с обработкой ошибок
• comp-10-cfg — Формальные грамматики - основа парсеров
• fl-02-chomsky — Иерархия Хомского объясняет мощность lexer vs parser
• arch-05-instruction-cycle — Машинный код выполняется по instruction cycle CPU
• comp-33-v8 — V8 - production пример JIT на базе этого pipeline
• fl-01-intro