Verfahren nach Earley

Home

Preferences

Help

2.1 Teilabläufe

Die Abläufe Predict, Complete und Scan treten im Algorithmus immer wieder auf.

Falls und w[an der Stelle 1]='a', so muss
Scan
Es findet ein Abgleich zwischem vorhergesagten Terminalsymbol und gegenwärtigem Inputsymbol (markiert durch den Index der statt. Bei Übereinstimmung wird der Punkt über das erkannte Terminalsymbol geschoben und das neue Item eingefügt.

Für und muss eingefügt werden.
Complete
Für alle vollständig abgearbeiteten Regeln (der Punkt befindet sich hinter dem letzten Symbol der rechten Regelseite) wird geschaut, für welche anderen Items sich dadurch der Punkt verschieben lässt. Ist bspw. ein Nomen zwischen den Positionen 3 und 4 erkannt und damit der Item [NP geht über in • N,3] vervollständigt worden, so kann jetzt in der Liste unter 3 nach denjenigen Items gesucht werden, die eine NP vorausgesagt hatten, also in denen der Punkt genau vor dem NP steht. V PV • NP. Für die auf diese Weise hinzugefügten Items wird aufs Neue Predict und Scan ausgeführt.

Für wird für jede S-Regel ein Item eingefügt: und (für die -Regel)
Predict
Jedes vorhergesagte Nichtterminalsymbol (das Symbol genau hinter dem Punkt) wird expandiert. D. h. es werden Items für jede Regel hinzugefügt, in denen dieses Nichtterminal auf der linken Regelseite steht. Da noch kein Symbol der rechten Regelseite erkannt wurde, bleibt auch hier der Punkt vor dem ersten Symbol (auf der rechten Regelseite).

Die Items wurden für die Grammatik G = ({A,B,S},{a,b},P,S) mit den Regeln S ASB, S , A a und B b; und das Wort w = aabb formuliert.

Dotted Rules 1 2 3 4 5 Algorithmus

Benutzer: Gast • Besitzer: matthias • Zuletzt geändert am:

	Die Abläufe Predict, Complete und Scan treten im Algorithmus immer wieder auf.
Falls und w[an der Stelle 1]='a', so muss	Scan Es findet ein Abgleich zwischem vorhergesagten Terminalsymbol und gegenwärtigem Inputsymbol (markiert durch den Index der statt. Bei Übereinstimmung wird der Punkt über das erkannte Terminalsymbol geschoben und das neue Item eingefügt.
Für und muss eingefügt werden.	Complete Für alle vollständig abgearbeiteten Regeln (der Punkt befindet sich hinter dem letzten Symbol der rechten Regelseite) wird geschaut, für welche anderen Items sich dadurch der Punkt verschieben lässt. Ist bspw. ein Nomen zwischen den Positionen 3 und 4 erkannt und damit der Item [NP • N,3] vervollständigt worden, so kann jetzt in der Liste unter 3 nach denjenigen Items gesucht werden, die eine NP vorausgesagt hatten, also in denen der Punkt genau vor dem NP steht. V PV • NP. Für die auf diese Weise hinzugefügten Items wird aufs Neue Predict und Scan ausgeführt.
Für wird für jede S-Regel ein Item eingefügt: und (für die -Regel)	Predict Jedes vorhergesagte Nichtterminalsymbol (das Symbol genau hinter dem Punkt) wird expandiert. D. h. es werden Items für jede Regel hinzugefügt, in denen dieses Nichtterminal auf der linken Regelseite steht. Da noch kein Symbol der rechten Regelseite erkannt wurde, bleibt auch hier der Punkt vor dem ersten Symbol (auf der rechten Regelseite).