Grammatik als Graphstruktur
Ein Compiler übersetzt Quellcode durch den Aufbau eines Analysebaums — ein verwurzelter Baum, in dem jeder Knoten eine angewendete Grammatikregel darstellt, & jedes Blatt ein Terminalzeichen darstellt (Variablennamen, Literal, Operator).
Baumgeometrie
Ein Baum mit n Knoten & n−1 Kanten. Tiefe d: der maximale Abstand von der Wurzel zu einem beliebigen Blatt. Für einen ausgeglichenen binären Baum der Tiefe d: bis zu 2^d Blätter & 2^(d+1)−1 Gesamtknoten.
Analysebäume für typische Ausdrücke sind nicht ausgeglichen: Operatorpriorität erzeugt rechtsasymmetrische oder linksasymmetrische Bäume. A + B C erzeugt einen Baum, in dem tiefer als + liegt und kodiert, dass * enger bindet.
BNF & ALGOL
Backus-Naur Form (BNF), erfunden um ALGOL zu spezifizieren, formalisiert Grammatik als Produktionsregeln:
``
<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>
<factor> ::= id | (<expr>)
``
Jede Produktionsregel definiert eine Ebene des Baums. Die Grammatik ist ein gerichteter Graph auf Nichtterminalzeichen; das Parsen eines Satzes verfolgt einen Pfad durch diesen Graphen vom Startsymbol zu den Blättern.
Tiefe von Analysebäumen & Ausdruckskomplexität
Für den Ausdruck (A + B) * (C + D) hat der Analysebaum eine spezifische Struktur unter Standard-Operatorpriorität.
Die Tiefe eines Analysebaums beeinflusst die Compiler-Leistung: tiefere Bäume erfordern mehr Stack-Rahmen beim rekursiven Abstiegsparsing.
Shannon-Entropie & Redundanz
Hamming bemerkte, dass gesprochene Sprache ~60% redundant ist, geschriebene Sprache ~40%. Dies hat eine präzise informationstheoretische Bedeutung.
Shannon-Entropie
Für eine Quelle, die Zeichen aus Alphabet A mit Wahrscheinlichkeiten {p₁, p₂, ..., pₙ} erzeugt:
H = −Σ pᵢ log₂(pᵢ) (bits per symbol)
Maximale Entropie: Gleichverteilung (alle Zeichen gleich wahrscheinlich). H_max = log₂(n) für n Zeichen.
Redundanz R: Anteil der Bits, die keine Information tragen (könnte entfernt werden, ohne Inhalt zu verlieren):
R = 1 − H / H_max
Wenn R = 0,4 (40% redundant): 40% der Bits können aus dem Kontext vorhergesagt werden. Ein Kanal, der englischen Text mit 8 Bits/Zeichen trägt, nutzt nur 60% seiner Kapazität für Information; 40% ist Struktur, die der Empfänger bereits kennt.
Fehlererkennung nutzt Redundanz: Wenn 40% der Bits vorhersehbar sind, kann ein Übertragungsfehler eine Sequenz erzeugen, die die Redundanzstruktur verletzt — erkennbar auch ohne Fehlerkorrekturcodes.
APLs nahezu keine Redundanz: Eine einzelne Zeichenänderung ist fast nie nur aus dem Kontext erkennbar. Englische 60% Redundanz: Sie können oft ein Wort aus dem umgebenden Kontext rekonstruieren, selbst wenn ein Buchstabe fehlt oder falsch ist.
Redundanz berechnen
Englische Buchstabenhäufigkeit (ungefähr): 'e' erscheint ~12,7% der Zeit; 'z' erscheint ~0,07%. Die tatsächliche Entropie des Englischen ist ungefähr H ≈ 1,0 Bit/Zeichen (unter Berücksichtigung des Wortebenen-Kontexts). Maximale Entropie für 26-Buchstaben-Alphabet: H_max = log₂(26) ≈ 4,70 Bits/Zeichen.
Wachstumskurven als Geometrie
Compiler-Algorithmen verarbeiten Programme der Größe n (Token, Zeilen oder Knoten). Die Wahl des Algorithmus bestimmt, wie sich die Compile-Zeit mit der Programmgröße skaliert.
Übliche Komplexitätsklassen
| Klasse | Laufzeit | Beispiel | |---|---|---| | O(n) | linear | lexikalisches Scannen | | O(n log n) | quasi-linear | optimales Sortieren | | O(n²) | quadratisch | naive Duplikaterkennung | | O(n³) | kubisch | Matrixmultiplikation, CYK-Parsing | | O(2ⁿ) | exponentiell | naiver Theorembeweis |
Das geometrische Bild: Laufzeit gegen n zeichnen. O(n) ist eine Linie. O(n²) ist eine Parabel. O(2ⁿ) ist eine Exponentialkurve, die nahe n=0 flach aussieht und nahe n=50 fast senkrecht ist.
Allgemeines kontextfreies Grammatik-Parsing (CYK-Algorithmus) läuft in O(n³). Für die meisten praktischen Programmiersprachen ist die Grammatik so konzipiert, dass sie LR(1)-parseble ist, was O(n)-Parsing ermöglicht. ALGOLs Grammatik war komplexer als FORTRANs, was zu langsameren Compilern beitrug — eine praktische Reibung, die 1958 wichtig war, als das Compilieren Stunden dauerte.
Schnittpunkte
Eine naive Symboltabellensuche verwendet O(n²) Gesamtoperationen für ein Programm von n Bezeichnern (lineares Scannen für jede von n Suchen). Eine Hash-Tabellen-Symboltabelle verwendet O(n) erwartete Gesamtoperationen.
Angenommen: O(n²)-Algorithmus läuft auf 1958er-Hardware bei 10⁶ Operationen/Sekunde. O(n)-Algorithmus läuft mit der gleichen Geschwindigkeit, erfordert aber 100n Setup-Operationen (Hash-Tabellenkonstruktion).