Ein einfacher, graphengesteuerter PL/0 Einpasscompiler geschrieben in C für Linux und Windows. Dieser Compiler erzeugt ausschließlich ausführbaren Zwischencode, welcher mit einer virtuellen Maschine ausgeführt werden muss. Dieses Programm ist die Belegarbeit des Moduls Compiler/Interpreter im Wintersemester 2024/2025.
Um meinen Compiler mit gcc zu kompilieren, folgenden Befehl im Terminal ausführen:
gcc -DVARSIZE=4 Compiler.c Lexer.c Parser.c Liste.c CodeGen.c Semroutinen.c -o Compiler32
- Die Variablengröße kann mit
-DVARSIZEangepasst werden (2, 4 oder 8 Byte). Ohne explizite Angabe ist die Größe standardmäßig 2 Byte. - Debugausgaben können zusätzlich mit
-DDEBUGeingeschaltet werden.
Hinweis für Windows: Für eine erhebliche Leistungsverbesserung von
printfsollte mit der Option-D__USE_MINGW_ANSI_STDIO=0kompiliert werden. Diese Option kann für alle weiteren Kompilierungen verwendet werden.
Aufgerufen wird der Compiler wie folgt (.pl0 kann weggelassen werden):
./Compiler32 Programm.pl0
Zur Ausführung des kompilierten Programms ist die virtuelle Maschine r24 von A. Beck erforderlich. Die Zahlen "16", "32" und "64" dahinter geben die Variablengröße an. Das heißt ein Programm, welches z.B. mit 32-bit (4 Byte) Variablen kompiliert wurde, muss mit r2432 ausgeführt werden. Diese lassen sich wie folgt kompilieren:
gcc r2416.c -o r2416
gcc r2432.c -o r2432
gcc r2464.c -o r2464
- Debugausgaben, welche in die Datei
DEBUG.dbggeschrieben werden, können zusätzlich mit-DDEBUGeingeschaltet werden.
Der Aufruf ist wie folgt (.cl0 kann weggelassen werden):
./r2432 Programm.cl0
Um die vom Compiler generierten kompilierten Programme lesbar sich anzuschauen gibt es das Tool outCl0, das ebenfalls von A. Beck geschrieben wurde. Es wird automatisch erkannt, um welche Variablengröße es sich handelt. Kompiliert wird wie folgt:
gcc outCl0.c -o outCl0
Und der Aufruf (.cl0 kann weggelassen werden):
./outCl0 Programm.cl0
Der Compiler hat die komplette Grundsprache von PL/0 implementiert, aber es gibt ein Paar zusätzliche Erweiterungen.
Kommentare können in den Quelldateien hinzugefügt werden und sind mit ** [Kommentar] ** gekennzeichnet. Diese können auch über mehrere Zeilen gehen.
Um den Anfang zu finden wird im Lexer, in der Fkt. SchreibenLesenBeenden (hier wird bei Sonderzeichen hingegangen), das aktuelle Zeichen X und das darauffolgende Zeichen überprüft, ob es jew. ein * ist. Wenn ja, wird der Zustand 9 gesetzt, wo alle Zeichenklassen immer die Fkt. Lesen aufrufen. Dies ergibt eine Endlosschleife, wo über alles mögliche darüberlesen wird.
Falls nicht, wird alles wieder zurückgesetzt, so wie vor der Überprüfung, sodass der Lexer weiterarbeiten kann als wäre nichts passiert.
In der Fkt. Lesen wird nun permanent versucht, das Kommentarende zu entdecken. Dafür wird das aktuelle Zeichen und das vorherige Zeichen überprüft, ob es jew. ein * ist. Falls ja, wird der nächste Zustand so wie immer gesetzt und der Lexer fährt normal fort. Wenn die vorherige Bedingung nie eintrifft und das Ende der Datei erreicht wurde, ist klar, dass die schließenden ** vergessen wurden.
Variablen und Konstanten können im Code im hexadezimalen Format zugewiesen werden, indem sie mit 0x[Zahl] beginnen. Buchstaben können GROß-und kleingeschrieben werden.
Für die Erkennung wird im Lexer zuerst versucht die 0x zu erkennen, womit klar ist das es keine normale Zahl ist. Dann wird in Zustand 10 gewechselt, wo nur Zahlen oder Buchstaben erkannt werden können. Bei den Buchstaben wird zusätzlich überprüft, ob diese zwischen A-F liegen. Beim Entdecken eines anderen Zeichen außer Buchst. und Zahl wird beendet, die hex-Zahl in eine normale Zahl konvertiert und ins Morphem gespeichert.
Der Lexer ist automatenbasiert und nutzt Zeichenklassen, damit die Automatentabelle nicht zu groß wird. Die Schlüsselworterkennung basiert auf einer Hashfunktion.
Folgende Funktionen kann der Automat aufrufen:
- Lesen
- Schreiben, lesen
- Schreiben als Großbuchstabe, lesen
- Schreiben, lesen, beenden
- Beenden
In den Lese - und Schreibfunktionen wird das aktuelle Zeichen gelesen und in einen Buffer gespeichert. Zusätzlich wird Zeile und Spalte des Morphems ermittelt. In der Beenden-Funktion werden dann auch die Morpheme erzeugt, wobei Typ und Wert mit in die Morphem-Struktur geschrieben werden.
Der Parser ist auf Kellerautomaten basiert und ist intern als mehrere Arrays von Bögen (= ein Graph) implementiert. Ein Bogen hat intern den folgenden Aufbau (oben ist das Element und darunter eine Erklärung / mögl. Elemente):
| Bogentyp | Bogenbeschreibung | Funktion | Folgebogen | Alternativbogen |
|---|---|---|---|---|
| Morphem, Symbol, Graph, Ende, NIL | ASCII-Symbol, Morphemsymbol, Pointer auf Graph | optional eine Semantikroutinenfkt. | wenn Erfolg, diesen Bogen als nächstes nehmen | wenn kein Erfolg, diesen Bogen als nächstes nehmen |
Erfolg gibt es zum Beispiel, wenn das Symbol mcIdent erwartet wird und das aktuelle Morphem dieses Symbol auch beinhaltet. Wenn dies nicht der Fall ist, werden die Alternativbögen genommen, bis es Erfolg gibt. Sollte es selbst dann noch kein Erfolg geben, ist klar das ein Syntaxfehler vorliegt.
Manche Bögen können auch eine Funktion aufrufen, welche für die Erstellung der Namensliste und Codegenerierung verantwortlich sind.
Nachfolgend sind die Graphen grafisch dargestellt mit densselben Bogennummern (in rot) und Funktionsnamen (in grün), welche im Programm verwendet werden.
Hier sind mitunter die Funktionen für die Erstellung der Namensliste für jede einzelne Prozedur. Dabei werden gleichzeitig die Gültigkeitsbereiche mit implementiert. Jedes Listenelement enthält:
- Kennzeichen (Bezeichner falls keine Objektbeschr., Variable, Konstante, Prozedur)
- Prozedurenindex
- Pointer auf Objektbeschreibung (Variable, Konstante, Prozedur)
- Name
Jede Prozedur besitzt eine eigene lokale Namensliste und ist verkettet mit übergeordneten Eltern-Prozeduren. Die Hauptprozedur hat die Nr. 0, keine Elternprozedur und wird immer erstellt. Prozeduren sind wie folgt aufgebaut:
- Kennzeichen
- Prozedurnummer
- Pointer auf Prozedurbeschr. der Elternprozedur
- Pointer auf lokale Namensliste der Prozedur
- Speicherzuordnungszähler für Variablen
Bei Konstanten wird zusätzlich jew. der Wert in einem Konstantenblock gespeichert, welcher ein Array ist und bei Bedarf mit realloc() vergrößert wird.
Variablen werden auch in der Liste gespeichert, aber nicht mit dem Wert sondern mit der Relativadresse im Speicher. Die Länge von Konstanten und Variablen ist entweder 16, 32 oder 64-Bit.
Wenn eine Funktion bei einem Bogen aufgerufen wird, wird z.B. überprüft, ob der Bezeichner schon vorhanden ist, indem die Liste lokal durchsucht wird. Wenn der Bezeichner beispielsweise gefunden wird, heißt das dieser doppelt angelegt wurde, was einen Fehler ergibt. Sonst wird ein neuer Bezeichner angelegt.
Neben Funktionen zum Erstellen der Namensliste, sind die meisten Funktionen für die Codegenerierung verantwortlich. Jeder Befehl besteht aus 1 Byte OpCode und hat 0-3 Parameter, welche jeweils 2 Byte groß sind. Diese werden immer in little Endian gespeichert. Hier ein Überblick über alle möglichen Zwischencodebefehle:
| Befehl | Opcode | Parameter | Beschreibung |
|---|---|---|---|
| Kellerbefehle | |||
| puValVrLocl | 00 | int Displ | Kellern Wert lokale Variable |
| puValVrMain | 01 | int Displ | Kellern Wert Main Variable |
| puValVrGlob | 02 | int Proc, int Displ | Kellern Wert globale Variable |
| puAdrVrLocl | 03 | int Displ | Kellern Adresse lokale Variable |
| puAdrVrMain | 04 | int Displ, int Proc | Kellern Adresse Main Variable |
| puAdrVrGlob | 05 | int Displ | Kellern Adresse globale Variable |
| puConst | 06 | int Index | Kellern einer Konstanten |
| storeVal | 07 | - | Speichern Wert -> Adresse, beides aus Keller |
| putVal | 08 | - | Ausgabe eines Wertes aus Keller nach stdout |
| getVal | 09 | - | Eingabe eines Wertes von stdin -> Keller |
| Arithmetische Befehle | |||
| vzMinus | 0A | - | Vorzeichen - |
| odd | 0B | - | Ungerade -> 0/1 |
| Binäre Operatoren | |||
| OpAdd | 0C | - | Addition |
| OpSub | 0D | - | Subtraktion |
| OpMult | 0E | - | Multiplikation |
| OpDiv | 0F | - | Division |
| cmpEQ | 10 | - | Vergleich = -> 0/1 |
| cmpNE | 11 | - | Vergleich # -> 0/1 |
| cmpLT | 12 | - | Vergleich < -> 0/1 |
| cmpGT | 13 | - | Vergleich > -> 0/1 |
| cmpLE | 14 | - | Vergleich <= -> 0/1 |
| cmpGE | 15 | - | Vergleich >= -> 0/1 |
| Sprungbefehle | |||
| call | 16 | int ProzNr | Prozeduraufruf |
| retProc | 17 | - | Rücksprung |
| jmp | 18 | int RelAdr | SPZZ innerhalb der Funktion |
| jnot | 19 | int RelAdr | SPZZ innerhalb der Funktion, Bedingung aus Keller |
| entryProc | 1A | int lenVar, int ProcIdx, int SpzzVar | Prozedureneinstieg |
Die Funktionen überprüfen, ob es die Bezeichner gibt und ob sie den richtigen Typ haben für den jew. Befehl, indem sie die Namensliste global durchsuchen. Es gibt dabei drei verschiedene Möglichkeiten zur Generierung von Variablen:
- local: Variable ist in der akt. Prozedur
- main: Variable ist in der Hauptprozedur (Nr. 0)
- global: Variable befindet sich in umgebenden Prozeduren
If und While verwenden Jump-Befehle mit Relativadressen.
Bei If wird der Befehl jnot nach der Bedingung generiert und vorerst die Relativadresse auf 0 gesetzt. Dieser Befehl zeigt wohin gesprungen werden muss, falls die Bedingung nicht wahr ist (es überspringt den if-Block). Sonst wird einfach der nächste Befehl nach der Bedingung ausgeführt.
Da anfangs nicht nicht klar ist, wann der If-Block endet, wird ein Label generiert mit der akt. Position im Codeausgabepuffer. Wenn am Ende angekommen, kann die relative Sprungdistanz berechnet werden für jnot (es werden 3 Byte abgezogen, damit jnot nicht mitgezählt wird):
Hier nochmal die Sache veranschaulicht (eine Zelle = 1 Byte):
| jnot | Param. | Param. | if-Bl. Anw. 1 | if-Bl. Anw. 2 | if-Bl. Anw. 3 | if-Bl. Anw. n | Folgende Anw. 1 |
|---|---|---|---|---|---|---|---|
| Label gener. | Relativadr. ber. -> nachtragen in jnot |
Hier sind die Hilfsfunktionen der Liste wie das Anfügen eines neuen Elements, das Löschen des letzten Elements/der ganzen Liste, die Suche und die Ausgabe zum Debuggen. Zusätzlich gibt es Funktionen zum Erstellen der Objektbeschreibungen und der Verknüpfung zwischen diesen und den Listenelementen. Außerdem gibt es Funktionen für den Konstantenblock und einen Stackliste für Label, welche für das Zwischenspeichern der akt. Position für jmp-Befehle benötigt werden.
Hier sind die Hilfsfunktionen der Codegenerirung wozu grundlegende Dinge, wie das Öffnen und Schließen der Datei zählt. Beim Öffnen der Datei wird der Dateiheader erstellt, wo Variablengröße und Prozedurenanzahl drinstehen. Beim Schließen der Datei wird der Konstantenblock am Ende angehangen und zusätzlich der Dateiheader vervollständigt. Zudem gibt es Funktionen, welche Code in den Codeausgabepuffer schreiben. Diese werden mit weiteren Funktionen im little Endian Format reingeschrieben.
Basierend auf http://www.informatik.htw-dresden.de/~beck/Compiler/