Граматика як структура графа
Компілятор перетворює вихідний код, будуючи дерево розбору — кореневе дерево, де кожен вузол представляє застосовану граматичну правило, а кожне листя представляє термінальний символ (назва змінної, літерал, оператор).
Геометрія дерева
Дерево з 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ᵢ) (біти на символ)
Максимальна ентропія: рівномірний розподіл (всі символи рівноймовірні). 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 операцій налаштування (побудова хеш-таблиці).