Formale Sprachen: Syntax, Semantik und Grammatiken

„Der Hund bellt den Regenbogen an." Der Satz ist grammatisch einwandfrei und inhaltlich sinnlos. „Bellt Hund der den an Regenbogen" ist beides nicht.

Diesen Unterschied kennst du aus Klasse 9 als Syntax und Semantik. In der Qualifikationsphase geht es einen entscheidenden Schritt weiter: Wie schreibt man die Syntax einer Sprache so auf, dass eine Maschine sie prüfen kann?

Die Antwort ist bemerkenswert: mit endlich vielen Regeln, aus denen sich unendlich viele richtige Sätze ableiten lassen. Genau das leistet eine Grammatik, und genau darauf beruht jeder Übersetzer, jede Programmiersprache und jede Eingabeprüfung.

Vorausgesetzt wird die Unterscheidung von Syntax (Form) und Semantik (Bedeutung) aus Variablen, Datentypen und Wertzuweisung. Neu ist hier, wie man Syntax aufschreibt, statt sie nur zu beschreiben.

Der wichtigste Unterschied ist die letzte Zeile, und er erklärt die anderen. Eine Maschine kann nicht nachfragen, was gemeint war. Deshalb muss bei einer formalen Sprache jede Zeichenfolge eindeutig entweder dazugehören oder nicht, und diese Entscheidung muss sich rein aus der Form treffen lassen.

Ein Alphabet $\Sigma$ ist eine endliche Menge von Zeichen.

Ein Wort über $\Sigma$ ist eine endliche Folge von Zeichen aus $\Sigma$. Auch das leere Wort gehört dazu; es wird $\varepsilon$ geschrieben.

Eine Sprache $L$ über $\Sigma$ ist eine Menge von Wörtern.

🔴 Beachte, dass eine Sprache hier nichts mit Bedeutung zu tun hat. Sie ist schlicht die Menge derjenigen Zeichenfolgen, die als „dazugehörig" gelten. Ob sie etwas aussagen, ist eine ganz andere Frage; das ist genau die Trennung von Syntax und Semantik.

$L_1$ oben enthält unendlich viele Wörter. Man kann sie nicht aufzählen, und ein Programm kann keine unendliche Liste durchsuchen.

Also braucht man eine endliche Beschreibung einer möglicherweise unendlichen Menge. Genau das leistet eine Grammatik.

Eine Grammatik besteht aus Regeln, mit denen sich Wörter erzeugen lassen. Man beginnt bei einem Startsymbol und ersetzt so lange, bis nur noch Zeichen des Alphabets übrig sind.

Beispiel für $L_1 = \{a^n b^n \mid n \ge 1\}$, also gleich viele $a$ wie $b$, alle $a$ zuerst:

S → a S b
S → a b

Gelesen: „$S$ darf durch $aSb$ ersetzt werden, oder durch $ab$."

Eine Ableitung wendet die Regeln nacheinander an:

Die Zeichen, die ersetzt werden dürfen ($S$), heißen Nichtterminale und stehen üblicherweise groß. Die Zeichen des Alphabets ($a$, $b$) heißen Terminale und werden nicht weiter ersetzt. Eine Ableitung ist fertig, wenn kein Nichtterminal mehr übrig ist.

Das ist der Kern des ganzen Kapitels, und die Antwort steckt in einer einzigen Eigenschaft: Rekursion.

Die Regel $S \to aSb$ enthält auf der rechten Seite wieder $S$. Man kann sie deshalb beliebig oft anwenden, bevor man mit $S \to ab$ abbricht. Jede Anwendung erzeugt ein weiteres Paar $a$ und $b$.

Zwei Bestandteile braucht jede solche Grammatik:

Eine rekursive Regel, die das Wort verlängert. Eine Abbruchregel ohne Nichtterminal auf der rechten Seite.

Fehlt die Abbruchregel, endet keine Ableitung, und die Sprache ist leer. Fehlt die Rekursion, ist die Sprache endlich. Das ist dieselbe Struktur wie bei einer Schleife: Rumpf und Abbruchbedingung.

Für Programmiersprachen benutzt man eine besser lesbare Schreibweise, die erweiterte Backus-Naur-Form. Sie kennt drei zusätzliche Zeichen:

Damit lässt sich vieles ohne Rekursion ausdrücken. Eine ganze Zahl mit optionalem Vorzeichen:

Ziffer     = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
Zahl       = [ "-" ] Ziffer { Ziffer } ;

Gelesen: „Eine Zahl besteht aus einem optionalen Minuszeichen, danach einer Ziffer, danach beliebig vielen weiteren Ziffern."

Die geschweiften Klammern übernehmen hier die Rolle der Rekursion, und deshalb sind auch mit EBNF unendlich viele Wörter beschreibbar. Beachte außerdem: Die Regel verlangt mindestens eine Ziffer, denn eine steht vor der Wiederholung. Ohne diese eine Ziffer wäre auch das leere Wort eine Zahl.

Ein etwas größeres Beispiel, ein Bezeichner in einer Programmiersprache:

Buchstabe  = "a" | "b" | … | "z" | "A" | … | "Z" ;
Bezeichner = Buchstabe { Buchstabe | Ziffer | "_" } ;

Daraus liest man unmittelbar zwei bekannte Regeln ab: Ein Bezeichner beginnt mit einem Buchstaben, und danach sind Buchstaben, Ziffern und Unterstriche in beliebiger Folge erlaubt. Genau das prüft ein Übersetzer, wenn er einen Variablennamen liest.

Jede Programmiersprache ist über eine Grammatik definiert. Der Übersetzer benutzt sie für zwei Aufgaben:

Prüfen, ob der Quelltext zur Sprache gehört. Tut er es nicht, entsteht ein Syntaxfehler, und zwar genau an der Stelle, an der keine Regel mehr passt. Das erklärt die Beobachtung aus Klasse 9, dass die gemeldete Zeile nicht immer die Ursache ist: Gemeldet wird, wo der Übersetzer stolpert.

Zerlegen in eine Struktur. Aus $2 + 3 \cdot 4$ entsteht ein Baum, in dem die Multiplikation tiefer steht als die Addition. Erst diese Struktur legt fest, dass zuerst multipliziert wird. Punkt vor Strich ist also keine Zusatzregel des Rechners, sondern steckt bereits in der Grammatik.

Eine Grammatik beschreibt ausschließlich die Form. Der Satz aus der Einführung ist grammatisch korrekt und sinnlos; in einer Programmiersprache ist $\texttt{flaeche := laenge + breite}$ ebenso korrekt und falsch gemeint.

Die Semantik legt fest, was ein syntaktisch richtiges Konstrukt bedeutet, also welche Wirkung es bei der Ausführung hat. Sie lässt sich nicht mit einer Grammatik beschreiben, und deshalb kann kein Übersetzer prüfen, ob dein Programm das Richtige tut. Er prüft die Form; für die Bedeutung bist du zuständig.