Compiler selbstgeschneidert

Teil 1: Die Sprache DOIT und die Symboltabelle des Compilers

Helmut Richter

Diese neue Compiler-Serie ist genau das richtige Projekt für diejenigen, die die Eigenwilligkeiten ihres Compilers nicht länger hinnehmen, sondern lieber eigene Vorstellungen in die Tat umsetzen wollen. Mit dem Wissen der Serie 'Software-Baustelle' gerüstet, stellen wir uns diesmal der harten Praxis. Das Ziel ist ein praktisch einsetztbarer 'DOIT-yourself-Compiler' für die pascalähnliche Sprache DOIT, der Maschinencode für die Z80-CPU produziert. Die Serie wird nicht nur zeigen, wie der Compiler arbeitet, sondern auch, wie er sich an eigene Vorstellungen anpassen läßt.

Die Sprache, die der Selbstbau-Compiler übersetzt, trägt den verheißungsvollen Namen DOIT. Diese erste Folge wird natürlich zunächst einmal die Struktur und das Konzept dieser Sprache vorstellen. Außerdem beschäftigt sie sich ausführlich mit dem ersten Stückchen Compiler, ohne daß kein praktisch einsetzbarer Compiler auskommt: mit der Symboltabelle. Vorher wird bereits ein Überblick über sie Aufgaben des Scanners und des Parsers gegeben. Die weiteren Folgen beschäftigen sich dann ausführlich mit Scanner und Parser sowie mit dem Code-Generator und möglichen Erweiterungen.

Diese Serie ist zwar in sich geschlossen, wir aber auf die Serie 'Software-Baustelle' (c't 9/85 bis 12/85) aufbauen und auf bereits dort erklärte Zusammenhänge nicht erneut eingehen. Fortgeschrittene Compiler-Bauer finden in N. Wirths 'Compilerbau' (Teubner) ebenfalls das notwendige Basiswissen und die Beschreibung eines ähnlichen Projekts, allerdings in sehr viel komprimierter Form. Da der Compiler in Turbo-Pascal geschrieben ist, sollte man ein gewisses Maß an Pasca beherrschen. Im wesentlichen besteht der DOIT-Compiler jedoch nur aus Standard-Elementen, so daß er sich auch leicht in andere Pascal-Dialekte übersetzen läßt. Treten kompliziertere Datenstrukturen als Arrays oder REcords auf (schwieriger als vekettete Listen und einfache Heaps wird's nicht), so werden diese ausführlich vorgestellt.

Es ist durchaus kein 'Sich-im-Kreise-drehen', wenn zur Erstellung eines neuen Compilers bereits ein Pascal-Compiler benutzt wird. Es wird nur scheinbar vorausgesetzt. Die Sprache Pascal hat hier hauptsächlich die Aufgabe, als Transportmedium und Formulierungssprache für Algorithmen zu dienen, wozu sie sich aufgrund ihrer leichten Lesbarkeit und klaren Struktur besonders gut eignet. Jeder geübte Programmierer hat so die besten Voraussetzungen, den DOIT-Compiler in eine anderre Sprache zu übertragen — zum Beispiel in Assembler für seine bevorzugte CPU. Für die mit dieser Serie beabsichtigte Vermittlung von Prinzipien hätte Assembler weder den Vorzug der leichten Lesbarkeit, noch den Vorteil der Prozessor-Unabhängigkeit. Turbo-Pascal hingegen bietet bietet als komfortabler und verbreiteter Compiler zusätzlich noch die Möglichkeit, schnell und bequem beliebige Eingriffe und Modifikationen des DOIT-Compilers vornehmen zu können und diese sofort in der Praxis überprüfen zu können. Doch zunächst folgen einige klärende Worte zur Struktur und zu den Möglichkeiten der Sprache DOIT selbst.

Die Sprache DOIT

