Grammatik als Graphenstruktur
Ein Compiler übersetzt Quellcode, indem er eine Ausdruckstriebe baut - eine verankernte Baum, bei dem jeder Knoten eine Grammatikregel angewendet darstellt und jeder Blatt eine terminale Symbol (Variablenname, Literal, Operator).
Baumgeometrie
Ein Baum mit n Knoten und n-1 Kanten. Tiefe d: die maximale Entfernung von der Wurzel bis zu jedem Blatt. Für einen ausgewogenen binären Baum der Tiefe d: bis zu 2^d Blätter und 2^(d+1)-1 gesamt Knoten.
Ausdruckstriebe für typische Ausdrücke sind nicht ausgewogen: Operatorvorrang erstellt rechts-skew oder links-skew Bäume. A + B C erzeugt einen Baum, bei dem tiefer ist als +, was bedeutet, dass * enger gebunden ist.
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 Baumes. Die Grammatik ist ein gerichteter Graph über Nicht-Terminalsymbols; das Parsen eines Satzes verfolgt einen Weg durch diesen Graphen von dem Startsymbol bis zu den Blättern.
Ausdruckstriebe-Tiefe & Ausdruckskomplexität
Für die Ausdruck (A + B) * (C + D) hat der Ausdruckstriebe eine spezifische Struktur unter standardmäßigem Operatorvorrang.
Die Tiefe eines Ausdruckstriebe beeinflusst die Leistung eines Compilers: tiefe Bäume erfordern mehr Frames auf der Stacks während der rekursiven Abstiegsparsing.
Shannons Entropie & Überlappung
Hamming bemerkte, dass gesprochene Sprache etwa 60% redundant ist, geschriebene Sprache etwa 40%. Das hat einen genauen informationstheoretischen Sinn.
Shannons Entropie
Für eine Quelle, die Symbole aus dem Alphabet A generiert, mit Wahrscheinlichkeiten {p₁, p₂, ..., pₙ}:
H = −Σ pᵢ log₂(pᵢ) (Bits pro Symbol)
Maximale Entropie: gleichmäßige Verteilung (alle Symbole sind gleich wahrscheinlich). H_max = log₂(n) für n Symbole.
Redundanz R: Bruchteil der Bits, die keine Informationen tragen (könnten ohne Verlust des Inhalts entfernt werden):
R = 1 − H / H_max
Wenn R = 0,4 (40% redundant): 40% der Bits können aus dem Kontext vorhergesagt werden. Ein Kanal, der englische Text bei 8 Bits/Zeichen überträgt, verwendet nur 60% seiner Kapazität für Informationen; 40% ist Struktur, die der Empfänger bereits kennt.
Fehlererkennung nutzt Redundanz: Wenn 40% der Bits vorhersehbar sind, kann eine Übertragungsfehler eine Folge erzeugen, die die Redundanzstruktur verletzt - detektierbar, auch ohne Fehlerkorrekturcodes.
APL's nahe Null-Redundanz: Eine Änderung eines einzelnen Zeichens ist fast nie aus dem Kontext allein detektiv. Englisches 60% Redundanz: Sie können oft ein Wort aus dem umliegenden Kontext rekonstruieren, selbst wenn ein Buchstabe fehlt oder falsch ist.
Redundanzberechnung
Englische Buchstabenfrequenz (ungefähr): 'e' tritt etwa 12,7% der Zeit auf; 'z' tritt etwa 0,07% der Zeit auf. Die tatsächliche Entropie des Englischen beträgt etwa H ≈ 1,0 Bit/Zeichen (berücksichtigt den Kontext auf Wortebene). Maximale Entropie für ein 26-Buchstaben-Alphabet: H_max = log₂(26) ≈ 4,70 Bit/Zeichen.
Wachstumskurven als Geometrie
Compileralgorithmen verarbeiten Programme der Größe n (Token, Zeilen oder Knoten). Die Wahl des Algorithmus bestimmt, wie die Compilierungszeit mit der Größe des Programms ansteigt.
Gemeinsame Komplexitätsklassen
| Klasse | Laufzeit | Beispiel | |---|---|---| | O(n) | linear | lexikalische Scannung | | O(n log n) | quasi-linear | optimale Sortierung | | O(n²) | quadratisch | naive Duplikatserkennung | | O(n³) | kubisch | Matrizenmultiplikation, CYK-Analysis | | O(2ⁿ) | exponentiell | naive Beweisführung |
Das geometrische Bild: Zeichne Laufzeit gegen n. O(n) ist eine Gerade. O(n²) ist eine Parabel. O(2ⁿ) ist eine exponentielle Kurve, die bei n = 0 flach und bei n = 50 fast senkrecht aussieht.
Allgemeine kontextfreie Grammatik-Analyse (CYK-Algorithmus) läuft in O(n³). Für die meisten praktischen Programmiersprachen ist die Grammatik so gestaltet, dass sie LR(1)-parsable ist, was eine O(n)-Analyse ermöglicht. Die ALGOL-Grammatik war komplexer als die von FORTRAN, was zu langsameren Compilern beitrug - eine praktische Reibung, die im Jahr 1958, wenn das Compilieren Stunden dauerte, von Bedeutung war.
Überschneidungspunkte
Eine naive Symboltabelle mit Suchvorgang benötigt O(n²) Gesamtoperationen für ein Programm mit n Identifikatoren (lineare Suche für jede der n Abfragen). Eine Hashtabelle mit Symboltabelle benötigt O(n) erwartete Gesamtoperationen.
Angenommen: O(n²)-Algorithmus arbeitet mit 10⁶ Operationen/s auf 1958-Hardware. O(n)-Algorithmus arbeitet auf derselben Geschwindigkeit, aber er benötigt 100n Einarbeitungsoperationen (Hash-Tabelle erstellen).