Eine kontextfreie Grammatik ist ein formales Regelsystem, das beschreibt, welche Zeichenfolgen zu einer Sprache gehören. Jede moderne Programmiersprache lässt sich durch eine solche Grammatik exakt definieren – sie ist die Grundlage, auf der Parser die Struktur von Quellcode erkennen.
Aufbau einer kontextfreien Grammatik
Eine Grammatik besteht aus vier Bausteinen:
- Terminalsymbole: die kleinsten Bausteine, meist die Token des Lexers wie Schlüsselwörter, Zahlen oder Operatoren.
- Nichtterminale: Platzhalter für Satzteile, zum Beispiel Ausdruck oder Anweisung.
- Produktionen (Regeln): Festlegungen der Form Nichtterminal → Folge von Symbolen.
- Startsymbol: das oberste Nichtterminal, von dem jede Ableitung ausgeht.
Als Notation hat sich die Backus-Naur-Form (BNF) etabliert; ihre erweiterte Fassung EBNF erlaubt Wiederholungen und optionale Teile. Beide sind reine Schreibweisen für dieselbe Idee.
Was bedeutet „kontextfrei“?
Kontextfrei heißt: Auf der linken Seite jeder Produktion steht genau ein Nichtterminal. Eine Regel wie Ausdruck → Ausdruck + Term ist damit überall anwendbar, wo ein Ausdruck erwartet wird – unabhängig vom umgebenden Kontext. Das unterscheidet kontextfreie Sprachen von kontextsensitiven Grammatiken, deren Regeln von Nachbarsymbolen abhängen. In der Chomsky-Hierarchie bilden kontextfreie Grammatiken den Typ 2 und liegen damit genau zwischen regulären Sprachen (Typ 3, die der lexikalischen Analyse zugrunde liegen) und kontextsensitiven beziehungsweise rekursiv aufzählbaren Sprachen.
Vom Startsymbol zur Tokenfolge
Eine Ableitung startet beim Startsymbol und ersetzt Schritt für Schritt Nichtterminale durch die rechten Seiten von Produktionen, bis nur noch Terminalsymbole übrig sind. Das Ergebnis ist genau die Tokenfolge eines Programms. Die Zwischenschritte lassen sich als Baum darstellen – den Syntaxbaum.
Ein einfaches Beispiel für arithmetische Ausdrücke:
Ausdruck → Ausdruck + Term | Term
Term → Term * Faktor | Faktor
Faktor → Zahl | ( Ausdruck )
Zahl → 0 | 1 | ... | 9Die Zeichenfolge 2 + 3 * 4 lässt sich damit ableiten, 2 + * 3 nicht – genau diese Unterscheidung übernimmt später der Parser.
Warum sind Grammatiken wichtig?
Eine präzise Grammatik ist die Spezifikation einer Programmiersprache. Aus ihr erzeugen LL-Parser und LR-Parser ihre Tabellen beziehungsweise Entscheidungsbäume, und Parser-Generatoren wie Yacc oder ANTLR übersetzen die Regeln direkt in lauffähigen Parser-Code. Wer eine eigene Compiler-Sprache oder eine domänenspezifische Sprache entwirft, beginnt deshalb fast immer mit der Grammatik.
Verwandte Grundlagen: Syntax, Rekursiver Abstieg, LALR-Parser.