DOIT ist eine universelle Programmiersprache mit pascal-ähnlicher Syntax und modularem Aufbau. In der Grundstufe kennt DOIT die Datentypen Integer und Character als Variable und Konstante, Hexadezimalzahlen nur als (Character-)Konstante. Kommentare sind im Programmtext überall dort erlaubt, wo man ein Leerzeichen einfügen darf. Wie sich Pointer, Real-Zahlen, Arrays, Strings und Records implementieren lassen, wird später beschrieben. Zusätzlich wird diese Serie zeigen, dass wie sich leicht ein sicheres Konzept für den Zugriff auf globale Daten anderer Module einführen läßt.

Wie in Pascal endet jede Anweisung mit ';'. Eine Besonderheit von DOIT ist, dass es nur eine, dafür aber mächtige Schleifenkonstruktion gibt, die mit DO und OD gebildet wird:


DO
     ‹Schleifenkörper›
OD

Alle Anweisungen zwischen DO und OD werden so lnage widerholt, bis mit der Anweisung EXIT die Schleife verlassen wird. Damit keine Endlosschleife entsteht, muß also innerhalb des Schleifenkörpers einmal EXIT erreicht werden. Mehrere EXIT-Anweisungen innerhalb einer Schleife sind erlaubt. EXIT bewirkt den Sprung direkt hinter die Schleife und nicht irgendwo in die Prärie, ist also nicht mit gewissen BASIC-Praktiken zu verwechseln. Zusammen mit der 'IF ‹condition› THEN ‹statement› ELSE ‹statement› FI'-Konstruktion lassen sich insgesamt vier typische Wiederholungs-Konstruktionen nachbilden:

1. Die For-to-do-Schleife:	2. Die While-do-Schleife:	3. Die Repeat-until-Schleife:	4. Die 'Goto-Schleife':
I=1; max=100; DO IF I›max THEN EXIT; FI; ‹statement› I=I+1; OD;	DO IF ‹condition› THEN EXIT; FI; ‹statement› OD;	DO ‹statement› IF ‹condition› THEN EXIT; FI; OD;	DO ‹statement› IF ‹condition› THEN EXIT; FI; ‹statement› OD;

1. Die For-to-do-Schleife:

2. Die While-do-Schleife:

3. Die Repeat-until-Schleife:

4. Die 'Goto-Schleife':

I=1;
max=100;
DO
  IF I›max THEN EXIT;
  FI;
  ‹statement›
  I=I+1;
OD;

DO
  IF ‹condition› THEN EXIT;
  FI;
  ‹statement›
OD;

DO
  ‹statement›
  IF ‹condition› THEN EXIT;
  FI;
OD;

DO
  ‹statement›
  IF ‹condition› THEN EXIT;
  FI;
  ‹statement›
OD;

Nach diesem kleinen Vorgeschmack wird es Zeit, den Aufbau eines vollständigen DOIT-Programms zu beschreiben:

Jedes DOIT-Programm beginnt mit dem Wort MODULE, gefolgt von Programmnamen und der Deklaration von Konstanten, Variablen und Prozeduren. Der Anweisungsteil selbst beginnt mit BEGIN und endet mit END:

MODULE DoitTest;

CONST....;
VAR......;

PROC TestProc;
(* lokale Deklaration *)
BEGIN
  ‹statement›
END (* testproc *);

BEGIN (* Hauptprogramm *)
  ‹statement›
END.

Im Gegensatz zu BASIC sind hier globale und lokale Variable möglich, außerdem ist Rekursion zugelassen. Prozeduren dürfen jedoch nicht verschachtelt werden. Bild 1 zeigt die vollständige Definition der DOIT-Syntax in EBNF.

    module::=MODULE ident; block;
     block::=CONST ident = (number|letter) {,(number|letter)}*;|
             VAR ident:(INT|CHAR) {,(INT|CHAR)}*;|
             PRUC ident; block;|
             BEGIN statement END (.|;)
 statement::=ident=expression;|ident;|
             READ ident;|WRITE ident;|LINE;|
             IF condition THEN statement + (ELSE statement) FI;
             DO statement OD;|
             EXIT;
 condition::=expression op expression
        op::=<|>|=|>=|<=|<>
