Грамматика как структура графа
Компилятор переводит исходный код, строя дерево разбора — корневое дерево, где каждый узел представляет применённое правило грамматики, а каждый лист представляет терминальный символ (имя переменной, литерал, оператор).
Геометрия деревьев
Дерево с n узлами и n−1 рёбрами. Глубина d: максимальное расстояние от корня до любого листа. Для сбалансированного бинарного дерева глубины d: до 2^d листьев и 2^(d+1)−1 всего узлов.
Деревья разбора типичных выражений не сбалансированы: приоритет операторов создаёт асимметричные деревья, смещённые вправо или влево. A + B C создаёт дерево, где глубже, чем +, кодируя, что * связывает более тесно.
BNF и ALGOL
Форма Бэкуса—Наура (BNF), изобретённая для определения ALGOL, формализует грамматику как правила продукции:
``
<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>
<factor> ::= id | (<expr>)
``
Каждое правило продукции определяет один уровень дерева. Грамматика — это ориентированный граф на нетерминальных символах; анализ предложения прослеживает путь через этот граф от начального символа к листьям.
Глубина дерева разбора и сложность выражений
Для выражения (A + B) * (C + D) дерево разбора имеет определённую структуру при стандартном приоритете операторов.
Глубина дерева разбора влияет на производительность компилятора: более глубокие деревья требуют больше кадров стека при синтаксическом анализе методом рекурсивного спуска.
Энтропия Шеннона и избыточность
Хэмминг заметил, что устная речь ~60% избыточна, письменная ~40%. Это имеет точное информационно-теоретическое значение.
Энтропия Шеннона
Для источника, генерирующего символы из алфавита A с вероятностями {p₁, p₂, ..., pₙ}:
H = −Σ pᵢ log₂(pᵢ) (bits per symbol)
Максимальная энтропия: равномерное распределение (все символы равновероятны). H_max = log₂(n) для n символов.
Избыточность R: доля битов, которые не несут информацию (могут быть удалены без потери содержания):
R = 1 − H / H_max
Если R = 0.4 (40% избыточна): 40% битов можно предсказать из контекста. Канал, несущий английский текст на 8 бит/символ, использует только 60% своей информационной ёмкости; 40% — это структура, которую получатель уже знает.
Обнаружение ошибок использует избыточность: если 40% битов предсказуемы, ошибка передачи может произвести последовательность, нарушающую структуру избыточности — обнаруживаемую даже без кодов коррекции ошибок.
Почти нулевая избыточность APL: изменение одного символа почти никогда не обнаруживается из контекста. 60% избыточность английского: часто можно восстановить слово из окружающего контекста, даже если буква отсутствует или неверна.
Вычисление избыточности
Частота букв английского языка (приблизительно): 'e' появляется ~12.7% времени; 'z' появляется ~0.07%. Фактическая энтропия английского приблизительно H ≈ 1.0 бит/символ (с учётом контекста на уровне слов). Максимальная энтропия для 26-буквенного алфавита: H_max = log₂(26) ≈ 4.70 бит/символ.
Кривые роста как геометрия
Алгоритмы компилятора обрабатывают программы размером n (токены, строки или узлы). Выбор алгоритма определяет, как время компиляции масштабируется с размером программы.
Общие классы сложности
| Класс | Время выполнения | Пример | |---|---|---| | O(n) | линейная | лексический анализ | | O(n log n) | квазилинейная | оптимальная сортировка | | O(n²) | квадратичная | наивное обнаружение дубликатов | | O(n³) | кубическая | умножение матриц, анализ CYK | | O(2ⁿ) | экспоненциальная | наивное доказательство теорем |
Геометрическая картина: нанесите время выполнения в зависимости от n. O(n) — это линия. O(n²) — это парабола. O(2ⁿ) — это экспоненциальная кривая, которая выглядит плоской вблизи n=0 и почти вертикальной вблизи n=50.
Анализ общей контекстно-свободной грамматики (алгоритм CYK) выполняется за O(n³). Для большинства практических языков программирования грамматика разработана так, чтобы быть LR(1)-анализируемой, позволяя O(n) анализ. Грамматика ALGOL была сложнее, чем FORTRAN, что способствовало более медленным компиляторам — практическое трение, которое имело значение в 1958 году, когда компиляция занимала часы.
Точки пересечения
Наивный поиск в таблице символов использует O(n²) всего операций для программы с n идентификаторами (линейный поиск для каждого из n поисков). Таблица символов хеш-таблицы использует O(n) ожидаемого количества операций.
Предположим: алгоритм O(n²) выполняется на скорости 10⁶ операций/сек на оборудовании 1958 года. Алгоритм O(n) выполняется с той же скоростью, но требует 100n операций настройки (построение хеш-таблицы).