Scanner - Parser Generator 



 Inhalt22-12-2003 

Die aktuelle Version gibts hier zum download [1 MB]

Beschreibung
Arbeitsweise des Scanners
Arbeitsweise des Parsers
Scanner Beispiele
Parser Beispiele



 Beschreibung20-12-2003 

Dieses Werkzeug dient zur Generierung eines Programms, welches Textdateien analysiert und auswertet. Damit ist es mit den Unix/Linux Werkzeugen Lex und Yacc vergleichbar. Die derzeit möglichen Ausgabeformate sind Perl oder Scheme Code. Andere Sprachen könnten aber durchaus hinzugefügt werden. Die Definitionen des Scanners und Parsers sind dabei Sprachunabhängig. Außschließlich die Hilfsfunktionen müssen in der passenden Sprache definiert werden. Dabei ist es aber auch möglich Hilfsfunktionen für jede einzelne Sprache innerhalb eines Projects zu definieren. Auf eine vollständige Abstraktion wurde zu Gunsten der Flexibilität verzichtet.


 Arbeitsweise des Scanners20-12-2003 

Die Eingabedatei wird zunächst in einen String gelesen (in Scheme in eine Liste aus Chars). Zu diesem wird eine Positionsmarke (CurrentPossition) definiert. Anfangs steht diese auf 0 und wandert bei jedem Lesen weiter.

Hilfsfunktionen:

PeekChar(n)
Gibt das Zeichen aus dem String zurück was sich an der Stelle CurrentPosition + n befindet. Somit gibt PeekChar(0) immer das aktuelle Zeichen zurück.

PeekWord(n,from)
Gibt ein Wort der Länge n ausgehend von der Stelle CurrentPosition + from zurück. Somit ergibt PeekWord(5,0) das aktuelle Wort der Länge 5.

PeekWordEq(word)
Liefert 1 wenn das aktuelle PeekWord(length(word),0) genau word entspricht ansonsten 0. Damit ist ein schneller Test möglich, ob ein Suchwort an der aktuellen Stelle steht.

BestMatch(word)
Prüft ob word ein "besseres" Wort ist als das im Prüfbuffer (BestMatchValue) befindliche. Besser heißt hier länger. Damit wird es möglich alle Regeln zu prüfen und die längste passende Regel anzuwenden. BestMatch wird immer dann aufgerufen wenn eine bestimmte Regel passt. Bei jedem Scandurchlauf werden die BestMatch Variablen geleert.

IsItem(list)
Prüft ob sich die Elemente von list an der aktuellen Stelle befinden. Dabei wird für jedes Listenelement PeekWordEq(Element) durchgeführt und bei Erfolg BestMatch angewendet.

IsChain(list)
Prüft ob die Elemente von list mindestens einmal an der aktuellen Stelle vorkommen. Sollte eines der Elemente passen, wird solange weitergetestet bis kein Element mehr gefunden werden kann. Der dadurch entstehende Teilstring wird jeweils mit BestMatch abgeglichen.
Beispiel: InputString = "12Hello" list = ("1","2") würde "12" ergeben da die ersten beiden Zeichen in der Liste enthalten sind. BestMatch wird auf das gefundene Wort angewendet.


IsFromTo(from,to)
Prüft ob der Teilstring from an der aktuellen Stelle gefunden werden kann. Sollte dies der Fall sein, wird solange weitergetestet bis Teilstring to gefunden wird.
Beispiel: InputString = "'Hello'123" from = "'" to = "'" würde "'Hello'" ergeben, da dies zwischen den from und to gefunden wird. BestMatch wird auf das gefundene Wort angewendet.



Die Testfunktionen sind stehts in einer Case Sensitive und einer Case Unsensitive Version vorhanden (zu erkennen durch das IsChainNOCS im Vergleich zu IsChain).
Zu den definierten Regeln wird jeweils eine dieser Funktionen verwendet.
Wurden alle Regeln abgetestet wird das BestMatch Wort ausgewählt und CurrentPossition um die länge dieses Wortes erhöht. Sollte keine Regel an der aktuellen Position gepasst haben, wird eine Warnmeldung ausgegeben das das aktuelle Zeichen ignoriert wurde.
Als Besonderheit gibt es die Everything Regel die genau dies unterdrückt. Alle Teilstrings die zu keiner Regel passen werden in diesem Fall der Everything Tokenclass zugeteilt. Dies kann vorallem für Scanner verwendet werden, die zum Großteil variablen Text beinhalten (wie zum Beispiel HTML).


 Arbeitsweise des Parsers20-12-2003 

