Turbo Toolbox

home *** CD-ROM | disk | FTP | other *** search

/ Turbo Toolbox / Turbo_Toolbox.iso / spezial / 02 / texte / pascomp.8 < prev

Wrap

Text File | 1980-01-03 | 20.3 KB | 526 lines

PASCOMP PASCAL baut einen Pascal-Compiler Teil 8: Erweiterungen von Johannes Velmans In diesem letzten Teil der Serie über Compilerbau möchte ich Sie mit dem Erweiterungskonzept des PASCOMP-Pascalcompilers vertraut machen. Nach langem Warten ist nun mittlerweile die komplette Compilersource für jeden PASCAL-Leser zugänglich. Sicherlich stellt der eine oder andere Leser gewisse Anforderungen an den Compiler, die dieser bis jetzt noch nicht erfüllen kann. Aller- dings soll das PASCOMP-Projekt, wie das in einer der ersten Fol- gen bereits betont wurde, keinen "Super"-Pascal-Compiler hervor- bringen, sondern nur einen Einblick in den Compilerbau verschaf- fen. Erinnern wir uns... So mußten fast immer Kompromisse hinsichtlich der Effizienz ge- macht werden, da an vielen Stellen immer wieder effizientere Me- thoden zu Gunsten einfacherer und verständlicherer Verfahren in den Hintergrund traten. Einige Vorteile haben Sie als regelmäßi- ger PASCAL-Leser jedoch errungen. Sie verfügen immerhin über ei- nen kompletten und lauffähigen Standard-Pascal-Compiler. Bislang existiert sicherlich genügend Material, das eine Einführung in den Compilerbau ermöglicht. Allerdings gibt es in fast keinem Werk so etwas wie einen kompletten und lauffähigen Compiler. Meist beschränkt man sich in der Literatur auf die Konstruktion eines Mini-Compilers, der dann irgendwelche Teilmengen einer gän- gigen Programmiersprache akzeptiert. Mit diesem vollständigen Compiler- Listing sind Sie nun auch in der Lage - basierend auf diesen Compiler - Implementierungen an- derer imperativer Programmiersprachen wie Basic, Modula-2, C usw. vorzunehmen. Dies entspricht übrigens dem gängigen Implementie- rungs-Verfahren einer neuen Sprache: Diese wird nämlich in einer bereits bestehenden Programmiersprache entwickelt, die die größte Teilmenge der neuen Sprache beinhaltet. Das bedeutet aber zu- gleich, daß dieser Compiler auch "offen" für Erweiterungen ist. Ähnlich wie man seinen Rechner durch Hardware-Karten "aufblasen" kann, so kann man zum Beispiel den PASCOMP-Compiler um die vorde- finierten Typen "String" und "long integer" erweitern oder das Konzept der parallelen Prozesse einführen (Hanssen-Pascal). Wie man solche Erweiterungen konsequent durch den Aufbau der Com- piler- Source "hindurchzieht" soll das Thema dieser letzten Folge sein. Also auf zum letzten Angriff .... Compilererweiterungen Derjenige, der sich den PASCOMP- Compiler näher ansieht, wird feststellen, daß doch einige Routinen über den vorgeschriebenen Standard hinausgehen. Da ist zum Beispiel die ansatzweise Imple- mentierung von Betriebssystem-Aufrufen des Atari ST und die voll- ständige Implementierung des quasi-Standard-Typs "long integer" zu nennen. Anhand der "long integer" Implementierung wollen wir uns die Erweiterung der Compiler-Source mit selbstgebastelten Typen näher anschauen. Zunächst aber wollen wir dem Kind erst mal einen Namen geben. In ST- Pascal wird der entsprechende Typ mit "Long_Integer" bezeich- net. Dies erscheint ein bischen lang. Meine Wahl fiel daher auf "LongInt". Initialisiert wird der Name "LongInt" in der Prozedur "Initstandardtypes". Wer sich einen anderen Namen für diesen Typ wünscht, der kann in dieser Prozedur den entsprechenden Namen än- dern. So einfach geht das. Bei der weiteren Besprechung aber soll der Name "LongInt" zur Bezeichnung dieses Types beibehalten wer- den. Programmstücke wie ... VAR longinteger: LongInt; ... longinteger := longinteger + 10; ... müssen daher im Nachfolgenden vom Compiler als richtig erkannt werden. Wie geht man nun aber die Sache an und strickt an den richtigen Source- Stellen die richtigen Erweiterungen ein? Nun, im Speziel- len wird das sicherlich unterschiedliche Vorgehensweisen bedin- gen. Im Großen und Ganzen läßt sich aber sagen, daß ein schritt- weises Abklären der nachfolgend aufgeführten Punkte hinreichend für eine geeignete Implementierung des gewünschten Typs, Proze- dur, Funktion o.ä. ist. Hierbei ist auch zu beachten, daß zum Beispiel die nachträgliche Aufnahme von neuen Standard-Prozeduren in das Source- Listing weitaus einfacher ist als die hier darge- stellte Typ-Implementierung, da viele der vorgestellten Schritte einfach entfallen. Und dann noch ein Tip: Da in dem nachfolgenden Text sehr oft Bezüge zum Compiler- Listing auftreten, ist es für das bessere Verständnis am sinnvollsten den Compiler-Text griff- bereit zu halten. Nun - fangen wir an .... 1. Schritt: Konstanten, Typen und Variablenerweiterungen. Die meisten Konstanten, die im Compiler-Listing verwendet werden, stehen in direktem Zusammenhang mit der Speicherabbildung der vordefinierten Typen. Die Konstantennamen "intsize", "realsize", "boolsize" usw. deuten dies an. Auch für den Typ "LongInt" findet sich eine Konstante "longsize" (=1), welche die Größe der Spei- cherabbildung - bezogen auf den Interpreterspeicher - festlegt. Fast alle in einem Pascal-Programm auftretenden Konstanten werden in Verbunden (Records) vom Typ Konstante abgelegt. Hier speichern wir auch unsere "LongInt"-Konstanten. Dazu muß dieser Record ent- sprechend erweitert werden. Zuerst einmal vergößern wird den Auf- zählungstyp Constklasse: Constklasse=(reell,setkonst,strg,long); und führen gleichzeitig in den Typ Konstante eine neue Variante ein, und zwar: Konstante = RECORD CASE konstart: constklasse OF ... long: (savval: Long_Integer); (**) END; Zu (**): Hier weicht die Implementierung, wie an wenigen anderen Stellen und hauptsächlich bei Benutzung von Stringfunktionen, von der Standard-Pascal-Definition ab. Der hier benutzte Typ "Long_Integer" ist dem ST-Pascal für den ATARI ST entnommen, in- dem auch das Compiler-Listing erstellt wurde. Verwendet man ande- re Compiler zur Übersetzung von PASCOMP, die diesen Typ nicht implementiert haben, so kann man den Typ "LongInt" zum Beispiel auch durch zwei normale Integer-Typen oder noch einfacher durch den Real-Typ programmieren. Dies sähe dann in etwa so aus: Konstante = RECORD CASE konstart: constklasse OF ... long: (highword,lowword: INTEGER); bzw. long: (savval: REAL); END; Im übrigen wird es in den meisten Fällen von Typerweiterungen so sein, daß die neu zu implementierenden Typen von dem die Source übersetzenden Compiler nicht beherrscht werden. Man denke zum Beispiel an die Einführung eines Typs für imaginäre Zahlen, der sicherlich in vielen Mathematik-Programmen einen Sinn macht und es so von Vorteil wäre, diesen Typ als Standardtyp definiert zu wissen. Dabei wird es wohl keinen Compiler geben, mit dem dieser Typ wie in unserem Beispiel der Typ "LongInt" direkt implemen- tiert werden kann. Soweit zur Einführung von weiteren Typen in die Compiler-Source. Als letztes wird noch eine neue Variable "LongPtr" vom Typ "STP" eingeführt, der eine wichtige Bedeutung bei späteren Kompatibilitäts- Überprüfungen zu Gute kommt. 2.Schritt: Definition der auf "LongInt" zulässigen Operationen Für den Typ "LongInt" sind die Arithmetik-Operationen -un, +, -, *, DIV und MOD, sowie die Ein- und Ausgabe- Prozeduren Write und Read zugelassen. -un bezeichnet dabei das unäre Minus, das zum Beispiel in der Zuweisung a := -1 vorkommt. Eine der Hauptaufga- ben der Compiler-Source-Erweiterung besteht nun darin, für alle diese Operationen und Prozeduren entsprechende P-Code-Befehle bereitzustellen. Wer den Compiler-Source-Text überfliegt, wird sicherlich auch die verschiedenen Initialisierungs-Prozeduren entdecken. Für diesen zweiten Schritt sind die Prozeduren "InitStdProcs" und "InitPCodeInstruction" von Bedeutung. In den damit korrespondie- renden Arrays "StdNames" und "PCO" werden P-Code- Befehle für die Ein- und Ausgabe sowie für die Arithmetik untergebracht. Die nachfolgende Tabelle gibt einen Ausschnitt der beiden Arrays wie- der: neue "long integer" Operationen: Operation │ P-Code ─────────────┼────────────── -un │ ngl + │ adl - │ sbl * │ mpl div │ dvl mod │ mdl │ ilo,ilt │ (Typanpassung Integer -> LongInt) │ lfo,lft │ (Typanpassung LongInt -> Real) write │ wrl read │ rdl 3. Schritt: Kompatibilitätsprobleme In der gleichen Weise, in der auch Kompatibilitäten zwischen In- teger und Real überprüft werden, muß auch der Typ LongInt auf Typverträglichkeit hinsichtlich der bereits bestehenden Standard- Typen untersucht werden. Zur besseren Veranschaulichung seien sämtliche Typkombinationen zwischen Integer, LongInt und Real in einer Tabelle dargestellt. Dabei bedeutet xi ist kompatibel zu yj genau dann, wenn yj := xi eine erlaubte Zuweisung darstellt. Die Kürzel k und nk stehen für kompatibel und nicht kompatibel. xi\yi │ INTEGER │ LONGINT │ REAL ────────┼─────────┼─────────┼────── INTEGER │ k │ k │ k ────────┼─────────┼─────────┼────── LONGINT │ nk │ k │ k ────────┼─────────┼─────────┼────── REAL │ nk │ nk │ k Die Tabelle macht deutlich, daß in genau drei Fällen Typanpassun- gen erforderlich werden. Dies sind 1. INTEGER -> REAL (flo,flt). 2. INTEGER -> LONGINT (ilo,ilt). 3. LONGINT -> REAL (lfo,lft). Da der erste Fall unabhängig von unserem neueingeführten Typ ist, bleiben nur die beiden letzten Fälle zu behandeln. Die in Klam- mern angegebenen Befehle, die im Array "PCO" ab Index 66 gespei- chert sind, bezeichnen die P-Code-Befehle für die Typanpassung. Dazu eine kleine Erklärung: Wie eigentlich alle P-Code-Befehle haben auch die Typanpassungs-Befehle eine unmittelbare Auswirkung auf den Laufzeitkeller (s. PASCAL 1/88 & 2/88, Codeerzeugung und Interpreter). Mit 't' endende Befehle beziehen sich dabei immer auf die Spitze des Laufzeitkellers und führen ihre Konvertierung dort aus. Die Befehle, die auf 'o' enden, bewirken eine Typan- passung auf den Inhalt des zweiten Elements oben auf dem Stack. Warum gibt es aber zu jedem der drei genannten Fälle zwei P-Code- Befehle für je eine Typanpassung. Eine Antwort hierauf gibt ein näherer Einblick in die Implementierung der Auswertung von Aus- drücken. 4. Schritt: Auswertung von Ausdrücken. Falls wir unseren neuen Typ nicht mit Operatoren versehen haben, so können wir diesen Schritt einfach weglassen. Andernfalls muß der Teil des Compilers, der sich mit dem Auswerten von Ausdrücken beschäftigt, näher untersucht werden. Genau dies ist bei dem Typ "LongInt" der Fall. Der Compiler zerlegt jeden Ausdruck in seine entsprechende Postfix-Form. Beispiel: Der Ausdruck a+b wird zu ab+ umgeformt. Bei der Auswertung des Ausdrucks werden immer zwei Operanden auf den Stack gelegt und mit dem Operator verknüpft. Im Anschluß hieran wird das Ergebnis der Auswertung auf den Stack zurückgelegt. Von Bedeutung ist nun, daß eine mögliche Typanpassung nur unmit- telbar vor der Verarbeitung mit dem Operator durchgeführt werden kann. Anschaulich bedeutet das: Auf dem Stack befinden sich zwei Operanden, deren Attribute in den Variablen "LastAttr" und "attr" stehen. Der zugehörige Operator ist in der Variablen "LastOp" gespeichert. Muß vor der Berechnung des Ausdrucks noch ein Typ angepasst werden, so werden Typanpassungs-Befehle aus dem P-Code- Befehlssatz gewählt, die auf 'o' enden, wenn "LastAttr" an "Attr" angepasst werden muß. Wenn "Attr" an "LastAttr" angepasst werden muß, werden Befehle mit einer Endung 't' gewählt, . Ein kleines Pascal-Programm soll diesen Sachverhalt verdeutli- chen: PROGRAM a; VAR i: INTEGER; l: LONGINT; BEGIN l := l+i; l := i+l END. Setzt man unseren Compiler auf dieses kleine Programm an, so "spuckt" er das P-Code-Stück aus, wie in Abb.1 zu sehen ist. Die- se hier im vierten Schritt beschriebene Anpassung wird in den Rümpfen der Prozedur "Term" (*, DIV, MOD) und "SimpleExpression" (+,-) durchgeführt und ist anhand des Compiler-Listings leicht nachzuvollziehen. Abb.1: l 3 ent 1 l 4 ent 2 l 5 ; 1.Zuweisung. ldol 10 ; lade Inhalt von l auf den Stack. ldoi 9 ; lade Inhalt von i auf den Stack. ilt ; konvertiere den Wert von i in einen longint Wert. adl srol 10 ; 2.Zuweisung. ldoi 9 ; lade Inhalt von i auf den Stack. ldol 10 ; lade Inhalt von l auf den Stack. ilo ; konvertiere den Wert von i in einen longint Wert. adl srol 10 retp l 4=11 l 5=7 q i 0 mst 0 cup 0 l 3 stp q Der erzeugte P-Code zur Typanpassung in Ausdrücken. 5. Schritt: Verwendung des neuen Typs bei Prozedur-Aufrufen. Der Aufruf von benutzerdefinierten Prozeduren und Funktionen fin- det im Source-Listing in der Prozedur "ExtendedCall" statt. Auch an dieser Stelle darf man nicht vergessen, daß man auch hier mit Kompatibilitäts- Problemen zu kämpfen hat. Denn bei einer Überga- be von Aktual-Parametern müssen die beiden betreffenden zu über- prüfenden Typen nicht gleich, sondern nur verträglich zueinander sein. Eine entsprechende Anpassung von LongInt an Real und Inte- ger an LongInt muß somit in die Pascal- Source mit aufgenommen werden. Auch hier soll ein kleines Pascal-Programm diese Anpas- sung erläutern: PROGRAM b; VAR l: LongInt; PROCEDURE anpassung (r: REAL); BEGIN END; BEGIN anpassung(l) end. Bei diesem Programm gibt der Compiler den in Abb. 2 gezeigten P- Code aus. Abb.2: 1 3 ; Prozedur "Anpassung" ent 1 l 4 ent 2 l 5 retp l 4=6 l 5=5 l 6 ; Hauptprogramm ent 1 l 7 ent 2 l 8 mst 0 ; Eintritt in den Prozeduraufruf. ldol 9 ; Lade den Inhalt von l auf den Stack. lft ; konvertiere den Wert von l in eine Realzahl. cup 1 l 3 ; Aufruf der Prozedur "Anpassung" retp l 7=10 l 8=6 q i 0 mst 0 cup 0 l 6 stp q Der P-Code zur Typanpassung bei Aufrufen benutzerdefinierter Pro- zeduren Sind nun alle fünf Schritte nacheinander abgearbeitet worden, so wird unser erweitertes Compiler-Listing übersetzt - in der Hoff- nung, mit dem neu erstellten Compiler ein Werkzeug geschaffen zu haben, das unseren Ansprüchen ein wenig mehr genügt. Funktioniert erst mal der Compiler, so hat man das größte Stück Arbeit schon hinter sich gebracht. Was bleibt denn noch zu tun? Nun, der Com- piler behandelt jetzt Variablen vom Typ "LongInt" korrekt. Für den Interpreter ist die Erweiterung des Befehlssatzes allerdings noch ein "böhmisches Dorf". Und genau das soll im sechsten und letzten Schritt geändert werden. 6. Schritt: Implementierung des erweiterten P- Code-Befehlssatzes. Als erstes muß dem Interpreter mitgeteilt werden, daß er ab so- fort in der Lage ist, den Typ "LongInt" in seine Speicherklasse mit aufzunehmen. Dies geschieht mittels Einführung einer neuen Variante im globalen Interpreter-Typ "StoreRec", der dann wie folgt aussieht: StoreRec = PACKED RECORD CASE DataType OF ... long: (vl: Long_Integer); ... END; Für den Typ "Long_Integer" gilt auch hier das bei der Implemen- tierung im Compiler gesagte. Als nächstes müssen die im Programm- text auftretenden "LongInt"-Konstanten ähnlich wie bei Set- und Real-Konstanten in ein separates Array untergebracht werden. So- mit vereinbaren wir zwei neue Variable: LongTable: ARRAY [1..MaxLong] OF Long_Integer; LongPos : INTEGER; (* gibt den maximal belegten Index in LongTable an *) Was nun noch fehlt ist die Einführung der neuen Namen in die Ar- rays "PCO" und "SPTable". Dies wird in der Prozedur "Init" durch- geführt. Wer sich noch an die Folge über den Interpreter erin- nert, dem wird sicherlich die Zweiteilung des Interpreters noch ein Begriff sein. In der ersten Phase - der Assemblerphase - wird der textuelle P-Code in einen Zahlencode umgewandelt. Gleichzei- tig werden Sprungtabellen und Konstantentabellen gefüllt. Die daran anschließende Interpreterphase führt diesen Zahlencode dann Anweisung für Anweisung aus. Was die Erweiterung der ersten Phase angeht, so besteht diese allein darin, in der Prozedur "Load- Const" die Konstantentabelle "LongTable" mit eventuell auftreten- den LongInt-Konstanten zu füllen. Das hier einzufügende Programm- stück erklärt sich von selbst: ... Read(PCode,LongKonst); IF LongPos < MaxLong THEN LongPos := LongPos+1 ELSE (* Programm abbrechen: *) Error('longtable overflow'); LongTable[LongPos] := LongKonst; ... Die Erweiterungen in der zweiten Phase sind da schon etwas umfan- greicher. Hier werden ausschließlich die Implementierungen der neuen Operatoren (+,-,*,....) und Standardprozeduren (Read, Wri- te) aufgenommen. Die Interpretation von "rdl" und "wrl" findet dabei in den Prozeduren "ReadLong" und "WriteLong" statt, wohin- gegen die Operatoren +,-,*,.... in der Prozedur "NextCase" inter- pretiert werden und deren Implementierung wiederum so leicht ver- ständlich ist, daß der Programmtext für sich selbst spricht: PROCEDURE NextCase (Op: INTEGER); BEGIN CASE Op OF 62 : BEGIN (* ADL *) SP:=SP-1; STORE[SP].VL := STORE[SP].VL+STORE[SP+1].VL END; 63 : BEGIN (* SBL *) SP:=SP-1; STORE[SP].VL := STORE[SP].VL-STORE[SP+1].VL END; 64 : BEGIN (* DVL *) SP:=SP-1; STORE[SP].VL := STORE[SP].VL DIV STORE[SP+1].VL END; 65 : BEGIN (* MDL *) SP:=SP-1; STORE[SP].VL := STORE[SP].VL MOD STORE[SP+1].VL END; 68 : BEGIN (* MPL *) SP:=SP-1; STORE[SP].VL := STORE[SP].VL*STORE[SP+1].VL END; 66 : STORE[SP-1].VL:=STORE[SP-1].VI; (* ILO *) 67 : STORE[SP].VL:=STORE[SP].VI; (* ILT *) 69 : STORE[SP].VL:=-STORE[SP].VL; (* NGL *) 70 : STORE[SP-1].VR:=STORE[SP-1].VL; (* LFO *) 71 : STORE[SP].VR:=STORE[SP].VL; (* LFT *) ... END END; Mit diesen selbstgebastelten Erweiterungen ist unser PASCOMP- Compiler nun in der Lage, den Typ "LongInt" (hoffentlich) korrekt zu compilieren und zu interpretieren. Vielleicht hat ja jetzt der eine oder andere Leser Lust bekommen, selbst neue Typen, Prozedu- ren o.ä. in seinen eigenen Compiler einzubauen. Sicherlich wird das keine 5-Minuten-Arbeit sein, aber man wird nach gewisser Zeit feststellen, daß die ca. 100 Seiten Papier, die bei einem Aus- druck von Compiler- und Interpreter-Listing schon mal herauskom- men, doch ein relativ einfaches Konzept, das sich auf einige Sei- ten zusammenfassen läßt, aufweisen. Und demjenigen, der sich dann noch näher mit dem Compilerbau be- schäftigt, wird bald klar werden, daß die beschriebenen Verfahren und Techniken sich nicht nur auf den Compilerbau beschränken. So findet man zum Beispiel Scanner in fast allen Programmen, die etwas mit Eingabe von Informationen zu tun haben - meist mit an- derem Namen oder gar nicht als separaten Programmteil deklariert. Parser spielen eine große Rolle in der KI und in Information- Retrievel- Systemen. Alles in allem kann man die in diesem Pro- jekt dargestellten Verfahren als einen großen Werkzeugkasten für viele Bereiche der Informatik ansehen. Wie hoffen, daß dies mit dieser Serie verdeutlichen werden konnte. Mit dieser Folge sind wir nun am Ende der Serie angelangt. Es gäbe natürlich noch vieles zu berichten, vor allem, weil der Fortschritt im Bereich der Informatik so ungeheuer schnell voran- schreitet. Wir bedanken uns bei Ihnen, liebe Leser, daß Sie bis hierhin gefolgt sind und wünschen Ihnen noch viel Spaß mit dem Compiler.