Tokenmengen

Algorithmen > Tokenmengen

Die Entscheidung über die nächste Verzweigung in der Grammatik kann in speziellen Fällen von einer Vorausschau im Text oder vom semantischen Prädikaten abhängig gemacht werden. Im Regelfall aber, um den es im Folgenden geht wird diejenige grammatische Alternative gewählt, deren Anfängersymbol im Text als nächstes erkannt wird. Neben den bereits erläuterten Präferenzregeln kann dies von der Menge der Token abhängen, welche getestet werden: Token, die nicht getestet werden, können auch keine Konflikte verursachen. Deshalb gibt es in den Projekt- und in den lokalen Einstellungen die Option, nur erwartete Token zu testen. Es kann aber auch gerade erwünscht sein, Konflikte frühzeitig zu erkennen. So dürfen z.B reservierte Worte einer Programmiersprache nicht als Namen für Variablen verwendet werden:

double int;  // Fehler

In diesem Fall ist die Option nur erwartete Token zu testen zu deaktivieren. Zu erörtern bleiben aber die Tokenmengen bei den Verwendung von Produktionen außerhalb der Hauptparsers.

Tokenmengen in Einschlüssen, Unterparsern und bei der Vorausschau.

Besonders im Falle von Kommentaren ist augenfällig, dass hier Konflikte mit den Token des Hauptparsers unerwünscht sind.

CppComment ::= "/*" ( SKIP | STRING )* "*/" 

// ! diese Definition ist für verschachtelte Kommentare nicht geeignet

/* int iCount : Zähler */

Würde das Schlüsselwort int hier erkannt, könnte der Kommentar nicht geparst werden.

Daher können Einschlüsse im TextTransformer ein neues Produktionen-System bilden, das von der Tokenmenge des Hauptparsers unabhängig ist.

Für Vorausschau-Produktionen gilt genau das Gegenteil: hier ist es zumeist erwünscht, das die gleichen Token erkannt werden wie im Hauptparser.

Folgende Regeln ermöglichen eine flexible Anpassung der Tokenmengen an die jeweiligen Zwecke:

1. Jede Produktion, die nicht von einer anderen Produktion aufgerufen wird, d.h. jede Start-Produktion bildet das Fundament für ein eigenständiges Produktionen-System mit eigener Tokenmenge. Diese Menge ergibt sich als Vereinigung aller  in dem System vorkommenden Token. (In dem System verwendete Vorausschau-Produktionen gelten hier nicht als aufgerufen, gehören also nicht automatisch zum System). Die Startregel des Hauptparsers bildet das erste System.

2. Wird eine Produktion in mehreren Systemen verwendet, dann werden die Tokenmengen dieser Systeme vereinigt.

Beispiel:

Prod1 ::= IF( Prod2() ) Prod2 ELSE Prod3 END

Prod2 ::= "a" "b" 

Prod3 ::= IF( !Prod4() ) "c" "d" ELSE  ID+ END

Prod4 ::= SKIP "h"

Ausgehend von der Startregel Prod1 sind die Regeln Prod2 und Prod3 zu erreichen. Die Tokenmenge dieses Systems ist: "a", "b", "c", "d", ID.

Prod2 wird als Vorausschau verwendet. Da diese Produktion aber auch zum System der Startregel gehört, ist die in Prod2 von globalen Scannern getestete Tokenmenge mit der des Hauptsystems identisch:  "a", "b", "c", "d", ID.

Die Vorausschau mit Prod4 hingegen ist vom Hauptsystem unabhängig. Prod4 bildet somit ein eigenes System, deren Tokenmenge nur aus "h" besteht.

Würde nun Prod4 erweitert zu:

Prod4 ::= SKIP "h" Prod2?

dann wäre Prod2 ein Teil von beiden bisherigen Systemen. In diesem Fall werden gemäß dem obigen Punkt2 die Tokenmengen der beiden Systeme vereinigt:  "a", "b", "c", "d", "h", ID.

Diese Erweiterung von Prod4 kann zu Folge haben, dass "a" im Text "a h" nicht mehr von SKIP übersprungen wird.

Diese Seite gehört zur TextTransformer Dokumentation