expression::=(+|-)term {(+|-)term}*
      term::=factor {(*|/)factor}*
    factor::=ident|number|(expression)
     ident::=letter {letter|digit}*
    number::=digit {digit}*
     digit::=0|1|2|...|9
    letter::=A|B|C|...|Z

Bild 1: DOIT besitzt eine pascalähnliche Syntax.

Als weitere Veranschaulichung und als kleine Hilfe zum Lesen der EBNF ist in Bild 2 nochmal die Syntax von ‹statement› als Syntaxdiagramm dargestellt. Nicht-terminale Symbole sind in beiden Abbbildungen wieder kursiv geschrieben.

Bild 2: Anschaulicher als in EBNF: das Syntaxdiagramm von 'statement'

Bild 3 gibt zwei Beispiele für DOIT-Programme, von denen das zweite den Gebrauch von Prozeduren mit lokalen Variablen und Rekursion demonstriert.

MODULE Demo1;

CONST  pi = 3;
VAR     i : INT;

BEGIN
  WRITE '?';
  (* ? ist eine Charakterkonstante *)
  READ i;
  i := i * pi;
  WRITE i;
END.

MODULE Procdemo;
(* globale Variablen *)
CONST     maxint = 32000;
CONST         pi = 3;
VAR         i, f : INT;
VAR           ch : CHARM

PROC Fakultaet;

BEGIN
  IF i > 1 THEN
     f := i * f;
     i := i - 1:
     Fakultaet;
  FI;
END; (* Fakultaet *)

PROC Hoch100;
(* lokale Variablen *)
VAR   index, k : INT;

BEGIN
  k := i;
  index := 2;
  DO
    IF index > 100 THEN EXIT; FI;
    IF i > maxint / i THEN EXIT;
    i := i * k;
    WRITE index; WRITE ':'; WRITE i;
    index := index + 1;
  OD;
END; (* Hoch100 *)

BEGIN (* Hauptprogramm *)
  f := 1;
  WRITE '?'; READ i; Fakultaet; WRITE f;
  WRITE '?'; READ i; Hoch100;
END.

Bild 3: In der Sprache DOIT sind auch rekursive Aufrufe möglich

An dieser Stelle fragt man sich vielleicht doch noch einmal, welche Möglichkeiten es gibt, wenn man seinen Compiler selber schreibt?

Einfache Abwandlungen wären zum Beispiel das Eindeutschen der reservierten Wörter: ANFANG statt DO, SCHLUSS statt OD, RAUS statt EXIT uns so weiter. Solche Änderungen müssen nur in der Schlüsselworttavelle gemacht werden und sind unkritisch und nebenwirkungsfrei, solange nichts doppelt verwendet wird und die gewählten Beteichner nicht mehr als sieben Zeichen haben (was man übrigens auch noch ändern kann).

Dann können Sie Sprachkonstrukte verwerfen oder hinzufügen, etwa das GOTO oder das EXITMOD als Befehl zur sofortigen Programmbeendigung oder ein CLEARSCREEN für Igren Rechner. Es läßt sich auch die Syntax ändern, indem man zum Beispiel den Programmkopf wegläßt. Und — last but not least — der Compiler kann erweitert werden (dazu später mehr). In einem Satz: Sie können sich Ihre Sprache maßschneidern.

DOIT-Compiler

Nach der Vorstellung der Sprache DOIT folgt nun eine Charakterisierung des DOIT-Compilers. Er ist ein Einphasen-Compiler, das heißt, der gesamze DOIT-Quelltext witd während eines Durchgangs in Z80-Maschinencode übersetzt. Er liest den Quelltext bon der Datei ‹name›.SRC und schreibt den erzeugten Code auf die Datei ‹name›.COM.

Der Parser übernimmt die syntaktische Analyse und dient damit als 'Hauptprogramm; die Übersetzung erfolgt also syntaxgesteuert. Er ruft bei Bedarf den Scanner auf, der die lexikalische Analyse vornimmt und das nächste Token liefert. Anschließend analysiert der Parser den entstandenen Ausdruck und veranlaßt nach der semantischen Prüfung die Generierung des Maschinencodes. Bild 4 veranschaulicht die Struktur des Compilers.

