Грамматика как структура граф
Компилятор преобразует исходный код, создавая дерево разбора - корневое дерево, в каждом узле которого представлена примененная грамматическая правило, а каждая листовая вершина представляет терминальный символ (имя переменной, литерал, оператор).
Геометрия дерева
Дерево с n узлов и n-1 рёбер. Глубина d: максимальное расстояние от корня до любой листовой вершины. Для сбалансированного бинарного дерева глубины d: до 2^d листьев и 2^(d+1)-1 всего узлов.
Дерева разбора для типичных выражений не сбалансированы: предопределенность операторов создает правосторонние или левосторонние деревья. A + B C создает дерево, где глубже, чем +, кодируя, что * имеет более высокий приоритет.
BNF & ALGOL
Backus-Naur Form (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ᵢ) (бит на символ)
Максимальная энтропия: равномерное распределение (все символы одинаково вероятны). 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ⁿ) | экспоненциальное | простое доказательство теоремы |
Геометрическое изображение: нарисуйте время выполнения по оси Y и n по оси X. 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 операций настройки (создание хеш-таблицы).