Der Parser wird einzig und allein aus der graphischen Baumdarstellung der Parserbeschreibung erstellt. Die verwendete Tag Sprache ist dabei nur eine Überführung in eben diese Baumdarstellung. In dieser Darstellung kann man erkennen welche Struktur der Parser besitzen wird. Sollten rote "X" in diesem Baum auftauchen dann bedeutet dies das ein Tag nicht richtig definiert wurde. Dies kann entweder daran liegen, dass ein unbekanntes Tag benutzt wurde oder ein read Tag kein zugehöriges Token aus der Scannerdifinition besitzt.

Bei der Generierung wird zunächst die Ausgabe (ScanOutput) des Scanners eingelesen. Die gefundenen Token - Value Paare werden in einer Liste gespeichert und wieder eine Positionsmarke definiert (CurrentPossition).

Für jedes <define Label> Tag (in Baumdarstellung als Sterne zu erkennen) wird eine Funktion angelegt. Jede Funktion hat dabei einen Boolean Rückgabewert. Im normal Fall ist dieser immer TRUE (Die Möglichkeit eines FALSE wird später angeführt).

Über ein <goto Label> Tag ist es möglich innerhalb einer Funktion rekursiv in eine andere zu springen. Das heißt, dass nach Abarbeitung der angesprungenen Funktion die Quellfunktion fortgesetz wird. Beispiel: <read "Hello" <goto HELLOSTAT> <goto HELLOEND>> wird das Token "Hello" gefunden wird zunächst die Funktion HELLOSTAT abgearbeitet und anschließend HELLOEND.

Am kann an diesem Beispiel erkennen das der GOTO Befehl nur dann abgeabreitet wird, wenn zuvor der READ Befehl erfolgreich war. Gleiches gilt aber auch für GOTO Anweisungen. Das obige Beispiel etwas anders: <read "Hello" <goto HELLOSTAT <goto HELLOEND>>> ergibt, dass die zweite Funktion nur dann angesprungen wird, wenn die erste erfolgreich verlief (ein TRUE zurückgegeben hat).

Der <read Token> Tag ist natürlich Hauptbestandteil der Parserdefinition. Mit einem READ legt man fest welches Token an welcher Stelle gefunden werden muss/kann. Dabei gelten folgende Regeln:
<read Tokenclass> liest an der aktuellen Stelle eine ganze Tokenklasse. Das heißt, wenn das aktuelle Token in der angegebenen Tokenklasse enthalten ist wird das Innere des Tags ausgeführt.
<read Tokenvalue> liest an der aktuellen Stelle einbestimmtes Token. Es wird also nach einem ganz bestimmten Tokenwert getestet. Für bessere Lesbarkeit werden Tokenvalues in " " eingefasst.

Folgen mehrere read Befehle nebeneinander (<read X <read Y> <read Z>>: ein X gefolgt von einem Y oder Z) bedeutet dies, dass diese als logisches OR angesehen werden. Es wird nacheinander jede Regel geprüft und die erste zutreffende abgearbeitet. Diese Oder Entscheidung wird aber nur dann verwendet, wenn read Anweisungen direkt aufeinander folgen (in gleicher Ebene).
Beispiel: <read X <read Y> <goto SOMEWHERE> <read Z>>
Dies bedeutet, daß genau ein X gefolgt von einem Y gefunden werden muss. Danach wird ein Sprung ausgeführt und nach diesem muss wieder genau ein Z folgen.

Sollte bei einem das entsprechende Token/Tokenclass bei einem read Befehl nicht gefunden werden wird sofort ein Parse-Error ausgegeben! Wenn man nun aber die Möglichkeit haben möchte das ein bestimmtes Token folgen kann aber nicht zwangsweise muss, dann benötigt man eine Epsilon Regel. Eine solche kann für jeden READ Block angegeben werden. Die Epsilon Regel muss wie folgt angegeben werden:
<read ""> Dabei ist es egal an welcher Stelle diese Regel innerhalb eines READ Blocks definiert ist.
Beispiel <read X <read Y> <read "">> ist gleich <read X <read ""> <read Y>>

Damit noch mal zurück zum goto Befehl. Wie bereits gesagt, wird üblicherweise TRUE zurückgegeben es sei denn, die letzte angewendete Regel war eine Epsilon Regel. Dann und nur dann wird FALSE zurückgegeben. Damit ist es möglich eine Folge von Funktionen an das Auffinden bestimmter Tokens zu knüpfen.
Beispiel:
<define ISEND <read END> <read "">>
<define FINDEND <goto ISEND <goto FINDEND>>>

Dises Beispiel scheint verwirrend. Die Abarbeitung entspricht einer Regel: END* es kann ein oder meherere END auftreten oder auch gar keins. Wenn ein END gefunden wurde gibt ISEND TRUE zurück und goto FINDEND wird ausgeführt. Wurde in ISEND die Epsilon Regel angewendet, wird der goto Befehl nicht angewendet.


