Lexer für PL/0

Lexikalische Analyse(Scanner)

Aufgaben:

Lesen des Eingabetextes und Zerlegung in die einzelnen Zeichen im Sinne der Grammatik der Programmiersprache(Morpheme, Token, Atome oder Lexeme).

Morpheme können aufeiander folgen ( a+b*77 ) oder durch Trennzeichen voneinander getrennt sein ( call f1 )
Elliminierung von irrelevanten Textteilen (Kommentare, Leerzeichen...)
Konvertierungen
Erkennung von Wortsymbolen und Ersetzung durch besser handhabbare Symbolcodes
Die Aufgabenteilung von Lexer und Parser ist verschieblich. So kann die Erkennung zusammengesetzter Symbole durch den Scanner, aber auch von der Syntaxanalyse realisiert werden. Auch der Aufbau von Symboltabellen wird mitunter schon von der lexikalischen Analyse vorbereitet.

Einordnung in die Compilerpässe

Die lexikalische Analyse kann als selbstädiger Compilerpass, als paralleler Prozess oder als Unterprogramm der Syntaxanalyse oranisiert sein. Bei den einfachen Einpasscompilern, die im Rahmen der Vorlesung diskutiert werden sollen, soll die lexikalische Analyse ein Unterprogramm sein, das jeweils das nächste Morphem liefert.

Der Lexer selbst arbeitet in zwei Schritten.

Schritt 1:

Aus dem Eingabestrom werden die Zeichen gelesen und in einem Puffer alle zum Morphem gehörenden Zeichen gesammelt. Hierzu wird ein Automat verwendet.

Schritt 2:

Nachbereitung in Abhängigkeit des letzten Zustandes des Automaten.

Schlüsselworterkennung, falls Bezeichenr
Konvertierung, falls Zahl
Eintragen aller relevanten Informationen (Morphemcode, Morphemwert, Zeilen-/Spaltenposition) in eine Struktur Morphem.

Der endliche Automat als Grundlage der lexikalischen Analyse

Regeln der Grammatik der Morpheme von PL/0:

<Morphem>       ::= <Sonderzeichen>|<Zahl>|<Bezeichner>
<Sonderzeichen> ::= + | - | * | / | , | . | ; | ( | ) | ? | ! | # | = | < | <= | > | >= | :=
<Zahl>          ::= Zi {<Zi>}
<Zi>            ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 
<Bezeichner>    ::=Bu {BuZi}
<BuZi>          ::= Bu | Zi
<Bu>            ::= A | B | ... | Z | a | b | ... | z

Anhand eines Zustandgraphen kann der Automat zur Bildung der PL/0-Morpheme ganz gut und anschaulich beschrieben werden:

Zustandsgraph des Automaten zur Bildung der PL/0-Morpheme

Zur Analyse regulärer Sprachen eignet sich der endliche Automat. Er wird durch ein 7-tupel in folgender Weise beschrieben.

A=(X,Y,Z,f,g,F,z₀)

X: Eingabealphabet

Y: Resultatalphabet

Z: Menge der Zustände

f: Schalt-/Übergangsfunktion

g: Ausgabefunktion

F: Menge der Finalzustände

z₀: Anfangszustand

Eingabealphabet X:

