Gramatyka jako struktura grafu
Kompilator tłumaczy kod źródłowy, budując drzewo analizy — drzewo zakorzenione, w którym każdy węzeł reprezentuje zastosowaną regułę gramatyki, a każdy liść reprezentuje symbol terminalny (nazwa zmiennej, literał, operator).
Geometria drzewa
Drzewo z n węzłami i n−1 krawędziami. Głębokość d: maksymalna odległość od korzenia do jakiegokolwiek liścia. Dla zrównoważonego drzewa binarnego głębokości d: do 2^d liści i 2^(d+1)−1 węzłów w sumie.
Drzewa analizy dla typowych wyrażeń nie są zrównoważone: pierwszeństwo operatorów tworzy drzewa pochylone w prawo lub w lewo. A + B C tworzy drzewo, w którym jest głębiej niż +, kodując, że * wiąże się ściślej.
BNF i ALGOL
Forma Backusa-Naura (BNF), wymyślona do specyfikacji ALGOL, formalizuje gramatykę jako reguły produkcji:
``
<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>
<factor> ::= id | (<expr>)
``
Każda reguła produkcji definiuje jeden poziom drzewa. Gramatyka jest grafem skierowanym na symbolach nieterminalnych; analiza zdania śledzi ścieżkę przez ten graf od symbolu początkowego do liści.
Głębokość drzewa analizy i złożoność wyrażenia
Dla wyrażenia (A + B) * (C + D), drzewo analizy ma określoną strukturę przy standardowym pierwszeństwie operatorów.
Głębokość drzewa analizy wpływa na wydajność kompilatora: głębsze drzewa wymagają więcej ramek stosu podczas analizy z zejściem rekurencyjnym.
Entropia Shannona i redundancja
Hamming zauważył, że mowa jest ~60% nadmiarowa, a język pisany ~40%. Ma to precyzyjne znaczenie teoretyczno-informacyjne.
Entropia Shannona
Dla źródła generującego symbole z alfabetu A z prawdopodobieństwami {p₁, p₂, ..., pₙ}:
H = −Σ pᵢ log₂(pᵢ) (bity na symbol)
Maksymalna entropia: rozkład równomierny (wszystkie symbole równie prawdopodobne). H_max = log₂(n) dla n symboli.
Nadmiarowość R: ułamek bitów, które nie noszą informacji (mogą być usunięte bez utraty zawartości):
R = 1 − H / H_max
Jeśli R = 0,4 (40% nadmiarowe): 40% bitów można przewidzieć z kontekstu. Kanał przenoszący angielski tekst na 8 bitów/znak wykorzystuje tylko 60% pojemności dla informacji; 40% to struktura, którą odbiorca już zna.
Detekcja błędów wykorzystuje nadmiarowość: jeśli 40% bitów można przewidzieć, błąd transmisji może wytworzyć sekwencję naruszającą strukturę nadmiarowości — wykrywalną nawet bez kodów korekcji błędów.
Niemal zerowa nadmiarowość APL: pojedyncza zmiana znaku prawie nigdy nie jest wykrywalna z kontekstu. 60% nadmiarowości angielskiego: możesz często zrekonstruować słowo z otaczającego kontekstu, nawet jeśli litera jest brakująca lub błędna.
Obliczanie redundancji
Częstotliwość liter angielskich (przybliżona): 'e' pojawia się ~12,7% czasu; 'z' pojawia się ~0,07%. Rzeczywista entropia angielskiego wynosi około H ≈ 1,0 bit/znak (biorąc pod uwagę kontekst na poziomie słowa). Maksymalna entropia dla alfabetu 26-literowego: H_max = log₂(26) ≈ 4,70 bitów/znak.
Krzywe wzrostu jako geometria
Algorytmy kompilatora przetwarzają programy rozmiaru n (tokeny, linie lub węzły). Wybór algorytmu określa, jak czas kompilacji skaluje się wraz z rozmiarem programu.
Wspólne klasy złożoności
| Klasa | Czas działania | Przykład | |---|---|---| | O(n) | liniowy | skanowanie leksykalne | | O(n log n) | quasi-liniowy | optymalne sortowanie | | O(n²) | kwadratowy | naiwna detekcja duplikatów | | O(n³) | sześcienny | mnożenie macierzy, analiza CYK | | O(2ⁿ) | wykładniczy | naiwne dowodzenie twierdzeń |
Obraz geometryczny: wykreśl czas działania vs n. O(n) to linia. O(n²) to parabola. O(2ⁿ) to krzywa wykładnicza, która wygląda płasko blisko n=0 i prawie pionowo blisko n=50.
Analiza ogólnej gramatyki bezkontekstowej (algorytm CYK) działa w O(n³). Dla większości praktycznych języków programowania gramatyka jest zaprojektowana tak, aby była analizowalna LR(1), co pozwala na analizę O(n). Gramatyka ALGOL była bardziej złożona niż FORTRAN, przyczyniając się do wolniejszych kompilatorów — praktyczne tarcie, które miało znaczenie w 1958 r., gdy kompilacja trwała godzinami.
Punkty przejścia
Naiwne wyszukiwanie w tabeli symboli wykorzystuje O(n²) całkowitych operacji dla programu o n identyfikatorach (skanowanie liniowe dla każdego z n wyszukiwań). Tabela symboli z funkcją haszującą wykorzystuje O(n) oczekiwanych całkowitych operacji.
Przyjmij: algorytm O(n²) działa z szybkością 10⁶ operacji/sec na sprzęcie z 1958 roku. Algorytm O(n) działa z tą samą szybkością, ale wymaga 100n operacji konfiguracji (konstruowanie tabeli haszującej).