Das <call FUNCTION> Tag bildet die Schnittstelle zum eigenen Programmcode. Dieser kann im SPG unter Helper Functions definiert werden. Ein CALL sieht dabei immer wie folgt aus:
<call FUNCTIONNAME -1,0,"string"> Dabei steht der Funktionsname direkt für die aufzurufende Funktion (sprachbedingt üblicherweise Case Sensitive). Die Parameter sind dabei fest definiert. Zahlen entsprechen stehts den Token an der Stelle n relative zur aktuellen. Das heißt <read X <read Y <call TEST -1,0>>> würde die Funktion TEST mit den Parametern X und Y - den Tokenclass/Tokenvalue Paaren an den entsprechenden read Tags ausführen. Damit ist es möglich längere Tokenketten erst am Ende der Erkennung in eine Funktion zu geben um dann alles auf einmal auszuwerten. Strings in den Parametern werden dabei immer genau so wie aufgeführt übergeben und können als Merker oder ähnliches an die Funktion mitgegeben werden. Es ist keine feste Reihenfolge für die einzelnen Parameter festgelegt. Demnach ist 0,-1,3,"Test",-1 durchaus als Parameterfolge möglich.
Wichtig: Die Parameter werden als Liste übergenen. Als Vorlage kann man den CALL Wizard benutzen um Grundgerüste für die Hilfsfunktionen zu generieren.
Wichtig: Jede Hilfsfunktion muss einen String zurückgeben. Sollte dies nicht nötig sein gibt man einfach "" zurück (return "";). Der zurückgegebene String wird dabei stehts als neue Zeile in den ParseOutput Buffer geschrieben. ParseOutput wird am Ende entweder in die Ausgabedatei geschrieben oder in der STDOUT ausgegeben (bedingt durch den Aufruf der Funktionen).


 Beispiel Scanner Definitionen21-12-2003 

Beispiel 1 - HTML Scanner:

TokenclassValuesScanmodeCaseSens
Tag< >BetweenNO
IgnoreChars\r \n \tignoreNO
Other everythingNO

Scanergebniss einer einfachen HTML Datei:
(Tag . "<html>")
(Tag . "<body bgcolor=#000000>")
(Other . "Text auf dem Body")
(Tag . "</body>")
(Tag . "</html>")


Beispiel 2 - Pascal ähnlicher Code:

TokenclassValuesScanmodeCaseSens
KeywordBEGIN END PROCEDURE FUNCTION VAR CONST RECORD WHILE FOR REPEAT UNTIL IF THEN ELSEexact oneNO
String' 'betweenNO
Relation= < > <= >= <>exact oneNO
Assignment:=exact oneNO
Brackets( )exact oneNO
Seperator;exact oneNO
IgnoreChars\r \n \tignoreNO
Other everythingNO

Diese Definition ist natürlich nicht vollständig da Pascal noch viel mehr Sprachelemente besitzt aber damit soll gezeigt werden wie nach Schlüsselwörtern gesucht werden kann.

Anmerkung: Mit SPG sind nicht alle denkbaren Scanner definierbar. Eine große Menge ist jedoch möglich. Denkbar wäre eine komplette Umstrukturierung auf Reguläre-Ausdrücke was aber zu Gunsten der einfacheren Handhabung verzichtet wurde.


 Beispiel Parser Definitionen21-12-2003 

Beispiel 1 - HTML Parser:
<define START
 <read Tag <call ParseTag 0> <goto START>>
 <read Other <goto START>>
 <read "" >
>
Dies ist ein möglicher Parser zum Scanner Beispiel 1. Eine Funktion START wird definiert die entweder einen Tag oder etwas anderes (Other) annimmt und wieder zu START zurückspringt. Sollte weder ein Tag noch ein Other gefunden werden wird die Epsilon Regel angewendet und die Funktion beendet sich, da bei read "" kein Sprung erfolgt. Other Tokens werden hier "überlesen" und bei jedem Tag wird die Funktion ParseTag mit dem aktuellen Tag aufgerufen. Wie diese Hilfsfunktion definiert werden könnte hängt dabei vollkommen von der Aufgabe des Endprogramms ab.


Beispiel 2 - HTML Parser 2:
<define START
 <goto READTAG <goto START>>
>

<define READTAG
 <read Tag <call ParseTag 0>>
 <read Other>
 <read "">
>
Dies ist ein weiterer Parser zum Scanner Beispiel 1. Hier wird die Rekursion deutlicher. Nur wenn READTAG erfolgreich war, wird wieder zu START zurückgesprungen.