Scanner-Algorithmus

Algorithmen > Scanner-Algorithmus

Ein Scanner versucht das nächste Token zu ermitteln, das auf den aktuellen Text passt. Dabei geht er von einer vordefinierten Gesamtheit aller möglichen Token aus. Im Unterschied zu anderen Parsergeneratoren arbeitet der TextTransformer nicht mit nur einem Scanner sondern es ist auch möglich mit einer Vielzahl kleiner Scanner jeweils nur spezifische Teilmengen der Gesamtheit aller in der Grammatik vorkommenden Token zu testen. Diese Teilmengen bestehen aus den Anfängermengen des aktuellen Knotens und den SKIP-Alternativen. Das Prinzip des Scanners bleibt jedoch das gleiche: für jedes Token des vorgegebenen Reservoirs muss getestet werden, ob es passt oder nicht. Für den Fall, dass es mehrere Token gibt, die passen, existiert ein Algorithmus zur Entscheidung zwischen diesen Kandidaten.

1. Anfängermenge testen

Der TextTransformer versucht zunächst eine Übereinstimmung zwischen dem Text an der aktuellen Position und einem der Token aus der Anfängermenge des aktuellen Knotens zu finden. Gibt es genau ein passendes Token, so ist die lexikalische Analyse an diesem Punkt erfolgreich abgeschlossen.

2. Vorzug der längsten Übereinstimmung

Falls es mehr als eine Übereinstimmung an der gleichen Textposition gibt, so wird dasjenige Token greifen, das die längste Übereinstimmung mit dem Text ergibt, d.h. die größte Anzahl von Zeichen des Eingabetextes abdeckt.

3. Vorzug literaler vor nicht literalen Token

Kommen immer noch mehrere Token in Frage, wird einem literalen Token der Vorzug vor einem nicht literalen gegeben.

4. Vorzug der längsten Übereinstimmung des ersten Unterausdrucks

Falls beide Kandidaten nicht literal sind,  wird dasjenige gewählt, dessen erster Unterausdruck die längste Übereinstimmung ergibt.

5. Vorzug der längsten Übereinstimmung des nächsten Unterausdrucks

Bei erneuter Mehrdeutigkeit wird die Länge der Übereinstimmungen der weiteren Unterausdrücke als Auswahlkriterium herangezogen.

6. SKIP-Alternative

Passt keines der Token der Anfängermenge an der aktuellen Textposition,  so wird geprüft, ob eine SKIP-Alternative vorhanden ist. Gibt es aus der zum SKIP-Symbol gehörenden Menge genau ein passendes Token, so ist die lexikalische Analyse an diesem Punkt erfolgreich abgeschlossen.

7. nächstliegende Textposition

Gibt es mehrere Kandidaten, zu denen im Text gesprungen werden kann, so wird dasjenige Token  ausgewählt, dessen Übereinstimmung mit dem Text der aktuellen Textposition am nächsten liegt.

8. längsten Übereinstimmung (analog Punkt 2-5)

Passen mehrere Token der zum SKIP-Symbol gehörenden Menge an der gleichen Textposition, so wird wie unter Punkt 2-5 gemäß der längsten Übereinstimmung entschieden.

Es ist darauf zu achten, dass bei Token, die in einer Verzweigung alternativ zueinander stehen, nicht eine Definition die Definition eines anderen Tokens umschließt. TETRA kann für diesen Fall keinen Warnhinweis geben.

Beispiel:

IDENT = \w+

NUMBER = \d+

Da "\w" u.a. Menge der Ziffern enthält, umschließt die Definition von IDENT auch die von NUMBER. Im Falle einer Alternative

IDENT | NUMBER

ist nicht auszumachen, welches der beiden Token greift, wenn eine reine Zahl in der Eingabe steht (->Anmerkung). Die Alternative von IDENT und NUMBER muss nicht explizit in einer Regel formuliert sein um zu Problemen führen zu können, sondern kann in der Anfängermenge von Verzweigungen versteckt sein, von denen aus IDENT und NUMBER indirekt erreichbar sind.

Allgemein gilt, dass es empfehlenswert ist ein Token möglichst spezifisch zu definieren. So würde z.B.

IDENT = [[:alpha:]|_]\w*

das obige Problem von vornherein ausschließen, da IDENT dann nicht mit einer Ziffer beginnen kann, NUMBER aber immer mit einer Ziffer beginnen muss.

Anmerkung: Tatsächlich greift IDENT, während bei einer Definition von IDENT als "[[:alpha:]|_|\d]+" NUMBER greift. Dies wird durch die interne Implementation der Regex-Library bestimmt und kann z.Z. nicht allgemein in Regeln gefasst werden.

Diese Seite gehört zur TextTransformer Dokumentation