Parser-Algorithmus

Algorithmen > Parser-Algorithmus

Die Aufgabe des Parsers besteht in der syntaktischen Analyse von Texten. Er geht aus von einem Regelsystem (Grammatik), das die erlaubten Möglichkeiten der Abfolgen von Token definiert. Bei jedem neuen Schritt des Parsers, testet dieser, ob das aktuell ermittelte Token ein erlaubtes Folge-Token ist oder nicht. Falls nicht, ist das Parsen des Textes gescheitert, falls ja, wird zu der durch das Token bestimmten Alternative des Regelsystems fortgeschritten.

Die Entscheidung über die Zulässigkeit des nächsten Tokens wird anhand der Zugehörigkeit zu vorberechneten Tokenmengen gefällt: den Anfängermengen der möglichen Nachfolgerknoten samt deren SKIP-Alternativen. Hier ist die Funktion des Parsers mit den Scannern verschränkt, denn diese Tokenmengen bilden genau die Gesamtmengen der einzelnen Scanner, von denen im vorherigen Abschnitt die Rede war. In den Projekteinstellungen kann die Menge der Token, die an einer Stelle des Regelsystems getestet wird auf die Menge der für den Fortgang des Parsens erlaubten Token eingeschränkt werden. Dies ergibt einen Geschwindigkeitsvorteil insbesondere dann, wenn das Lexikon des Parsers groß ist.

Der Parser-Algorithmus ist nun also dieser:

1. Anfänger der Startregel testen

Zu Beginn der Textanalyse ist noch kein Token erkannt. Daher wird durch einen lokalen Scanner der Textanfang mit der Menge von Token verglichen, die als Anfänger der Startregel in Frage kommen. ( Sollen auch andere Produktionen des Parser unmittelbar aufgerufen werden können, so müssen entsprechend auch für diese die Mengen der terminalen Anfänger berechnet und ein Scanner konstruiert werden.)

2. Fortgang zum erwarteten Terminalsymbol

Ist ein Token gefunden, so wird zu demjenigen nachfolgenden Knoten fortgegangen, zu dessen Anfängermenge das Token gehört. Dies wird durch die Reihe der löschbaren Knoten solange wiederholt, bis der Knoten erreicht ist, der das Terminalsymbol repräsentiert.

3. Nachfolger innerhalb und außerhalb der Produktion testen

Jedem Terminal-Knoten ist ein Scanner zugeordnet, der aus dem Bereich der möglichen nachfolgenden Terminalsymbole dasjenige ermittelt, das zum aktuellen Text passt.  Nun müssen allerdings zwei Fälle unterschieden werden:

a) innerhalb der dem Terminalsymbol übergeordneten Produktion liegt zwischen diesem Terminal und den die Produktion abschließenden Symbolen stets ein weiteres Terminalsymbol. In diesem Fall wird das nächste Token ermittelt und es wird fortgesetzt wie unter Punkt 2.

b) dem Terminalsymbol folgt in seiner Produktion eine löschbare Struktur derart, dass deren letztes Symbol die Produktion abschließt. In diesem Fall hängt die Menge der möglichen Nachfolger des Terminalsymbols von der Menge der Nachfolger der Produktion ab. Eine Produktion kann aber an verschiedenen Stellen einer Grammatik aufgerufen werden, und an den jeweiligen Stellen können jeweils andere Token nachfolgen. Es wird also zunächst die unvollständige Menge derjenigen Nachfolger getestet, die innerhalb der aktuellen Produktion erwartet werden, und weiter wird mit Punkt 3 fortgesetzt.

Bemerkung:

Der TextTransformer ist ein interpretierter Parsergenerator. Er ist ein Parser, der Regelskripte parst  um aus ihnen einen neuen Parser zu erzeugen.  Der erzeugte Parser wiederum parst Eingabetext, um ihn zu transformieren. Da der Parser des TextTransformers von ihm selbst erzeugt ist, unterscheiden sich die Algorithmen beim Parsen der Skripte und beim Parsen des Eingabetextes nicht.

Diese Seite gehört zur TextTransformer Dokumentation