Bild 4: Über die Symboltabelle tauschen Parser, Scanner und Code-Generator wichtige Informationen aus.

Nebenher werden erkannte Fehler auf dem Bildschirm aufgelistet. Es liegt dabei in der Hande des Benutzers, ob der Compiler nach dem ersten, zweiten oder n-tesn Fehler abbricht oder den gesamten Quelltext durcharbeitet. Auch läßt sich eine Listfile-Generierung installieren, die auf der Datei ‹name›.LST ein Compiler-Listing erzeugt. Eine Codeoptimierung ist nicht vorgesehen, läßt sich aber anhängen.

Die syntaxgesteuerte Einphasenanalyse wird von der Sprache selbst unterstützt. Sie ist ein Vertreter der Sprachklasse LL(1) und damit auf eine bestimmte, hier vorteilhafte Weise eingeschränkt. Sie läßt sich per 'rekursivem Abstieg' vollständig analysieren, das heißt, der Ableitungsweg im Syntaxbaum ist eindeutig vorherbestimmt, es ist kein Backtracing nötig.

Scanner und Parser

Im einzelnen hat der Scanner die folgenden Aufgaben zu erfüllen:

Zerlegen des Quelltextes in einen Tokenstrom,
Identifizieren von Schlüsselwörtern,
falls implementiert und gewünscht, ein Sourcelisting zu erzeugen,
Kommentare zu überlesen,
Ziffern zu erkennen und in Zahlen umzuwandeln,
Spezialzeichen (etwa Operatoren oder Compilerdirektiven) zu erkennen und in Token umzuwandeln.

Je mehr dieser Aufgaben bereits vom Scanner erledigt werden, um so einfacher und klarer läßt sich der Parser konstruieren.

Die Einphasenübersetzung stellt höhere Anforderungen an den Parser als bei der Kompilation in mehreren Passes. Neben seiner Hauptaufgabe der syntaktischen Analyse muß er den gesamten Programmablauf steuern (syntaxorientierte Übersetzung), wobei er Scanner und Codegenerator als Unterprogramm benutzt. Das folgende Beispiel zeigt den Ablauf einer Syntax-Überprüfung:
Trifft der Scanner auf die Zuweisung x := 6, liefert er den Tokenstrom ‹identifier, op, integerconst› zurück, und der Parser muß eine passende Ableitung finden. Der einzige Ableitungsweg (Top-Down-Analyse) führt über ‹statement›:

statement ::= ident:=expression

gefolgt von

expression :: =term
term ::= number
number ::= digit {digit}*
ident ::= letter {letter | digit}*

wobei ‹letter› und ‹digit› Terminalsymbole sind und einen gültigen Endzustande der Analyse darstellen. Damit ist x := 6 als ein syntaktisch richtiges Element der Sprache DOIT erkannt.

Ist eine Listfile-Generierung vorgesehen, so muß diese vom Parser ausgeführt werden, das heißt, er muß den Source-Text mit Zeilennummern versehen und auf eine Datei schreiben ( name.PRN oder name.LST ).

Wichtiger als die Listfile-Generierung ist die Fehlerbehandlung, die ebenfalls vom Parser vorgenommen werden muß. Folgendes Beispiel zeigt, daß auch hier Entwurfsentscheidungen zu treffen sind:

MODULE Test;
VAR x : INT;
BEGIN
 x := 6;
 x := 6 * y;
 x := 6y;
END.

und sein Listfile:

1 MODULE Test;
2 VAR x : INT;
3 BEGIN
4  x := 6;
5  x := 6 * y;
  error    ↑
Identifier not declared
6  x := 6y;
  error ↑
';' expected
7 END.

Der Fehler in Zeile 5 ist plausibel. Mit nicht deklarierten Variablen kann man auch in DOIT nicht rechnen (kontext-sensitiver Zusamenhang).

