Grammatica als Graafstructuur
Een compiler vertaalt broncode door een parse tree te bouwen — een gewortelde boom waarbij elk knooppunt een toegepaste grammaticaregel vertegenwoordigt, en elk blad een terminaal symbool vertegenwoordigt (variabele naam, letterlijke waarde, operator).
Boomgeometrie
Een boom met n knooppunten en n−1 randen. Diepte d: de maximale afstand van wortel naar enig blad. Voor een evenwichtige binaire boom van diepte d: tot 2^d bladeren en 2^(d+1)−1 totale knooppunten.
Parse trees voor typische uitdrukkingen zijn niet evenwichtig: operatorprioriteit creëert rechts-scheve of links-scheve bomen. A + B C produceert een boom waarbij dieper is dan +, wat aangeeft dat * sterker bindt.
BNF en ALGOL
Backus-Naur Form (BNF), uitgevonden om ALGOL te specificeren, formaliseert grammatica als productieregels:
``
<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>
<factor> ::= id | (<expr>)
``
Elke productieregel definieert één niveau van de boom. De grammatica is een gerichte graaf op niet-terminale symbolen; het parseren van een zin volgt een pad door die graaf van startsymbool naar bladeren.
Parse Tree-Diepte en Expressiecomplexiteit
Voor de expressie (A + B) * (C + D) heeft de parse tree een specifieke structuur volgens standaard operatorprioriteit.
De diepte van een parse tree beïnvloedt de prestatie van de compiler: diepere bomen vereisen meer stack frames tijdens recursive descent parsing.
Shannon-Entropie en Redundantie
Hamming merkte op dat gesproken taal ~60% redundant is, geschreven taal ~40%. Dit heeft een precieze informatietheorische betekenis.
Shannon-Entropie
Voor een bron die symbolen genereert uit alfabet A met waarschijnlijkheden {p₁, p₂, ..., pₙ}:
H = −Σ pᵢ log₂(pᵢ) (bits per symbool)
Maximale entropie: uniforme verdeling (alle symbolen even waarschijnlijk). H_max = log₂(n) voor n symbolen.
Redundantie R: het deel van bits dat geen informatie draagt (kon worden verwijderd zonder inhoud te verliezen):
R = 1 − H / H_max
Als R = 0,4 (40% redundant): 40% van de bits kan uit context worden voorspeld. Een kanaal dat Engelse tekst draagt met 8 bits/karakter gebruikt slechts 60% van zijn capaciteit voor informatie; 40% is structuur die de ontvanger al kent.
Foutdetectie gebruikt redundantie: als 40% van de bits voorspelbaar zijn, kan een transmissiefout een reeks produceren die de redundantiestructuur schendt — detecteerbaar zelfs zonder foutcorrigerende codes.
APLs nabije-nul redundantie: een enkele karakterverandering is bijna nooit detecteerbaar uit context alleen. Engels' 60% redundantie: je kunt vaak een woord uit omliggende context reconstrueren zelfs als een letter ontbreekt of fout is.
Redundantie Berekenen
Engelse letterfrekwentie (bij benadering): 'e' verschijnt ~12,7% van de tijd; 'z' verschijnt ~0,07%. De werkelijke entropie van het Engels is ongeveer H ≈ 1,0 bit/karakter (rekening houdend met context op woordniveau). Maximale entropie voor 26-letteralfabet: H_max = log₂(26) ≈ 4,70 bits/karakter.
Groeicurven als Geometrie
Compileralgorithmen verwerken programma's van grootte n (tokens, regels, of knooppunten). De keuze van algoritme bepaalt hoe compilatietijd schaalt met programmagrootte.
Veelvoorkomende Complexiteitsklassen
| Klasse | Runtime | Voorbeeld | |---|---|---| | O(n) | lineair | lexicale scanning | | O(n log n) | quasi-lineair | optimaal sorteren | | O(n²) | kwadratisch | naïeve detectie van duplicaten | | O(n³) | kubisch | matrixvermenigvuldiging, CYK parsing | | O(2ⁿ) | exponentieel | naïev stellingbewijzen |
Het geometrische beeld: plot runtime versus n. O(n) is een lijn. O(n²) is een parabool. O(2ⁿ) is een exponentiële curve die vlak lijkt dicht bij n=0 en bijna verticaal dicht bij n=50.
Algemeen contextvrije grammatica parsing (CYK-algoritme) draait in O(n³). Voor de meeste praktische programmeertalen is de grammatica ontworpen om LR(1)-parseerbaar te zijn, wat O(n) parsing mogelijk maakt. ALGOLs grammatica was complexer dan FORTRANs, wat bijdroeg aan langzamere compilers — een praktische wrijving die in 1958 van belang was toen compilatie uren duurde.
Kruispunten
Een naïeve symbool-tabel opzoeking gebruikt O(n²) totale operaties voor een programma met n identificatoren (lineaire scan voor elk van n opzoekingen). Een hash-tabel symbool-tabel gebruikt O(n) verwachte totale operaties.
Stel: O(n²) algoritme draait op 10⁶ operaties/sec op 1958-hardware. O(n) algoritme draait op dezelfde snelheid maar vereist 100n setup operaties (hashtabel constructie).