Kontextfreie Grammatiken verstehen

Warum der Rechner die Klammer vermisst

Eine Grammatik ist ein Satz von Regeln, der beschreibt, welche Wörter zu einer Sprache gehören. Mit ihr entscheiden Sie zum Beispiel, ob in einer Formel jede Klammer, die aufgeht, auch wieder zugeht.

Ein Tabellenprogramm meldet bei =(2+3*4 sofort einen Fehler. Dahinter steckt eine Grammatik, die verschachtelte Klammern kennt. Das schafft kein endlicher Automat und kein regulärer Ausdruck.

Am Ende dieser Lektion

Notiz

Ich kann mit einer Grammatik entscheiden, ob ein Wort gültig ist.

Schlüsselwörter

Begriff	Was er bedeutet	Beispiel
Grammatik	ein Satz von Regeln für die Wörter einer Sprache
Regel	eine Zeile, die ein Zeichen durch andere ersetzt	K → ( K ) K
Terminal	ein Zeichen, das im fertigen Wort steht	(
Nichtterminal	ein Platzhalter, den eine Regel ersetzt	K
Ableitung	die Schritte vom Startzeichen zum fertigen Wort
Verschachtelung	ein Teil, der innen in einem gleichartigen Teil steht

Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.

Eine Grammatik ersetzt Zeichen nach Regeln

Eine Grammatik hat Terminale, das sind die Zeichen im fertigen Wort, und Nichtterminale, das sind Platzhalter. Eine Regel sagt, wodurch ein Platzhalter ersetzt werden darf.

Für Klammern genügt eine Regel mit zwei Seiten: K darf zu ( K ) K werden, oder zu nichts. Ein Wort ist gültig, wenn es sich vom Startzeichen K aus so ableiten lässt.

Die Grammatik für Klammern

Regel	Gelesen als	Beispiel
K → ( K ) K	Eine Klammer auf, ein K, eine Klammer zu, danach wieder ein K	(()) entsteht daraus
K → leer	K darf auch verschwinden	beendet jede Ableitung

Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.

Die Ableitung von (()) Schritt für Schritt

Code: python

# Grammatik fuer Klammern:  K -> ( K ) K  oder leer.
# Jeder Schritt ersetzt das linkeste K durch eine Regel.
schritte = [
    "K",
    "( K ) K",
    "( ( K ) K ) K",
    "( ( ) K ) K",
    "( ( ) ) K",
    "( ( ) )",
]
for nummer in range(len(schritte)):
    print(nummer, schritte[nummer])
# Aendern Sie die Schritte so, dass "( ) ( )" entsteht.

Eine Grammatik kann verschachteln

In der Regel K → ( K ) K kommt K auf der rechten Seite wieder vor. So darf innen in einer Klammer wieder eine Klammer stehen, beliebig tief.

Ein Automat kann das nicht, denn er müsste die Tiefe zählen und hat nur endlich viele Zustände. Grammatiken wie diese heißen kontextfrei: Eine Regel ersetzt K, ganz gleich, was daneben steht.

Ein häufiger Fehler

Warnung

Viele denken, man prüfe Klammern, indem man „(“ und „)“ zählt. Gleich viele reichen aber nicht: )( hat von beiden eine. Es zählt die Reihenfolge. Eine Klammer zu braucht eine offene davor, und ([)] ist ungültig, obwohl die Zahlen stimmen.

bison liest eine Grammatik und baut den Parser

Die Grammatik eines echten Rechners steht in der Datei calc.y. bison macht aus ihr einen Parser, der prüft, ob eine Eingabe gültig ist.

Dort steht dieselbe Idee wie bei den Klammern: expr darf zu ( expr ) werden. Die Befehle zeigen die Regeln und füttern den Rechner mit Rechnungen, gültigen und ungültigen.