Anfängermenge

Glossar > Anfängermenge

Jeder Knoten im TETRA-Syntaxbaum und jedes Symbol der Grammatik ist durch zwei Mengen von Token charakterisiert: die Menge seiner Anfänger und die Menge seiner Nachfolger. Die Anfängermenge ist bei der durchgeführten TopDown-Analyse eines Textes von besonderer Wichtigkeit, da sie den Fortgang der Analyse bestimmt.

Die Anfängermenge eines Knotens enthält alle diejenigen Token, deren Erkennung im Text den Parser veranlassen, gerade diesen Knoten als nächsten zu wählen und nicht einen anderen. Passt der aktuelle Text zu keinem der Token der Anfängermenge des Knotens, so wird derjenige alternative Knoten gewählt, dessen Anfängermenge ein Token enthält, zu dem der Text passt. Gibt es keine derartige Alternative, so wird das Parsen des Eingabetextes mit einer Fehlermeldung abgebrochen. Um zwischen Alternativen eindeutig entscheiden zu können, müssen die Anfängermengen der Alternativen disjunkt sein, d.h. es darf kein Token geben, das in mehr als einer der alternativen Anfängermengen enthalten ist.

Die Anfängermengen entscheiden somit über den Fortgang der Textanalyse und in der Berechnung dieser Mengen besteht die zentrale Leistung des TextTransformers. Zur Berechnung dieser Mengen müssen mehrere Fälle unterschieden werden.

Der einfachste Fall ist der, bei dem ein Knoten ein Terminalsymbol repräsentiert. Hier besteht die Anfängermenge genau aus diesem Terminalsymbol selbst.

Beispiel:

Die Anfängermenge von "TETRA" ist die Menge, die als einziges Element das Token "TETRA" enthält.

Die Anfängermenge einer Kette von Symbolen ist die Anfängermenge ihres ersten Gliedes (sofern es nicht löschbar ist s.u.)

Beispiel:

Die Anfängermenge von "TETRA" "steht" "für" "Texttransformer" ...  ist die Menge, die als einziges Element das Token "TETRA" enthält.

Mehr Elemente umfassen Anfängermengen von Knoten, die Alternativen enthalten. Die Anfängermenge eines solchen Knotens besteht aus der Vereinigung aller Anfängermengen der einzelnen Alternativen.

Beispiel:

Die Anfängermenge von ( "TETRA" ... | "Texttransformer" ... ) ist die Menge der Token  "TETRA" und "Texttransformer".

Am schwierigsten ist die Ermittlung von Anfängermengen löschbarer Knoten. Das sind Optionen "(...)? und optionale Wiederholungen "(...)*". Zunächst sind Anfänger dieser Knoten alle Token, mit denen die alternativen Ketten innerhalb der optionalen Struktur beginnen. Für:

( "sehr"+ | "super" )? "gut"

ist dies die Menge aus den Token "sehr" und "super". Wegen der Optionalität des Knotens soll es aber nicht zum Abbruch des Parsens kommen, wenn an der aktuellen Textposition weder das Token "sehr" noch "super" zu finden sind. Das Parsen soll mit dem nachfolgenden Knoten fortgesetzt werden. Um beim aktuellen löschbaren Knoten bereits entscheiden zu können, ob das Parsen fortgesetzt werden kann muss die bisherige Anfängermenge {"sehr", "super"} mit der Nachfolgermenge vereinigt werden. (Dabei müssen die zu vereinigenden Mengen untereinander wiederum disjunkt (s.o.) sein.) Die Anfängermenge der Beispielsoption ist also: {"sehr", "super", "gut"}. Die Beispielsoption mag nun die Produktion  attribut1 bilden:

attribut1 = ( "sehr" ... | "super" ... )? "gut"

Ein zweites Attribut sei schlicht:

attribut2 = "cool"

und eine Produktion laute:

urteil = "Der TextTransformer funktioniert" ( attribut1 | attribut2 )

Wird mit der urteil-Produktion der Text:

"Der TextTransformer funktioniert gut"

analysiert, so wird zunächst "Der TextTransformer funktioniert" erkannt. Um entscheiden zu können, ob attribut1 oder attribut2 folgt, wird untersucht, ob der anschließende Text: " gut" überhaupt zu einem der in der Grammatik vorkommenden Token:  {"sehr", "super", "gut", "cool"} passt. Er passt zu "gut" und "gut" gehört zur Anfängermenge von attribut1 nicht aber zu der von attribut2. Somit ist klar, dass das erste Attribut zutrifft.

Die Nachfolgermenge ist die Menge derjenigen Token, die auf den Knoten folgen können

Semantische Aktionen werden innerhalb des Syntaxbaums auch als Knoten dargestellt.  Bei ihnen handelt es sich um löschbare Knoten. Ihre Anfängermenge ist genau ihre Nachfolgermenge.

Diese Seite gehört zur TextTransformer Dokumentation