Grammatik

Eine Grammatik ist in der Informatik eine Methode zur Beschreibung, Analyse oder Erzeugung von Sprachen. Jede Grammatik beginnt mit einem Startsymbol, auf das dann Produktionsregeln angewandt werden. In diesen Produktionsregeln kommen sogenannte Terminale und Nichtterminale sowie das leere Symbol vor.

Formal gesehen besteht eine Grammatik aus vier Komponenten (sie ist also ein 4-Tupel):

  1. Einer endlichen Menge N von Nichtterminalsymbolen.
  2. Einer endlichen Menge T von Terminalsymbolen.
  3. Einer endlichen Menge P von Produktionsregeln.
  4. Dem Startsymbol S aus N.

In der deutschen Sprache sind Nichtterminalsymbole Begriffe wie "Wort", "Satz", "Adjektiv" und so weiter, während Terminalsymbole Worte wie "Hund", "hat", "ist", "ein" und so weiter sind. Terminalsymbole können nicht mehr weiter aufgelöst werden, während Nichtterminalsymbole durch Produktionsregeln in Ketten aus Terminalen und weiteren Nichtterminalen aufgelöst werden können.

Ein Beispiel

Folgende Grammatik wurde der Abituraufgabe HT 4 von 2021 entnommen:

  • Startsymbol: S
  • Terminalsymbole: {g, r, l, p}
  • Nichtterminalsymbole: {S, G, K}
  • Produktionen: {S ⟹ pKp | pGp, K ⟹ rGl | lGr, G ⟹ gG | epsilon }

Das Startsymbol kann zu pKp oder pGp weiter entwickelt werden. Die Symbolkette pKp kann dann zu prGlp entwickelt werden und so weiter. Am Ende dieser Ableitungen muss eine Symbolkette stehen, die ausschließlich aus Terminalsymbolen besteht. Dieses Wort gehört dann zur Sprache L(G) der Grammatik G.

Eine besondere einfache Art von Grammatiken sind die kontextfreien Grammatiken. Bei ihren Produktionen steht immer genau ein Nichtterminalsymbol auf der linken Seite der Produktionen. Das obige Beispiel ist eine kontextfreie Grammatik.  Das Gegenteil wäre eine kontextsensitive Grammatik. Hier kann die linke Seite komplexer aussehen. Das "Schicksal" eines Nichtterminals kann dann davon abhängen, in welchem Kontext es steht, das heißt bei xN kann aus N etwas anderes werden als bei yN (N = Nichtterminal, x,y = Terminale). Ein einfacher Spezialfall der kontextfreien Grammatiken sind die regulären Grammatiken, die im Zentralabitur NRW eine besondere Rolle spielen.