Compiler selbstgeschneidert

Teil 3: Der Parser

Helmut Richter

Die Beschreibung des Selbstbau-Compilers für die Sprache DOIT wird mit dieser Folge fortgesetzt. Diesmal geht es um den Parser, der die syntaktische Analyse durchführt. Er überprüft, ob der Programmtext die Refeln für den Aufbau eines DOIT-Programms einhält. Dazu verwertet er die Informationen, die der in der letzten Folge vorgestellte Scanner aus dem Programmtext ableitet, er setzt also die Scanner-Prozeduren voraus. Beide Compiler-Teile zusammen sind voll funktionsfähig und ermöglichen es, die ersten beiden Schritte des Übersetzungsvorganges ablaufen zu lassen und ausführlich zu studieren.

Wie schon beim Scanner ist auch die hier vorgestellte Software ein über den reinen Parser hinausgehendes Stand-alone-Programm mit integrierten Testrotinen. Es ist also zusammen mit dem Scanner in sich lauffähig, kann DOIT-Programme analysieren und gibt alle gewonnenen Informationen und Ergebnisse auf dem Bildschirm aus. Die lexikalische und syntaktische Analyse eines DOIT-Programms kann so Schritt für Schritt verfolgt und untersucht werden. Dies macht zum einen die Arbeitsweise des Compilers deutlich und erleichtert zum anderen den Test des Compilers und die Anpassung an eigene Vorstellungen.

Leser der Serie 'Software-Baustelle' werden sich erinnern, daß der Scanner den Zeichenstrom eines Programms daraufhin untersucht, ob er zur Sprache DOIT gehörende Worte enthält, ihn in diese Worte zerlegt und für jedes erkannte DOIT-Wort das entsprechende Grundsymbol an den Parser liefert. So meldet er bei einem ':='-Zeichen das Grundsymbol 'becomes'. Die erste Aufgabe des Parsers ist nun, die vom Scanner gelieferten Grundsymbole zu Sätzen zusammenzufassen, das heißt so lange Grundsymbole aneinanderzureihen, bis sich eine in gewisser Weise abgeschlossene Folge ergibt. Beispielsweise wäre die Folge 'VARsy becomes CONSTsy times VARsy semicolon' ein solcher Satz, der dann auf syntaktische Korrektheit zu überprüfen wäre. Die Aufgaben des Parsers sind im einzelnen:

Die Prozeduren, die den Maschinencode erzeugen, sind in dieser Version des Parsers noch nicht enthalten, sie werden im nächsten Teil dieser Serie votgestellt.

Anpassung des Scanners
Um den Scanner aus der letzten Folge mit dem Parser zu kombinieren, sind einige Vorbereitungen nötig. Der hier beschrittene Weg ist, SCANNER in vier Teile zu zerlegen und als Include-File in das Programm PARSE einzubinden. 

PROGRAM PARSER;

CONST
  (*$I SCCONST.INC *)
  Test : BOOLEAN = TRUE;
TYPE
  (*$I SCTYPE.INC *)
 ... Parser-Typen ...
VAR
  (*$I SCVAR.INC *)
 ... Parser-Variablen ...

(*$I PARS-001.INC *)
(*$I PARS-002.INC *)
(*$I PARS-003.INC *)
(*$I PARS-004.INC *)

PROCEDURE Parse;
BEGIN
 ...
END;

BEGIN
(* Testhauptprogramm *)
  level := 0;
  neu := FALSE;
  Parse;
END.
Der Scanner wird in Form von vier Include-Files in den Parser eingebunden.
Das File SCCONST.INC enthält alle Konstanten des Scanners, SCTYPE.INC die Typen und SCVAR.INC alle Variablen. Die Schlüsselwörter CONST, TYPE und VAR dürfen in den Includes nicht noch einmal auftreten. Der Aufbau der Datei PARSER.PAS geht von dieser Aufteilung aus. Die eigentlichen Scanner-Prozeduren sind in PARS-001.INC enthalten. Die restlichen Include-Files beinhalten die Parser-Unterprogramme in einer groben Gliederung nach ihrer Funktion. Insgesamt sind die Dateien PARS-00x.INC wie folgt aufgebaut:

