Search Home Preferences Login Help

2.1 Items und Itemsets

Der Aufbau einer geteilten Produktion Falls die obige Regel Bestandteil der korrekten Analyse von w ist, so müssen diese Bestandteile im Analysebaum vorhanden sein.

Beim Earley-Parseverfahren werden für jede Position im Wort Itemsets (Produktionsmengen) konstruiert. Eine jede enthält items (geteilte Produktionen, dotted rules). Anhand dieser geteilten Produktionen kann der Parsefortschritt verfolgt werden. Sei w = a1a2 · · · an [A X1X2 · · ·Xk • Xk+1 · · ·Xm, i] ist ein Item für w, wenn AX1 · · ·Xm eine Regel in P ist und 0in. Der Punkt ' • ' ist dabei ein nicht in der Grammatik vorkommendes Symbol. Für jedes j, 0jn wird ein Itemset Ij konstruiert. Dieses enthält [Ax • y, i] gdw. es gibt ein w1 und w2, so dass S =>* w1Aw2 und w1 =>* a1 · · · ai und x =>* ai+1 · · · aj. w L(G) gdw. es gibt einen Item [Sz•, 0] in In. Eine S-Regel überspannt die Eingabe von Anfang bis Ende (0 bis n). Die Items geben mir Auskunft darüber, mittels welcher Regeln der erste Teil des Wortes (bis zum Index j des Itemsets) abgeleitet werden kann. Die Symbole bis zum Punkt sind mit der Ableitung des gegebenen Wortes konsistent. Die Symbole nach dem Punkt machen Voraussagen über die weitere Ableitung.

Einführung 1   2   3   4   5 Teilschritte

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