Gramatyka jako Struktura Grafu
Kompilator tłumaczy kod źródłowy, budując drzewo parse - drzewo z korzeniem, gdzie każdy węzeł reprezentuje zastosowaną regułę gramatyczna, a każdy listek reprezentuje symbol końcowy (nazwa zmiennej, literał, operator).
Geometria Drzewa
Drzewo o n węzłach i n-1 krawędziach. Głębokość d: maksymalna odległość od korzenia do każdego liścia. Dla równowagi binarnego drzewa o głębokości d: do 2^d liści i 2^(d+1)-1 węzłów ogółem.
Drzewa parse dla typowych wyrażeń nie są równoległe: kolejność operatorów tworzy drzewa skosowe w prawo lub lewo. A + B C tworzy drzewo, gdzie jest głębsze niż +, kodując, że * wiąże się mocniej.
BNF & ALGOL
Backus-Naur Form (BNF), wynaleziony, aby określić 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 to skierowany graf na symbolach nieterminowych; analizowanie zdania śledzi ścieżkę przez ten graf od symbolu początkowego do liści.
Głębokość Drzewa Parse i Złożoność Wyrażeń
Dla wyrażenia (A + B) * (C + D), drzewo parse ma konkretną strukturę pod standardową kolejnością operatorów.
Głębokość drzewa wpływa na wydajność kompilatora: głębsze drzewa wymagają więcej pól ramki stosu podczas parsowania rekurencyjnego.
Entropia Shannon'a & Nadmiar
Hamming zauważył, że język mówiony jest ~60% nadmiarowy, zapisany język ~40%. To ma dokładne znaczenie informacyjno-teoretyczne.
Entropia Shannon'a
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: równomienne rozkładanie (wszystkie symbole są równie prawdopodobne). H_max = log₂(n) dla n symboli.
Nadmiar R: frakcja bitów, które nie przekazują informacji (można je usunąć bez utraty treści):
R = 1 − H / H_max
Jeśli R = 0,4 (40% nadmiar): 40% bitów można przewidzieć na podstawie kontekstu. Kanał przesyłający tekst angielski o 8 bitach na znak używa tylko 60% swojej zdolności do przekazu informacji; 40% to struktura, którą odbiornik już zna.
Ochrona przed błędami wykorzystuje nadmiar: jeśli 40% bitów jest przewidywalnych, błąd transmisji może wygenerować sekwencję, która narusza strukturę nadmiaru - wykrywalna nawet w przypadku braku kodów korekcyjnych.
Nadmiar APL bliski zeru: zmiana pojedynczego znaku jest prawie nigdy nieodkrywalna z kontekstu. Angielski 60% nadmiaru: można często odtworzyć słowo z otoczeniem kontekstu nawet jeśli jeden znak jest nieprawidłowy lub pominięty.
Obliczanie Nadmiaru
Częstość liter angielskich (przybliżona): 'e' pojawia się około 12,7% czasów; 'z' pojawia się około 0,07%. Prawdziwa entropia angielska wynosi około H ≈ 1,0 bit/znak (uwzględniając kontekst na poziomie słów). Maksymalna entropia dla alfabetu o 26 literach: H_max = log₂(26) ≈ 4,70 bitów/znak.
Kształty wzrostu jako geometria
Algorytmy kompilatorów przetwarzają programy o wielkości n (tokeny, wiersze lub węzły). Wybór algorytmu determinuje, jak szybkość kompilacji wzrasta wraz ze wzrostem wielkości programu.
Wspólne klasy złożoności
| Klasy | Czas wykonania | Przykład | |---|---|---| | O(n) | liniowy | skanowanie leksyczne | | O(n log n) | quasi-liniowy | optymalne sortowanie | | O(n²) | kwadratowy | prosta detekcja powtórzeń | | O(n³) | krytyczny | mnożenie macierzy, parsing CYK | | O(2ⁿ) | wykonalny | proste dowodzenie na teorię |
Obraz geometryczny: narysuj czas wykonania w funkcji od n. O(n) to linia. O(n²) to parabola. O(2ⁿ) to wykonalna krzywa, która wygląda płasko blisko n = 0 i prawie pionowo blisko n = 50.
Ogólne parsowanie kontekstowo-zależnych gramatyk (algorytm CYK) wykonuje się w czasie O(n³). Dla większości praktycznych języków programowania, gramatyka jest zaprojektowana tak, aby być LR(1)-parsowalna, co pozwala na parsing w czasie O(n). Gramatyka ALGOL była bardziej skomplikowana niż gramatyka FORTRAN, co przyczyniało się do wolniejszych kompilatorów - praktyczne opory, które miały znaczenie w 1958 roku, gdy kompilacja zajmowała godziny.
Punkty przecięcia
Prostego wyszukiwanie w tabeli symboli używa O(n²) operacji całkowitych dla programu o n identyfikatorach (liniowa skanowanie dla każdego z n wyszukiwań). Tabela haszująca używa O(n) operacji całkowitych oczekiwanego wyniku.
Załóżmy: algorytm O(n²) wykonuje 10⁶ operacji na sekundę na sprzęcie z 1958 roku. Algorytm O(n) wykonuje te same operacje, ale wymaga 100n operacji uruchomienia (konstrukcji tabeli haszującej).