Die Fehlermeldung in Zeile 6 entspricht jener von Turbo-Pascal und ist vielleicht etwas überraschend. Bei der Verarbeitung der Zeichenfolge '6y' muß der Scanner den falschen Character innerhalb der Integer-Konstanten erkannt haben. Aber statt 'error in constant' oder ähnliches zu melden, hat er die Konstante als beendet angesehen. Un diesem Fall muss natürlich ein Simikolon folgen.

Symboltabelle

Während der Analyse eines Programms muß ein Compiler Informationen über die im Quelltext vorkommenden Namen (oder Bezeichner oder identifier) dammeln und widerverwenden. Diese Informationen werden in der Symboltabelle aufbewahrt und verwaltet. Jeder Tabelleneintrag besteht dabei aus zwei Komponenten, nämlich aus dem Namen selbst und aus Informationen über das Objekt, welches diesen Namen trägt.

In Bild 5 sind zwei prinzipielle Methosen zur Abspeicherung der Namen dargestellt. Die erste ist die direkte Abspeicherung in einem Record zusammen mit den Informationen, die zweite Möglichkeit ist die getrennte Abspeicherung der Namen in einer linearen Liste. Der Vorteil der ersten Methode ist die direkte Verfügbarkeit der Namen, der Nachteil eine unter Umständen beträchtliche Speicherplatzverschwendung, da für jeden Tabelleneintrag ein Namensfeld reserviert werden muß, das auch noch den längsten Namen faßt.

Bild 5: Symboltabellen: mal so — mal anders.

Das zweite Verfahren speichert die Namen in einer Liste mit variabler Feldlänge und ist so ökonomischer im Verbrauch von Speicherplatz. Kurze Namen benötigen auch nur entsprechend wenig Platz. Der Nachteil ist das längere Suchen, da der zu den Informationseinträgen gehörende Name erst über den Zeiger auf die Namensliste erreicht werden kann (siehe Bild 5). Der DOIT-Compiler verwendet erstere Darstellung mit einem zehnstelligen Namensfeld (n=10). Signifikant sind also die ersten zehn Zeichen von DOIT-Namen. Wer möchte, kann dies ändern.

Die über den Namen zu speichernde Informationen umfassen den Typ, der bei DOIT Proc, Integer oder Char sein kann. Bei letzteren beiden ist noch die Speicheradresse innerhalb des Objektprogramms wichtig. Nimmt man noch die Typen Array und REcord dazu, braucht der Compiler weitere Informationen, nämlich deren Größe, die er in der Deklaration mitgeteilt bekommt.

In Bild 6 ist die Datenstruktur eines Objektes dargestellt, wie es in der DOIT-Symboltabelle eingetragen wird, nebst der in Objekt verwendeten Datentypen. Soll DOIT weitere Datentypen erhalten, wie zum Beispiel Real-Zahl und Pointer, muß die Typdefinition von Objekt-Klasse entsprechend erweitert werden. Die Unterscheidung zwischen den DOIT-Datentypen Character und Integer ist notwendig, da Integers zwei, Characters ein Byte lang sind.

Objekt = RECORD
           Name : Str10;
           next : ObjPtr;
           CASE Kind : ObjektKlasse of
              CharCon : (CWert : CHAR);
              IntCon  : (IWert : INTEGER);
              Proc    : (Startadresse : INTEGER);
              CharVar,
               IntVar : (Datenadresse : INTEGER);
              Header  : (Last, Down : ObjPtr);
         END;

mit den Datentypen

  Str10        = STRING[Identifierlaenge];
  ObjPtr       = ^Objekt;
  ObjektKlasse = (CharCon, IntCon, Proc,
                    CharVar, IntVar, Header);

Bild 6: Ein Variablen-Record legt die Struktur für die Elemente der Symboltabelle fest.

Wie der Parser im einzelnen Variablen in die Symboltabelle einträgt, wird nun an dem Programmbeispiel in Bild 7 gezeigt.

  MODULE  Test;

  CONST pi = 3;
  VAR   ch : CHAR;
  VAR    i : INT;

    PROC Demo;

    VAR  b : CHAR;
    VAR  i : INT;

    BEGIN

      (* Prozedur-
           rumpf *)
    END;

  BEGIN (* Test *)

    (* Hauptpro-
      grammrumpf *)
    END.

