Algorithmen und Datenstrukturen

Datentypen

Chart-Kante:

Repräsentiert eine vollständige oder partielle Konstituente. Sie besitzt einen Start- und einen Endknoten, eine Markierung (ein Symbol) und eine Fortsetzung (eine Folge von Symbolen). Ist die Fortsetzung leer, ist die Kante inaktiv, sonst aktiv.

Chart-Knoten:

Repräsentiert eine Stelle in der zu analysierenden Wortfolge.

Aktive Chart:

Repräsentiert eine Aufzeichnung aller Konstituenten und Teilkonstituenten.

Vorschlagsliste:

Eine Liste von aktiven Kanten, die auf Bearbeitung warten.

Prozeduren

Chart-Initialisierung:

Generiert eine aktive Chart aus einer Folge von Eingabewörtern. Zuerst wird eine Kette von Knoten und Kanten, die mit dem entsprechenden Wort der Folge markiert sind, generiert. Diese Kanten werden dann mit Kanten, die mit den Lexikoneinträgen der Wörter markiert sind, überspannt (für jeden Eintrag eine Kante).

Chart-Analyse:

Analysiert einen Satz auf der Basis einer kontextfreien Grammatik. Die Kanten aus der Vorschlagsliste werden nach und nach mit Hilfe von Kanten-Kombination in die Chart eingefügt. Bei aktiven Kanten wird Kategorie-Vorschlagen auf ihren Endknoten und das erste Element ihrer Fortsetzung angewendet. Beide Funktionen können neue aktive Kanten in die Vorschlagsliste einfügen. Erzeugt die Prozedur eine inaktive Kante, die den gesamten Satz überspannt und mit dem Startsymbol der Grammatik markiert ist, so wird die Prozedur erfolgreich beendet. Ansonsten bricht das Verfahren ab, wenn die Vorschlagsliste leer ist.

Kategorie-Vorschlagen:

Sucht nach einer Konstituente eines bestimmten Typs, die an einem gegebenen Knoten starten soll. Falls es noch keine Kante in der Vorschlagsliste und in der Chart gibt, die an dem gegebenen Knoten beginnt und mit dem gegebenen Kategoriebezeichner markiert ist, so wird eine solche leere aktive Kante erzeugt und in die Vorschlagsliste eingefügt.

Kanten-Kombination:

Fügt eine neue Kante in die Chart ein. Versucht dann, die Kante nach vorne bzw. nach hinten fortzusetzen, je nachdem, ob sie inaktiv oder aktiv ist. Dies geschieht mit Hilfe der Funktion Aktive-Kante-Fortsetzen.

Aktive-Kante-Fortsetzen:

Die Funktion erzeugt eine neue Kante aus einer inaktiven und einer aktiven Kante gemäß der fundamentalen Regel der Chart-Analyse (siehe S. ). Sie fügt die neue Kante in die Vorschlagsliste ein, wenn sie aktiv ist, sonst in die Chart.