Eingabe: Eine kontextfreie Grammatik G = (N,T, P, S) und ein Wort w = a1a2 · · · an
Ausgabe: Produktionsmengen I0, I1, . . . ,In.
Methode:
- Initialisierung: Für jede Regel S
z in P,
füge [S • z, 0] zu I0 hinzu.
Nun führe Schritt 2 und 3 solange aus, bis zu I0 keine neuen Items mehr hinzukommen.
- Wenn [B w •, 0] in I0 ist,
dann füge für jedes [A x • By, 0]
hinzu [A xB • y, 0].
- Wenn [A x • By, 0] ein Item in I0 ist,
dann füge für jede Regel B w in P
den Item [B • w, 0] hinzu (falls nicht schon vorhanden).
Ij wird auf der Basis der I0, I1,. . . ,Ij-1 konstruiert:
-
(Scann)
Für jedes [B x • ay, i] in Ij-1 mit a = aj
füge [Bxa • y, i] zu Ij
Wiederhole Schritt 5 und 6 solange, bis keine neuen Items mehr hinzugefügt werden können.
-
(Complete)
Wenn [A w •, i] in Ij ist, dann suche in Ii
nach Items der Form [B x • By, k]
und füge für jeden gefundenen Item [BxB • y, k] Ij hinzu.
- (Predict)
Wenn [Ax • By, i] ein Item in Ij ist,
dann füge für jede Regel B w in P
den Item [B • w, i] hinzu (falls nicht schon vorhanden).
w,x,y und z sind Teilwörter aus (T
N)*.
A und B bezeichnen Elemente aus N
|
|
Benutzer: Gast •
Besitzer: matthias • Zuletzt geändert am:
|
|
|
1
2
3
4
5
Üben