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:

DrawObject

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 mu� 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)