|
Eingabe: eine kontextfreie Grammatik G = (N,T, P, S) ohne Zyklen und  -Regeln
und ein Eingabewort w = x1x2 · · · xn mit n > 0.
Die Produktionen in P sind nummeriert 1, 2, . . . , p.
Ausgabe: Rechtsparse, wenn existent, sonst "Fehler"
Methode:
- Ordne die Regeln willkürlich.
- Eine Konfiguration wird durch das 4-Tupel (s, i, L1, L2) beschrieben: mit:
- s: Zustand des Algorithmus. Der Algorithmus kann sich in den Zuständen q (normaler Modus), b (Backtracking) oder t (Terminiert) befinden.
- i: Position des Eingabezeigers. An der Position n+1 sollte der rechte Rand des Wortes durch $ markiert sein.
- L1: die erste push-down-Liste enthält Elemente (N
 T)*,
mit denen der Wortteil links vom Eingabezeiger abgeleitet werden kann. Der Kopf der Liste befindet sich rechts. Sie verhält sich wie ein Keller.
- L2: die zweite push-down-Liste (L2), in der die Reduktionen und Shift-Operationen vermerkt werden,
die von der bisherigen Eingabe zur in L1 festgehaltenen Rechtsatzform geführt haben. Der Kopf dieser Liste befindet sich links.
- Die Ausgangskonfiguration ist (q, 1, $, ).
- Der Algorithmus selbst unterteilt sich in 5 Schritte. Beginnend bei Schritt 1 wird der passende Übergang ausgesucht.
- Schritt 1: Versuch der Reduktion
- (q, i, L1w1, L2) |- (q, i, L1A, jL2), wenn die Regel A
 w1
die j-te Regel in P ist und die erste rechte Regelseite (nach der Ordnung unter Punkt 1), die einen Suffix von L1 bildet.
Konnte Schritt 1 angewendet werden, gehe zu Schritt 1, sonst zu Schritt 2.
- Schritt 2: Shift
- (q, i, L1, L2) |- (q, i + 1, L1a, sL2), wenn i
 n + 1.
Falls i = n + 1 gehe zu Schritt 3.
Das aktuelle Eingabesymbol wird in den Keller geschoben. Dieser "shift" wird durch ein "s" in der Parselist vermerkt.
Wenn Schritt 2 ausgeführt werden konnte, gehe zu Schritt 1.
- Schritt 3: Akzeptieren
- (q, n+1, $S, ) |- (t, n+1, $S,
 );
Ausgabe von h(), wobei h(s) =
und h(j) = j. h() ist ein umgekehrter Rechtsparse von w.
Halte an.
Konnte Schritt 3 nicht angewendet werden, gehe zu Schritt 4.
- Schritt 4: Übergang in den Backtrackmodus
- (q, n+1, L1, L2) |- (b, n+1, L1, L2) vorausgesetzt L1 $S
(dann könnte im Schritt 3 akzeptiert werden).
Gehe zu Schritt 5.
- Schritt 5: Backtracking
- Vier mögliche Übergänge gibt es im Backtrackmodus.
- Alternative Reduktion: (b, i, L1A, jL2) |- (q, i, L1'B, kL2), wenn die j-te Regel in P Aw1 ist
und die nächste Regel (in der Ordnung unter 1), deren rechte Regelseite einen Suffix von L1w1 bildet,
Bw2 ist Diese Regel hat die Nummer k.
L1w1 = L1'w2.
Gehe zu Schritt 1.
- Reduktion rückgängig: (b, n + 1,L1A, jL2) |- (b, n + 1,L1w1, L2), wenn die j-te Regel in P A w1 ist und keine alternativen Reduktionen von L1w1 möglich sind.
Gehe zu Schritt 5.
- Shift statt Reduktion: (b, i, L1A, jL2) |- (q, i+1, L1w1a, sL2), wenn i n+1 und die j-te Regel in P Aw1 ist und keine alternativen Reduktionen von L1w1 möglich sind.
Gehe zu Schritt 1.
- Shift rückgängig: (b, i, L1a, sL2) |- (q, i - 1, L1, L2), wenn das oberste Symbol von L2 "s" -für ein Shift- ist.
Gehe zu Schritt 5.
|
1
2
3
4
5
Üben