Für einen PL/0 Scanner umfasst das Eingabealphabet die Buchstaben (A-Z, a-z), die Ziffern (0-9) sowie eine Reihe von Sonderzeichen ( + - * / ( ) . ; # ? ! < > : = ).

Menge der Finalzustï¿œnde F:

Ein Finalzustand ist dann erreicht, wenn ein Morphem vollständig erkannt wurde. Die zu erkennenden Morpheme umfassen

Sonderzeichen
Zahl
Bezeichner / Wortsymbol
<=
>=
:=

Die Übergangsfunktion f:

Sie legt fest, in welchen Zustand z_n+1der Automat ï¿œbergeht, wenn er sich in einem Zustand z_n befindet und ein bestimmtes Eingabezeichen anliegt.
Die Übergangsfunktion wird in einer Matrix, die von den Zeichen des Eingabealphabetes und den Zuständen des Automaten aufgespannt wird, dargestellt.

Die Ausgabefunktion g:

Sie legt fest, in welcher Weise das anliegende Eingabezeichen verarbeitet wird. Im realisierten PL/0-Compiler sind es die folgenden:

überlesen
schreiben in Puffer
schreiben in Puffer mit Umwandlung in Groß-/Kleinbuchstaben

Der Anfangszustand z₀

Der Anfangszustand ist der Zustand 0.

Soll nun eine Automatentabelle gebaut werden, so wird jedem Eingabezeichen eine Spalte, und jedem Zustand eine Zeile zugeordnet. Die Zustände sind aus dem Zustandsgraphen ersichtlich. In die Felder dieser Matrix wird der Folgezustand (Schaltfunktion) und die auszuführende Ausgabefunktion eingetragen. Diese Matrix lässt sich nun drastisch komprimieren, in dem die Eingabezeichen klassifiziert werden. Alle Buchstaben könnten zB. die Klasse Buchstabe, alle Ziffern die Klasse Ziffer und alle Sonderzeichen die Klasse Sonderzeichen bilden. Dies kann sehr effizient mit einem Zeichenklassenvektor realisiert werden.

Zeichenklassenvektor

Zeichenklassen

0: Sonderzeichen

1: Ziffer

2: Buchstabe

3: ':'

4: '='

5: '<'

6: '>'

7: Sonstige

Somit ergibt sich folgende Automatentabelle:

Jeder Eintrag besteht aus zwei Teilen:

Folgezustand
Aktionsindex einer Akltion, die ausgeführt wird, bevor der Automat in den Folgezustand übergeht

Die einzelnen Einträge wurden hier durch einen einfachen char-Wert, der die beiden Informationen in jeweils einer Tetrade codiert, gebildet. Selbstverständlich könnte auch jede Eintragung aus einer Struktur mit den Komponenten Folgezustand und Aktion bestehen.

Die Aktionen

Die Funktion "lesen" (fl)

Ihre Funktion besteht darin, das nächste Zeichen aus der Eingabedatei zu lesen und in der Variablen X (das anliegende Eingabezeichen) zu speichern. Weiterhin werden hier Zeilen- und Spaltenposition ermittelt.

Die Funktion "schreiben" (fs)

Das in der Variablen X abgelegte Zeichen wird in den Puffer vBuf übernommen (angehängt an den bereits bestehenden Inhalt)

Die Funktion "schreiben als Großbuchstabe" (fg)

Das in der Variablen X abgelegte Zeichen wird in einen Großbuchstaben umgewandelt und in den Puffer vBuf übernommen (angehängt an den bereits bestehenden Inhalt)

Die Funktion "beenden" (Wortsymbolerkennung) (fb)

Während die Lese- und Schreibfunktionen recht simpel ausfallen, ist die Funktion "beenden" doch etwas komplexer. Sie stellt in Abhängigkeit des Endzustandes des Automaten den Morphemcode ein und fï¿œhrt abschließende Konvertierungen durch. Hier wird die Struktur Morphem vollständig ausgefüllt. Diese Funktion setzt auch das Flag Ende, das zum Beenden der lexikalischen Analyse führt. Es ist auch sinnvoll, hier die Erkennung von Wortsymbolen einzubauen.
Im einfachsten Falle baut man einen Vektor der die Strings der Wortsymbole bereitstellt auf und und vergleicht das erkannte Moprphem mit jedem Element dieses Vektors.

char* vWSymb[]={“BEGIN“,“CALL“,“CONST“,"DO",“END“,“IF“,“ODD“,“PROCEDURE“,“THEN“,“VAR“,“WHILE“};

Diese Methode ist einfach zu implementieren, aber doch recht uneffektiv, vor allem, wenn die Anzahl der Wortsymbole größer wird. Wesentlich besser sind Techniken, die auf dem Prinzip der hash-code-Tabellen basieren. Bei diesen Techniken wird nach einem günstigen Kriterium ein Eintrag in einer Tabelle indiziert, hinter dem sich im bestenfalls nur noch ein einzelner Eintrag verbirgt, ansonsten muss von dort aus dann sequenziell durchsucht werden.

Eine sehr einfache Realisierung könnte eine Matrix sein, deren Zeilen durch den Anfangsbuchstaben und deren Spalten durch die Länge des einzutragenden Wortsymbols indiziert werden. Für den Scanner von PL/0 ergibt sich dabei eine relativ dünn besiedelte Matrix, deren Einträge aus einer Struktur, die einen Zeiger auf das zu untersuchende Wortsymbol und den im Falle der Übereinstiommung zu erzeugenden Wortsymbolcode enthält. Diese Matrix wird mit dem Anfangsbuchstaben und der Morphemlänge -2 indiziert. Ist das indizierte Feld mit 0L belegt, kann es sich nur um einen Bezeichner handeln, andernfalls muï¿œ ein Stringvergleich ausgeführt werden. Für ein Wortsymbol wird ein Zeichencode wie für ein gewöhnliches Sonderzeichen aus dieser Tabelle ermittelt. Die Codes für solche Symbole sind in lex.h deklariert.

Die Funktionen fsl, fgl, fslb

Diese Funktionen setzen sich aus den vorgenannten Funktionen zusammen.
fsl: schreiben + lesen
fgl: schreiben als Großbuchstabe + lesen
fslb:schreiben + lesen + beenden

Quelltextausschnitte:

Lex.h

Dieser Quelltext lexframe.c soll einen Rahmen für den im Praktikum zu bauenden Lexer sein und den Einstieg erleichtern.

Lex.c (unvollständig)