Compilerbau: Kontextfreie Grammatik
Willemers Informatik-Ecke

Zu einer kontextfreien Grammatik gehören vier Komponenten

  1. Eine Menge von Terminalen. Terminale sind die Symbole einer Sprache. Terminal heißen sie, weil sie am Ende der Auflösung stehen. Beispiele sind Stern, Klammern, aber auch Schlüsselworte (if, then, while) oder Konstanten.
  2. Eine Menge von Nichtterminalen. Nichtterminale sind Zwischensymbole der Grammatik, die noch nicht vollständig aufgelöst sind.
  3. Eine Menge von Produktionen. Eine Produktion besteht links aus einem Nichtterminal, gefolgt von einem Pfeil und einer rechten Seite, die aus Terminalen und Nichtterminalen bestehen kann. Eine Produktion ist eine Regel, die beschreibt, wie sich zulässige Worte (bzw. Sätze) der Grammatik bilden lassen.
  4. Ein Startsymbol. Das Startsymbol ist ein Nichtterminal.
Beispiel:

statement -> if ( expression ) statement else statement

vgl. Aho, Sethi, Ullmann: Compilerbau. Addison Wesley 1988. S.33.