PARS-001.INC - die kompletten Scanner-Prozeduren.

PARS-002.INC diverse Hilfsfunktionen:
TestAusgabe(s:STR255);
ProcCall;
MakeData(VAR adr:Integer;Laenge:Integer);
NewObj(k:OnjektKlasse):ObjPtr;
Find(id:STR10):ObjPtr;
TestSym(s:Symbol;n:Cardinal);
TestSemicolon;

PARS-003.INC - Analyseroutinen I:
Expression;Factor;Term;Condition;Statement;IFstatement;

PARS-004.INC - Analyseroutinen II:
Block;

War der Scanner im informatorischen Sinne ein deterministischer endlicher Automat, so stellt der Parser im wesentlichen einen Automaten mit Gedächtnis, einen Kellerautomaten dar. Das Thema 'Automaten' kam bereits im Artikel 'Bernie und die Automaten' (c't 8/85) zur Sprache.

In DOIT wird zur Satzanalyse das Verfahren des 'rekursiven Abstiegs' verwendet, es ist eine Top-Down-Analyse-Strategie, wie sie die Serie 'Software-Baustelle' bereits näher beschrieb. Das wesentliche Merkmal dieser Methode ist es, Unterprogramme passend zur EBNF-Definition der Sprachsyntax aufzurufen und sich so im Ableitungsbaum 'nach unten' zu hangeln. Um einen Parser zu bauen, hat man folglich für jeden Begriff, der in der EBNF-Definition auf der linken Seite auftritt, ein Unterprogramm bereitzustellen. Die Aufrufbeziehungen der Unterprogramme im Parser spiegeln die Struktur der EBNF-DEfinition von DOIT wider und sind hier noch einmal skizziert.

[EBNF-Definition]
Die Aufrufbeziehungen im Parser spiegeln die Struktur der EBNF-Definition von DOIT wider. Rekursiven Definitionen entsprechen rekursive Prozeduren.
Die Pozedur PARSE ist gemäß der syntaxgesteuerten Übersetzung das Hauptprogramm für den gesamten Ablauf. Ihre erste Aktion ist die Einstellung bestimmter Compileroptionen:

$A-: relativer Code, wegen der rekursiven BLOCK, STATEMENT und EXPRESSION
$U-: keine Benutzerunterbrechung mit Ctrl-C, manche Compiler werden ohne diese Voreinstellung ausgeliefert.
$C+: Bei READ oder READLN unterbricht ein Ctrl-C den Programmablauf. Später: $C-.

Dann initialisiert PARSE den Scanner und die Symboltabelle (TopScope := NIL;), prüft den Programmkopf nach der Reihenfolge 'MODULEsy Indentifier Semikolon' und ruft BLOCK.

Schließt das Programm mit einem Punkt ab, und war auch sonst alles wie es sein soll, zeigt NOERR an, daß das Quellprogramm fehlerfrei war, und die Analyse ist beendet. Andernfalls meldet NOERR die Fehler.

Völlig analog verhält sich BLOCK. Die durch die EBNF vorgegebene Sprachdefinition von block muß in due Struktur der Prozedur BLOCK abgebildet werden und legt so den Analyseverlauf fest.

Marsch durch den Parser
Nach der groben Beschreibung der Programmstruktur folgt nun die Besprechung der Prozeduren in der Reihenfolge des Listings. Da PARS-001.INC den schon besprochenen Scanner beinhaltet, wird sofort PARS-002.INC eingegangen.

Im wesentlichen liegen hier jene Unterprogramme vor, die nur helfend zur Satzanalyse beitragen. So hat TESTAUSGABE die Aufgabe, den Ausdruck von Hinweisen über den Zustand des Parsers während des Übersetzungsprozesses sichtbar zu machen. Mit der logischen Variablen TEST läßt sich die Ausgabe unterdrücken, später kann sie ganz entfernt werden.

PROCCALL bearbeitet eine Prozedurreferenz, also den Aufruf eines vorher deklarierten und definierten Unterprogramms. Ihre Rolle tritt erst bei der Erzeugung von Objektcode auf, jetzt muß sie lediglich als 'Skelett' vorhanden sein. Ähnlich wie PROCCALL hat MAKEDATA ihren Auftritt erst bei der Codegenerierung. Sie muß den Speicherplatz für die lokalen Variablen anlegen.

NEWOBJ dagegen wird jetzt schon benötigt. Sie soll ein neues Objekt in die aktuelle Symboltabelle eintragen und tritt bei der Abarbeitung der Deklaration in Aktion. Sie muß beachten, ob der Identifier schon einmal deklariert worden ist. Dies geschieht durch 

IF Idname = Obj^.Name THEN ...
Tritt dieser Fall ein, so erfolgt die Meldung 'Identifier doppelt deklariert', und die Prozedur witd mittels EXIT (Turbo-Pascal 3.0) beziehungsweise GOTO 99 (Turbo-Pascal 2.0) verlassen.

Ansonsten wird ein neues Element unter Berücksichtigung der Objektklasse angelegt:

Im Varianten-Teil des beschreibenden Records erfolgt die Speicherbelegung gemäß 

CASE Kind OF
  CharacterCon : CWert := CharVal;
  IntegerCon : IWert := IntVal;
  Prozedur : Startadresse := 0;
  CharVar : MakeData(Daten-
    Adresse,1);
  IntVar : MakeData(Daten-
    Adresse,2);
  Nix : ;
END;
Die Belegung von Start- und Datenadresse hat wieder vorläufigen Charakter.

Die Funktion FIND soll die aktuelle Symboltabelle von ihrem Beginn her nach dem in IDNAME ausgezeichneten Identifier sequentiell durchsuchen und im Erfolgsfall einen Zeiger auf den gefundenen Record als Wert von FIND liefern.

Zwecks schnelleren Auffindens der momentan gültigen Symboltabelle mit den 'lokalen' Daten zeigt TopScope auf deren Header, sprich den ersten Record. Dies wird in der Anweisung 'Hd := TopScope;' ausgenutzt, worauf Hd die Rplle des Suchzeigers übernimmt.

Entdeckt FIND in dieser Tabelle den gesuchten Identifier nicht, so kann es sich um eine Referenz auf ein globales Datum handeln. Pb dies der Fall ist, kann bei der Betrachtung des Zeigers down im Header entschieden werden. Dabei besagt Hd^.down < > NIL, daß die momentane Analyse sich in einem Unterprogramm (PROC) abspielt und darüber möglicherweise globale Daten des Hauptprogramms liegen, sofern jenes überhaupt Daten besitzt.

In diesem Fall muß die erfolglos durchsuchte Tabelle verlassen und die nächst höhere durchforstet werden. Die Umblendung geschieht durch 'Hd := Hd^.down;'. Hd^.down = NIL bedeutet, daß wir auf Hauptprogrammebene sind und es keine globalen Daten mehr gibt.

Ist der gesuchte Bezeichner immer noch nicht gefunden, so war er nicht deklariert und eine Spezialbehandlung wird erforderlich. Zunächst wird eine Fehlermeldung ausgegeben. Will man nun vermeiden, daß bei jedem weiteren Auftreten dieses Identifiers wieder die gleiche Fehlermeldung auftritt, so muß er in die lokale Tabelle eingetragen werden. Als Objektklasse bekommt er ein Nix, da man nicht entscheiden kann, von welchem Typ er ist. Die entsprechende Programmanweisung ist 'Find := NewObj(Nix);'.

Eine implizite Typendeklaration wie in BASIC oder FORTRAN geschieht nicht, könnte aber an dieser Stelle eingefügt werden.

Die Codegenerierung wird in ERROR abgebrochen, somit kann im Fehlerfall kein Schaden im Maschinencode entstehen.

TESTSYM prüft das übergegebene Symbol. Sie dient dem möglichst guten Aufsetzen der Analyse im Fehlerfall. An dieser Stelle wird die spezielle Anordnung der Symbolmenge (Anfangssymbole zuletzt) benötigt. TESTSEMICOLON untersucht, ob ein Semikolon vorliegt. Ist dies der Fall, so wird das nächste Symbol geholt, sonst das Fehler reklamiert und sym unverändert zurückgereicht.

Das Modul PARS-003.INC enthält nur Analyseprogramme. Als erstes befindet sich EXPRESSION mit seinen lokalen Prozeduren FACTOR und TERM darin. Die Serie 'Software-Baustelle' ging bereits auf die EBNF von arithmetischen Ausdrücken ein und stellte entsprechende Syntaxdiagramme vor (c't 10/85, S.96/97).

CONDITION findet seine Anwendung bei der Untersuchung der Bedingung im IF-Statement.

Diese Prozedur testet zwei Fälle. In DOIT können logische Ausdrücke entweder mit dem einstelligen Operator ODD oder mit zweistelligen Vergleichsoperatorengebildet werden. Am Ende von CONDITION enthält sym bereits das der Bedingung folgende Symbol, es wird in FACTOR geholt. Für die Codegenerierung wird hier einiges zu ergänzen sein.

Des Parsers Kern
Die letzte Prozedur von PARS-003.INC ist STATEMENT. Sie bildet den Hauptteil der syntaktischen Analyse, ähnlich wie SCANNER jener der lexikalischen war. In ihr werden alle Anweisungen der Sprache DOIT untersucht und vollständig bearbeitet.

Die erste Aktion besteht in einer Prüfung des vorliegenden Symbols. Ist es unbrauchbar, wird der Quelltext mit 'TestSym(semicolon,98);' so lange überlesen, bis ein Anfangssymbol gefunden ist. Der erste Zweig von STATEMENT bearbeitet Zuweisungen und Prozeduraufrufe, die mit einem Identifier beginnen. Im Programm sieht das so aus: 'IF sym = Identifier THEN ...'.

Der gefundene Name wird nun mit 'Obj := Find(idname);' in der Symboltabelle gesucht. Die Bedingung, daß ein benutzter Bezeichner deklariert worden sein muß, ist übrigens kein kontextfreier, sondern ein kontextsensitiver Zusammenhang. Nach dieser Kontrolle erfolgt die Bearbeitung entsprechend der Objektklasse des Identifiers. Gilt 'Obj^.kind = Prozedur', wird zu PROCCALL verzweigt.

Ein Variablenname liegt vor, wenn Obj^.kind < > Nix ist. Es folgt der Test auf becomes, dann kann EXPRESSION den Rest erledigen.

War Obj^.kind weder eine Prozedur noch ein gültiger Bezeichner, so liegt ein nicht deklarierter Identifier vor. Anhand des Folgesymbols kann man entscheiden, ob es sich um Prozeduraufruf oder Zuweisung handelt: 
IF sym = Semicolon THEN ProcCall
ELSE BEGIN
  IF sym = becomes THEN GetSym
  ELSE Error(11,':= erwartet');
  Expression;
END;

Das DOIT-Schleifenkonstrukt DO .. OD ist die nächste mächtige Anweisung. Hier besteht das Hauptproblem im Erkennen des Schleifenendes bei vergessenem OD. Daher wird vor seiner Abarbeitung eine Menge von Folgesymbolen des DO festgelegt: 
Folgesymbole := [ODsy, ENDsy,
       period, eofsy];
GetSym;
REPEAT
  Statement;
UNTIL sym in Folgesymbole;
Anschließend wird getestet, ob das Konstrukt ordnungsgemäß verlassen wurde.

Die lokale Prozedur IFstatement ist ein Speizialunterprogramm zur Bearbeitung des IF-Statements und der dabei auftretenden Fehlerfälle. Im wesentlichen ist dies das korrekte Aufsetzen bei Fehlern (FI vergessen).

Beim IF-Statement tritt aber noch eine zweite Schwierigkeit auf, deren Lösung jeder Programmierer unbewußt kennt: das Dangling-ELSE-Problem.

Dangling-ELSE
Zreten verschachtelte IF-Statements auf, so stellt sich die Frage, zu welchem IF das erste auftretende ELSE gehört. Bispiel: 
IF <condition1> THEN
IF <condition2> THEN
 <statement>
ELSE
 <statement>
FI;
ELSE
 <statement>
FI;
Ohne Einrückungen, die sowieso kein Compiler auswertet, ist nicht klar, ob das erste ELSE zum ersten oder zweiten IF gehört. Die weitestverbreitete, aber nicht einzige Lösung ist, das ELSE zum letzten IF zu schlagen.

In DOIT wird dieses Problem schon durch die Verbundeigenschaft des IF-Statements gelöst. Würde das erste ELSE zum ersten IF gehören, so müßte davor ein FI zum Abschluß des inneren IF-THEN-Statements stehen. Wurde hingegen das FI vergessen, so bleibt die Blockstruktur des IF-THEN-ELSE-FI offen. Dies ist der schwierigste Fehlerfall.

Eine sichere Korrektur ist leider nur ein einem einzigen Spezialfall möglich: 
IF <cond1> THEN
   IF <cond2> THEN
      <statement>
   ELSE <statement>
ELSE..

Trifft man in der Analyse nach einem ELSE ein weiteres ELSE an, so ist sicher, daß im inneren IF-Statement das FI vergessen wurde. Im Parser besteht jetzt folgende Rekursionssituation: eine Stufe 'über' uns befindet sich STATEMENT, darüber der THEN-Zweig des äußeren IF-Statements.

Eine brauchbare Fehlerbehandlung erforder das korrekte Neaufsetzen des Parsers, also das 'Flicken' der defekten Programmstruktur. Am einfachsten kann kann man das hier erreichen, indem man das nächste Symbol nicht liest, sondern SYM nach der Fehlermeldung 'FI erwartet' unverändert an die aufgerufene Prozedur zurückgibt.

Dies ist zwar eine klare Abweichung von Wirths Fehlerbehandlungsstrategie, keine speziellen Fehlerausgänge in Analyseprozeduren einzubauen, betrifft hier jedoch nur einen Sonderfall und ist zudem sehr wirksam.

Mit EXIT wir ein DO-OD-Block verlassen. Die detaillierte Bearbeitung geschieht erst bei der Codegenerierung.

READ und WRITE stellen im Prinzip keine einfachen Statements, sondern Unterprogrammaufrufe dar. Dementsprechend müssen sie durch ein 'Laufzeitsystem' zur Verfügung gestellt werden. Ähnlich verhält es sich bei mathematischen Operationen (+, -, *, ...).

Als letzte Möglichkeit wird das 'leere' Statement, ein einsames Semikolon, getestet. TestSemicolon prüft, ob ein das Statement abschließendes Semikolon existiert.

Rekursion als Prinzip
Das Modul PARS-004 enthält nur die Prozedur BLOCK. Ihr Aufgabengebiet umfaßt die Bearbeitung des Programmblocks, also Deklarationen der Konstanten, Variablen und Prozeduren sowie des dann folgenden Anweisungsteils. Die deklarierten Konstanten und Variablen werden dabei in einer neuen, sozusagen lokalen Symboltabelle gesammelt.

BLOCK untersucht sowohl den Rumpf des Hauptprogramms als auch jene der Prozeduren. Die Rekursionstiefe der Prozedur BLOCK macht der Zähler LEVEL sichtbar. Ist er größer als 1, wird der Fehler 'verschachtelte Prpzeduren nicht erlaubt' gemeldet.

Bei jeder Deklaration, auf die Block trifft, wird durch MARK(Heap,Top) die Speichergrenze für die neue Symboltabelle markiert. Die Anweisung NEW(Hd) erzeugt den Kopf-Record, der dann mit 'Hd^.down := TopScope'mit der alten Tabelle verkettet wird.

Sucht man nach globalen Variablen, so kann die Symboltabelle des Hauptprogramms an Hd^.down = NIL erkannt werden. TopScope := Hd richtet TopScope zwecks schnelleren Zugriffs auf den Anfang der neuen Tabelle.

fall LEVEL = 0 ist, also der Block des Hauptprogramms vorliegt, wird Bottom auf den Header der ersten Symboltabelle gerichtet (Bottom := Hd;) und markiert so den Boden des Heaps der Tabellen. Später wird LEVEL bei der Berechnung von Variablenadressen begilflich sein.

Die Konstanten- und Variablendeklarationen werden mit den Unterprogrammen CONSTANTDECLARATION und VARDECLARATION analysiert, während Prozeduren direkt abgearbeitet werden. Doch zunächst ein Blick in CONSTANTDECLARATION.

Nach dem Wort CONST muß ein Name folgen, danach ein Gleichheitszeichen, dann eine Konstante. Dem Typ der Konstanten entsprechend kann nun der Eintrag der Objektklasse (Typ) und des Konstantenwertes in die Symboltabelle gemacht werden. Der Umstand, daß der Identifier den Typ der Konstanten erhält, ist wieder kontextsensitiv.

In DOIT kann man mehrere Konstantendeklarationen durch Semikolon trennen oder das Wort CONST bei jeder Konstantendeklaration neu vor den nächsten Identifier schreiben. Erkennbar ist dies an: 'WHILE (sym = CONSTsy) OR (sym = Identifier) DO...'

Ähnliches gilt für Variablendeklarationen, nur wird hier der Typ der Variablen explizit durch INT oder CHAR festgelegt und statt des 'Variablenwerts' ihre Ablageadresse eingetragen. Die Aufzählung mehrerer Variablen gleichen Typs ist in dieser Version nicht möglich.

Mit dem Symbol BEGINsy startet der Statement-Teil, es folgt nun die Analyse des eigentlichen Programmrumpfes: 'WHILE (sym <> ENDsy) AND (sym <> eofsy) DO Statement;'. 

 1. MODULE erwartet
 2. Integer- oder Characterkobstante erwartet
 3. "=" erwartet
 4. Identifier erwartet
 5. ";" erwartet
 6. Statement erwartet
 7. ")" erwartet
 8. BEGIN erwartet
 9. END erwartet
10. "." erwartet
11. ":=" erwartet
12. - 13. frei
14. Nach READ identifier erwartet
15. THEN erwartet
16. FI erwartet
17. OD erwartet
18. Ausdruck erwartet
19. frei
20. Relation erwartet
21. Prozeduren hier nicht erlaubt
22. Verschachtelte Prozeduren nicht erlaubt
23. frei
24. Identifier nicht deklariert
25. Identifier doppelt deklariert
26. - 30. frei
31. FI erwartet
32. frei
33. Nach ":" INT oder CHAR erwartet
34. ":" erwartet
35. - 50. frei
51. Integerzahl zu groß
52. Falsches Zeichen in Integerzahl
53. Characterkonstante ungültig
54. Hochkomma erwartet
55. Hexkonstante falsch: Fehler im High-Byte
56. Hexkonstante falsch: Fehler im Low-Byte
57. - 97. frei
98. Dieses Symbol darf hier nicht stehen
99. Compilerfehler
Diese Fehler werden vom Parser erkannt und gemeldet.

[Listing]
Diese Parser-Module müssen mit den Scanner-Routinen aus der letzten Folge kombiniert werden. Beide zusammen sind in der Lage, DOIT-Programme im Einzelschritt-Verfahren zu analysieren. Alle erkannten Informationen werden dabei auf dem Bildschirm ausgegeben.
Wirth hat diese Schleife vermieden, indem er BEGIN als Statement betrachtete und dementsprechend in STATEMENT eine Rekursion der Art: 
...
ELSE IF sym = BEGINsy THEN BEGIN
  GetSYm;
  REPEAT
     Statement;
     IF sym = Semicolon THEN GetSYm
     ELSE IF sym = ENDsy THEN EXIT;
     ELSE IF sym < CONSTsy THEN Error(..)
     ELSE Error(..);
  UNTIL FALSE;
END;
...
einfügte und in BLOCK nach den Deklarationen sofort STATEMENT aufruft. Dieses Konstrukt hat zudem den Vorteil, Anweisungen zwischen BEGIN und END zu klammern. Will man es einbauen, so sollte man in BLOCK die Prüfung von BEGIN und END herausholen.

Zum Schluß wird getestet, ob ein ENDsymbol vorliegt, TopScope muß auf die nächst höhere Symboltabelle (oder NIL) geschaltet (TopScope := TopScope^.down;) und der von der lokalen Symboltabelle reservierten Speicherplatz freigegeben werden (RELEASE(HeapTop);) Hat man den MARK/RELEASE-Mechanismus micht zur Verfügung, so hilft die Prozedur KillTable. 

Vorbereitung:
Neue globale Variable VORGAENGER vom Typ OBJPTR
einrichten und mit NIL initialisieren.
In FIND VORGAENGER := OBJ vor OBJ := OBJ^.NEXT
einf}gen.

  PROCEDURE KillTable;
  VAR hd, loesch : Objptr;

    PROCEDURE KickOutTable(p:Objptr);
(*  Loescht ein neliebiges Record der Tabelle *)
    VAR p1 : Objptr;
    BEGIN
(*    Zuerst VORGAENGER richtig setzen        *)
      p1 := FIND(p);
      Vorgaenger^.next := p^.next;
(*    Falls p = letztes Record Topscope^.last *)
(*    korrigieren                             *)
      IF p = TopScope^.last THEN
        TopScope^.last := Vorgaenger;
      DISPOSE(p);
    END (* KickOutTable *);

  BEGIN (* KillTable *)
    hd := TopScope;
    WHILE hd^.next <> NIL do KickOutTable(hd^.next);
    TopScope := TopScope^.down;
    DISPOSE(hd);
  END (* KillTable *);
Diese Prozedur leistet gute Dienste, wenn der Mark/Release-Mechanismus nicht zur Verfügung steht.
PARSE wurde schon oben beschrieben, somit sind alle Teile grob umrissen.

Wenn Sie geduld- und programmiermäßig an diese Stelle gelangt sind, so benötigen Sie nur noch ein paar Testprogrämmchen ihne und mit Fehlern und können dann den Parser im Single-Step analysieren lassen. 

module test;
var i : int;
BEGIN
  IF i <> 6 THEN
    i := 6   (* ';' fehlt *)
    IF i >= 10 THEN
      WRITE i;
      EXIT   (* ';' fehlt *)
    ELSE
      i := 6 + 9;
      ! i;   (* FI fehlt, aber ... *)
  ELSE
    x;       (* Proc X nicht dekl. *)
    i := i + 9;
  FI;
END.

MODULE Test;
(* Allgemeines Testmodul für DOIT *)
VAR x       : INT;
VAR y       : INT;
VAR i       : INT;
VAR ch      : CHAR;
BEGIN
  IF i <> 6 THEN i := 6; ELSE i := 9; FI;
  x := x + 6;
  ?  x;
  DO
    i := i + 1;
    IF i >= 10 THEN EXIT; FI;
  OD;
  ! x;
END.

MODULE Test2;
(* Konstante, Variable, Prozedur. *)
CONST pi = 3;
      esc = $1B;

VAR x       : INT;
    ch      : char;

PROC Test2;
var x : int;
    ch      : char;

BEGIN
  ? x;
  ! x;
END (* TEst 2 *);

BEGIN (* Hauptprogramm *)
  IF x>6 THEN x := 6; ELSE ; FI;
END.

MODULE Test2;
(* Testmodul für den DOIT-Parser mit FEhlern *)
VAR x       : INT;
VAR ch      : CHAR;

PROC ReadX;
BEGIN ? x END;

BEGIN
  IF i << 6 THEN i := 6;
  x := y + 6;
  ? x;
  DO
    i := i + 1;
    IF i <= 10 THEN EXIT; FI;
  OD;
  ! ;
END.
Einige DOIT-Beispielprogramme ohne und mit Fehlern als Testobjekte für Scanner und Parser.
[2. Teil] [Inhalt] [4. Teil]

Edited by Werner Cirsovius
April 2011
© Heise Verlag