Formale Grammatik: Regeln, Ableitung und Sprache

Eine formale Grammatik ist ein mathematisches Modell. Sie legt eine Menge von Wörtern fest. Ein Wort ist dabei eine endliche Folge von Zeichen. Die Menge der Wörter, die sich mit der Grammatik erzeugen lassen, heißt formale Sprache.

Eine bloße Liste von Ersetzungsregeln ist noch keine Grammatik. Man schreibt eine Grammatik als 4-Tupel, also als Liste aus vier Teilen:

Terminale: Das sind die Zeichen, aus denen die fertigen Wörter bestehen. Sie werden nicht weiter abgeleitet. Normalerweise sind es Kleinbuchstaben oder Ziffern.

Nichtterminale (auch Variablen genannt): Das sind Zeichen, die noch durch andere Zeichen ersetzt werden müssen. Man schreibt sie als Großbuchstaben.

Produktionsregeln: Sie beschreiben, wie Nichtterminale ersetzt werden dürfen. Eine Regel schreibt man mit Pfeil, zum Beispiel α → β. Auf der linken Seite muss mindestens ein Nichtterminal stehen.

Startsymbol: Das ist ein bestimmtes Nichtterminal, bei dem jede Ableitung beginnt. Man nennt es normalerweise S.

Ein Zeichen kann nicht gleichzeitig Terminal und Nichtterminal sein. Manche Bücher fassen Terminale und Nichtterminale auch zu einem gemeinsamen Vokabular zusammen.

Ableiten heißt, ein Wort nach den Regeln einer Grammatik zu erzeugen. Du beginnst mit dem Startsymbol. Dann führst du nacheinander Ableitungsschritte durch. Bei geeigneter Wahl der Regeln endest du bei einem fertigen Wort.

Ein Ableitungsschritt ersetzt einmal einen Teilabschnitt der Zeichenfolge nach einer Regel. In jedem Schritt wird genau eine Regel angewendet. Man schreibt den Schritt mit dem Pfeil ⇒.

Die Zeichenfolgen dazwischen heißen Satzformen. Eine Satzform besteht aus Terminalen und Nichtterminalen. Ein Wort besteht nur aus Terminalen. Eine Ableitung beginnt mit dem Startsymbol, und ihre letzte Satzform ist ein Wort.

Oft passen mehrere Regeln, oder eine Regel passt an mehreren Stellen. Formale Grammatiken schreiben keine Reihenfolge vor. Ein kleines Beispiel: Mit der Regel X → + oder X → - kann man die Zeichenfolge 1X2 entweder zu 1+2 oder zu 1-2 ableiten. In einem Schritt entsteht aber nur eines davon.

Die Frage, ob ein Wort zu einer Sprache gehört, heißt Wortproblem. Die Sprache einer Grammatik besteht aus allen Wörtern, die nur aus Terminalen bestehen und sich in endlich vielen Schritten aus dem Startsymbol ableiten lassen.

Deshalb gilt: Ein Wort gehört zur Sprache, wenn eine Ableitung des Wortes existiert. Eine Ableitung ist damit ein Beweis dafür, dass das Wort zur Sprache gehört.

Das nutzt zum Beispiel der Parser eines Compilers. Er sucht indirekt eine Ableitung für den Quelltext. Scheitert er, weil das Programm einen Syntaxfehler enthält, ist nachgewiesen, dass keine Ableitung existiert.

Bei einer Typ-1-Grammatik (die Typen lernst du im letzten Abschnitt kennen) kannst du systematisch alle möglichen Ableitungen ausprobieren. Sobald du die Länge des gesuchten Wortes überschritten hast, kannst du aufhören. Aus einer längeren Satzform kann das Wort nicht gebildet werden. Bei regulären Grammatiken lässt sich das Wortproblem sogar sehr effizient entscheiden.

Eine rechtsreguläre Grammatik darf nur Regeln dieser drei Muster haben: X → aY, X → a und X → ε. Dabei sind X und Y Nichtterminale und a ist ein Terminal.

Die Do-Re-Mi-Grammatik ist so ein Beispiel. Ihre Terminale sind d, e, i, m, o, r. Ihre Nichtterminale sind S, A, B, C, und S ist das Startsymbol. Die Regeln sind S → dA | rB | mC | ε und A → oS, B → eS, C → iS. Die Sprache besteht aus allen Folgen der Blöcke do, re und mi.

So wächst das Wort: Jede Satzform mit Nichtterminal besteht aus einem Terminalwort vorneweg und einem einzigen Nichtterminal am Ende. In jedem Schritt wird rechts ein Terminal angefügt, und das Nichtterminal am Ende ändert sich. Das Wort wächst also von links nach rechts.

Das entspricht dem Einlesen eines Wortes in einem endlichen Automaten. Ein endlicher Automat liest ein Wort Zeichen für Zeichen und wechselt dabei zwischen Zuständen. Die Nichtterminale der Grammatik entsprechen den Zuständen. Für jede Regel X → aY gibt es einen Übergang (X, a, Y): vom Zustand X über das Zeichen a zum Zustand Y.

Die Chomsky-Hierarchie ordnet formale Grammatiken in vier Typen, gezählt von 0 bis 3. Die Typen unterscheiden sich darin, wie streng die Form der Regeln eingeschränkt ist. Typ 0 hat keine Einschränkung. Typ 1 bis Typ 3 sind zunehmend stärker eingeschränkt.

Typ 0 heißt auch unbeschränkt. Typ 1 heißt kontextsensitiv: Ein Nichtterminal A wird durch γ ersetzt, aber nur, wenn davor α und danach β steht. α, β und γ sind Zeichenfolgen, γ muss mindestens ein Symbol enthalten. Die Regel S → ε ist als Ausnahme erlaubt. Typ 2 heißt kontextfrei: Links steht genau ein Nichtterminal, es wird unabhängig vom Kontext ersetzt. Typ 3 heißt regulär: Es sind Typ-2-Grammatiken, bei denen rechts genau ein Terminal und höchstens ein Nichtterminal stehen darf. Das Nichtterminal steht in allen Regeln auf derselben Seite, entweder immer vor oder immer hinter dem Terminal. Das nennt man linksregulär oder rechtsregulär. Mischt man beides, ist die Grammatik nicht regulär. Heute erlaubt man bei Typ 2 und Typ 3 oft auch das leere Wort auf der rechten Seite, deshalb gibt es bei der Do-Re-Mi-Grammatik die Regel S → ε.

Nach Definition ist jede Typ-3-Grammatik auch vom Typ 2, jede Typ-2-Grammatik auch vom Typ 1 und jede Typ-1-Grammatik auch vom Typ 0. Die Umkehrungen gelten nicht. Darum ist es eine echte Hierarchie. Grammatiken niedrigeren Typs sind erzeugungsmächtiger. Dafür sind Sprachen eingeschränkterer Typen üblicherweise einfacher algorithmisch zu verarbeiten.

Zwei Gegenbeispiele zeigen, dass die Sprachklassen verschieden sind: Die Sprache aus n-mal a, dann n-mal b, dann n-mal c (n ≥ 1) ist vom Typ 1, aber nicht vom Typ 2. Die Sprache aus n-mal a, dann n-mal b (n ≥ 1) ist vom Typ 2, aber nicht vom Typ 3. Reguläre Ausdrücke für Textsuchen entsprechen dem Typ 3. Für Programmiersprachen benutzt man meist Typ-2-Grammatiken.