Bild 7: Für den Aufbau der Symboltabelle: ein Beispielprogramm.

Bild 8 stellt dabei den jeweiligen Zustand der Symboltabelle zu bestimmten Zeitpunkten der Übersetzung dar. Sie ist nämlich gar keine Tabelle, sondern eine lineare beziehungsweise zeitweise verzweigte Liste:

Bild 8: Dynamisch — so wechselt die Symboltabelle ihre Gestalt, wenn der Scanner das Beispielprogramm durchläuft..

Die erste Skizze in Bild 8 zeigt die Symboltabelle nach der Initialisierung, wo sie nur aus den Zeigern Bottom, Topscope und dem Tabellen-Header mit weiteren Zeigern besteht.

Nach der Abarbeitung der globalen Variablen ist der in der Skizze gezeigte Zustand erreicht. Die Objekte pi, ch und i sind erzeugt und über den Zeiger 'next' miteinander verkettet. Sie enthalten neben dem Namen den Typ des Objekts und dessen Wert beziehungsweise dessen Speicheradresse. Der Zeiger 'last' des Headers zeigt auf das letzte Objekt.

Die dritte Symboltabelle entsteht nach der Abarbeitung der lokalen Variablen der Prozedur Demo. Zunächst einmal wird auch der Prozedurname auch in die Tabelle eingetragen, wobei das Adreßfeld die Startadresse von 'Demo' enthält. Um nun die folgenden Variablen als lokal zu kennzeichnen, werden sie in einer gesonderten Symboltabelle eingetragen. TopScope zeigt dabei auf den Header dieser neuen lokalen Symboltabelle, während Bottom auf den Header der alten globalen Tabelle gerichtet ist. Beide Tabellen sind über den 'Down'-Zeiger des neuen Headers verknüpft. Die gesamte Symboltabelle bildet einen Heap, also eine Art Stack, der nach oben wächst. Er kann aber nur zwei Etagen hoch wachsen, da verschachtelte Prozeduren verboten sind. 'Down' eignet sich zur Überprüfung der aktuellen Programmebene. Ist 'Down'=nil, befindet man sich in der Symboltabelle der Hauptprogrammebene.

Am Ende des Prozedurblocks wird die Symboltabelle mit den lokalen Variablen verworfen, da sie für die weitere Übersetzung nicht mehr benötigt wird. Dieser Zustand ist in der letzten Skizze dargestellt.

Zur Verwaltung der Symboltabelle müssen folgende Operationen durchgeführt werden können:

feststellen, ob ein Name in der Tabelle enthalten ist,
einen neuen Namen hinzufügen,
die Informationen eines eingetragenen Namens zur Verfügung stellen,
neue Informationen zu einem eingetragenen Namen hinzufügen,
einen Namen oder eine ganze Gruppe von Namen aus der Tabelle entfernen.

Dies leisten die folgenden Prozeduren und Funktionen:

Find(name:Str10):ObjPtr;
prüft, ob 'name' in der Symboltabelle und liefert gegebenenfalls einen Zeiger auf das Element. 'Find' wird vom Scanner und Parser benötigt.

NewObj(k:ObjektKlasse):ObjPtr;
fügt ein Element an und liefert einen Zeiger darauf. Diese Funktion wird im Parser benutzt.

KickOuttable(name:Str10);
wirft 'name' komplett aus der Symboltabelle hinaus. KickOuttable wird nur vom Parser benutzt.

Damit ist bereits ein wichtiger Teil des DOIT-Compilers beschrieben. Die Ziele sind abgesteckt und die zu überwindenden Schwierigkeiten angedeutet. Die nächste Folge führt dann mitten in die Praxis und wird einen Scanner für die Sprache DOIT vorstellen, der auch schon ohne Parser lauffähig ist und nach Strich und Faden getestet werden kann.