Logo des digitalen Schulbuchs inf-schule.de. Schriftzug in Zustandsübergangsdiagramm eines endlichen Automaten.

Exkurs - Shift-Reduce-Parser

Ein Kellerautomat zur Simulation einer Rechtsableitung

Wir betrachten weiterhin die Sprache LRA der vereinfachten Rechenausdrücke mit der Grammatik G:

A -> A+S
A -> S
S -> S*F
S -> F
F -> (A)
F -> z 

Die Grammatik G geben wir in JFlap ein:

JFlap - Grammatik

Mit den Menupunkten [Convert][Convert CFG to PDA (LR)] lässt sich jetzt ein Kellerautomaten erzeugen:

JFlap - Kellerautomat

Mit [Export] kann man den erzeugten Kellerautomaten in ein neues Fenster kopieren.

Wie der erzeugte Kellerautomat arbeitet, soll anhand des Eingabeworts z+z*(z+z) verdeutlicht werden. Mit [Input][Fast Run] lässt sich eine Ableitung zu einem Eingabewort (hier z+z*(z+z)) erzeugen.

JFlap - Ableitung

Die folgende Übersicht gibt die gesamte Ableitung wieder. Eingetragen sind hier der jeweilige Zustand, der aktuelle Kellerinhalt und das verbleibende Eingabewort. Zusätzlich sind die benutzten Zustandsübergänge angegeben sowie eine Kommentierung der Übergänge.

Zustand; Kellerinhalt   Eingabewort             Aktion
X

Fehler melden

X

Suche