Grammatik som grafstruktur
En kompilator översätter källkod genom att bygga ett analysträd — ett rotat träd där varje nod representerar en tillämplig grammatikregel och varje löv representerar en terminalsymbol (variabelnamn, literal, operator).
Trädens geometri
Ett träd med n noder och n−1 kanter. Djup d: det maximala avståndet från rot till vilket blad som helst. För ett balanserat binärt träd med djup d: upp till 2^d löv och 2^(d+1)−1 totala noder.
Analysträd för typiska uttryck är inte balanserade: operatorprioritet skapar högersned eller vänstersned träd. A + B C producerar ett träd där är djupare än +, vilket kodar att * binder tätare.
BNF & ALGOL
Backus-Naur Form (BNF), uppfunnen för att specificera ALGOL, formaliserar grammatik som produktionsregler:
``
<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>
<factor> ::= id | (<expr>)
``
Varje produktionsregel definierar en nivå i trädet. Grammatiken är en riktad graf på icke-terminala symboler; analys av en mening spårar en väg genom den grafen från startsymbol till löv.
Analysträdsdjup och uttryckskomplexitet
För uttrycket (A + B) * (C + D) har analysträdet en specifik struktur enligt standardoperatorprioritet.
Djupet på ett analysträd påverkar kompilatorns prestanda: djupare träd kräver fler stackramar under rekursiv nedåtanalys.
Shannons entropi och redundans
Hamming noterade att talat språk är ~60% redundant, skrivet språk ~40%. Detta har en exakt informationsteoretisk betydelse.
Shannon-entropi
För en källa som genererar symboler från alfabet A med sannolikheter {p₁, p₂, ..., pₙ}:
H = −Σ pᵢ log₂(pᵢ) (bitar per symbol)
Maximal entropi: uniform fördelning (alla symboler lika sannolika). H_max = log₂(n) för n symboler.
Redundans R: andel bitar som inte bär någon information (kunde tas bort utan att förlora innehål):
R = 1 − H / H_max
Om R = 0,4 (40% redundant): 40% av bitarna kan förutsägas från sammanhang. En kanal som bär engelsk text på 8 bitar/tecken använder bara 60% av sin kapacitet för information; 40% är struktur som mottagaren redan vet.
Feldetektering använder redundans: om 40% av bitarna är förutsägbara kan ett överföringsfel producera en sekvens som bryter mot redundansstrukturen — detekterbar även utan felkorrigeringskoder.
APLs nästan noll redundans: en enda teckenändring är nästan aldrig detekterbar från sammanhang ensamt. Engelsks 60% redundans: du kan ofta rekonstruera ett ord från omgivande sammanhang även om en bokstav saknas eller är fel.
Beräkning av redundans
Engelsk bokstavsfrekvens (ungefärlig): 'e' förekommer ~12,7% av tiden; 'z' förekommer ~0,07%. Den faktiska entropin för engelska är cirka H ≈ 1,0 bit/tecken (med hänsyn till ordnivåsammanhang). Maximal entropi för 26-bokstavs alfabet: H_max = log₂(26) ≈ 4,70 bitar/tecken.
Tillväxtkurvor som geometri
Kompilatoralgoritmer bearbetar program med storlek n (tokens, rader eller noder). Algoritmalternativet bestämmer hur kompileringstiden skaleras med programstorlek.
Vanliga komplexitetsklasser
| Klass | Körtid | Exempel | |---|---|---| | O(n) | linjär | lexikalisk skanning | | O(n log n) | kvasilinjär | optimal sortering | | O(n²) | kvadratisk | naiv dubblettdetektering | | O(n³) | kubisk | matris multiplicering, CYK-analys | | O(2ⁿ) | exponentiell | naiv satsbevisning |
Den geometriska bilden: plot körtid vs n. O(n) är en linje. O(n²) är en parabel. O(2ⁿ) är en exponentiell kurva som ser flat ut nära n=0 och nästan vertikal nära n=50.
Allmän kontextfri grammatikanalys (CYK-algoritm) körs i O(n³). För de flesta praktiska programmeringsspråk är grammatiken utformad för att vara LR(1)-parsbar, vilket tillåter O(n) analys. ALGOLs grammatik var mer komplex än FORTRANs, vilket bidrog till långsammare kompilatorer — en praktisk friktion som gjorde skillnad 1958 när kompilering tog timmar.
Korsningspunkter
En naiv symboltabelluppslagnig använder O(n²) totala operationer för ett program med n identifierare (linjär skanning för var och en av n uppslagningar). En hashtabellsymboltabell använder O(n) förväntade totala operationer.
Antag: O(n²)-algoritm körs på 10⁶ operationer/sekund på 1958-hårdvara. O(n)-algoritmen körs med samma hastighet men kräver 100n inställningsoperationer (hashtabellkonstruktion).