Exkurs - Shift-Reduce-Parser

Ein Kellerautomat zur Simulation einer Rechtsableitung

Wir betrachten weiterhin die Sprache L_RA 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:

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

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.

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