Compilerbau

Ziel dieses Buches ist die Entwicklung einer einfachen, rudimentären Programmiersprache und eines zugehörigen Compilers. Dieses Compiler-Programm ist ein Muster-Beispiel für eine systematische Entwicklung eines gut strukturierten Programmes nicht-trivialer Komplexität Hauptsächlich aber soll dieses Kapitel als Einführung in die Technik des Compilerbaus dienen. Kenntnisse und Einblick in dieses Thema fördern ganz allgemein die Fähigkeiten des Programmierern in höheren Programmiersprachen. Ferner sind sie Grundlage und Vorbedingung für die Möglichkeit, eigene Eingabesprachen und Systeme für spezifische Zwecke zu konstruieren. Da der Compilerbau ein komplexes Thema mit vielen Aspekten ist, beschränken wir uns in dieser Hinsicht auf eine Einführung. Vielleicht die wichtigste Grundidee ist dabei die Erkenntnis, dass die grammatikalische Struktur einer Sprache sich in der Struktur des Compilers widerspiegeln muss. Daraus folgt unmittelbar, dass die Komplexität — oder besser die Einfachheit — einer Sprache das Mass für die Komplexität ihres Compilers darstellt Wir beginnen daher mit einer Behandlung von Sprachstrukturen und deren formeller Beschreibung im allgemeinen. Danach konzentrieren wir uns ausschliesslich auf einfache Strukturelemente, die ich durch einfache, effiziente und übersichtliche Compiler behandeln lassen.

Jeder Sprache liegt ein Vokabular zugrunde. Normalerweise bezeichnet man seine Elemente als Worte. Bei formalen Sprachen hingegen ist es üblich, sie Symbole oder Grundsymbole zu nennen. In jeder Sprache gibt es Folgen von diesen Symbolen, die als korrekt oder wohlgeformt, andere die als falsch oder missgebildet gelten. In erster Linie ist es die Grammatik oder Syntax, die bestimmt, zu welcher Kategorie eine Symbolfolge gehört Wir gehen hier sogar soweit, dass wir die Menge von Symbolfolgen, die von der Syntax als wohlgeformt definiert sind, als die Sprache selbst bezeichnen. Missgebildete Folgen gehören überhaupt nicht zur Sprache, auch wenn sie ausschliesslich aus Symbolen des zugehörigen Vokabulars aufgebaut sind.

Die Aufgabe eines Übersetzers oder Compilers ist normalerweise nicht die Erzeugung oder Herleitung, sondern die Erkennung eines Satzes und seiner Struktur. Dies bedeutet, dass die Schritte der Erzeugung beim Lesen eines Satzes als Schritte der Erkennung nachvollzogen werden müssen. Dies ist im allgemeinen eine komplizierte, und in vielen Fällen sogar eine unmögliche Aufgabe. Ihre Komplexität hängt unmittelbar von der Art der Produktionen ab, die die Syntax bestimmen. Zahlreiche Erkennungs-Algorithmen für verschiedene Klassen von Sprachen unterschiedlicher struktureller Komplexität sind bekannt Ihre Effektivität hängt direkt von ihrer Mächtigkeit ab: je allgemeiner sie verwendbar sind, umso weniger Effizienz kann erwartet werden. Unser Ziel hier ist jedoch lediglich die Entwicklung einer Methodik, relativ einfach Sprachen zu erkennen, dies jedoch mit einer Effizienz, wie sie von der Praxis gefordert wird. Die Zeit, die gebraucht wird, um einen Satz zu erkennen, darf demnach höchstens proportional zu seiner Länge anwachsen. Anstatt einen möglichst allgemeinen Erkennungs-Algorithmus, genannt Parser, zu finden, gehen wir in umgekehrter Richtung vor: Wir postulieren einen einfachen Algorithmus und bestimmen danach die Klasse der Sprachen, die er verarbeiten kann.

Die Darstellung einer Syntax in BNF ist nur eine von verschiedenen Möglichkeiten. Eine andere, in vieler Hinsicht vorteilhafte Art der Darstellung beruht auf der Verwendung von Diagrammen oder Graphen. Der Hauptvorteil beruht dabei auf der besseren Ueberschaubarkeit. Wir schlagen nachfolgend eine Art der Graphen vor, die den Ablauf einer Satzerkennung im top-down Verfahren unmittelbar veranschaulicht Wir geben ein einfaches Rezept, wie eine durch BNF definierte Syntax konsequent in entsprechende Graphen übersetzt werden kann. Der umgekehrte Vorgang ist natürlich ebenso leicht möglich. Wir nehmen an, dass die BNF bereits in dem Sinne normalisiert ist, dass jedes nicht-terminale Symbol durch eine einzige Produktionsfolge definiert ist. Die Uebersetzung ist dann durch nachfolgende Regeln bestimmt.

Falls eine Syntax durch einen deterministischen Graphen darstellbar ist, so lässt sich dieses Programm sehr systematisch aus dem Graphensystem herleiten. Die einzelnen Graphen entsprechen den zu erkennenden syntaktischen Kategorien und werden in einzelne Prozeduren abgebildet. Jeder Graph stellt sozusagen das Flussdiagramm der entsprechenden Prozedur dar. Die Übersetzung des Graphensystems in ein Programm lässt sich wiederum durch einzelne Regeln beschreiben, ganz analog zur Übertragung von BNF in graphische Form.

Im vorangehenden Kapitel wurde eine Methodik beschrieben, die es erlaubt, für irgend eine Syntax den zugehörigen Parser zu programmieren, sofern die Syntax den zwei einschränkenden Regeln genügt Da jedoch immer dasselbe Prinzip der Analyse verwendet wird, ist es auch möglich, ein einziges, allgemeines Programm zu erstellen, das für alle entsprechenden Sprachen geeignet ist Dieses allgemeine Programm wird je nach Sprache mit Tabellen versehen, welche deren Syntax in codierter Form darstellen. Der Parser wird dann sozusagen von diesen — während der Analyse unveränderten — Tabellen gesteuert Er verkörpert den Algorithmus, nach dem wir einen Satz erkennen, wenn wir anhand der Syntax-Graphen vorgehen.

Im Unterschied zu den vorangegangenen Beschreibungen von Darstellungs-Transformationen streben wir in diesem Kapitel nicht eine informelle Definition, sondern ein formales Programm an. Dieses Ziel erscheint nicht nur deshalb interessant, weil sich damit die Umformung durch Computer automatisch und fehlerfrei durchführen lässt, sondern ganz besonders weil dieses Transformations-Programm als unmittelbare Anwendung der in Kapitel 4 beschriebenen Technik erscheint.

Dieses und die folgenden Kapitel sind der Entwicklung einer elementaren Programmiersprache und ihres Compilers gewidmet Sie heisse PL/0. Einerseits ist es unumgänglich, diese Sprache und den Compiler einfach zu halten, damit sie in den Rahmen dieses Buches passen. Anderseits liegt der Wunsch nahe, die wichtigsten Grundprinzipien von Programmiersprachen und Compilations-Techniken darlegen zu können. Daraus ergeben sich bereits die Randbedingungen für die Art der zu wählenden Sprache PL/0. Ohne Zweifel könnte sie auch einfacher oder komplizierter Gewählt werden. PL/0 stellt lediglich einen der möglichen Kompromisse zwischen genügender Einfachheit für eine übersichtliche Darstellung und genügender Komplexität dar, die das ganze Projekt realistisch und lohnend macht.

In einem ersten Schritt soll ein Parser für PL/0 entwickelt werden, der alsdann nach der Methode des schrittweisen Ausbaus zu einem Compiler vervollständigt werden kann. Dieser erste Schritt kann strikte nach den angegebenen Regeln Bl bis B6 ausgeführt werden. Zuvor ist es aber nötig zu prüfen, ob die vorliegende Syntax den Regeln 1 und 2 aus Kapitel 2 genüge. Dies ist anhand der vorliegenden Graphen sehr leicht durchzuführen, sobald für jedes Diagramm (d.h. für jedes nicht-terminale Symbol) die Mengen der Anfangs- und der Folgesymbole ermittelt sind. Das Resultat dieser Ermittlung ist in folgender Tabelle festgehalten.

Bisher erfüllte der Parser nur die eher bescheidene Aufgabe zu bestimmen, ob eine Folge von Symbolen einen syntaktisch korrekten Satz darstelle. Fast als Nebenprodukt entdeckt dabei der Parser die Struktur des gelesenen Textes. Sobald jedoch ein inkorrektes Symbol vorliegt, ist des Parsers Aufgabe erfüllt, und der Vorgang der Satzzerlegung kann abgebrochen werden. Für praktische Zwecke ist dieses Vorgehen natürlich unzulässig. Vielmehr muss ein Compiler in dieser Lage eine entsprechende Fehleranzeige ausgeben und danach den Zerlegungsprozess fortsetzen. Dabei ist es sogar wahrscheinlich, dass weitere Fehler entdeckt werden. Eine Fortsetzung des Prozesses ist aber nur möglich, wenn gewisse Annahmen oder Hypothesen über die Art des Fehlers gemacht werden. Je nach dieser Annahme muss ein gewisser Teil des Textes übersprungen oder eingefügt werden. Solche Annahmen sind notwendig, selbst wenn gar nie die Absicht gehegt wird, das fehlerhafte Programm zu korrigieren und dennoch auszuführen. Ohne eine einigermassen zutreffende Hypothese ist eine Fortsetzung der Satzzerlegung schlechthin unmöglich.

Es ist in der Tat bemerkenswert, dass ein PL/0 Compiler bis hierher ohne Kenntnis des Computers entwickelt wurde, für den er Programme übersetzen soll. Aber aus welchem Grunde sollte die Struktur der Zielmaschine die Strategie der syntaktischen Analyse und der Fehlerbehandlung beeinflussen? Ganz im Gegenteil muss eine solche Beeinflussung sogar vermieden werden. Anstatt dessen wird eine geeignete Art der Code Generierung für einen beliebigen Computer nach dem Prinzip des schrittweisen Ausbaus auf das bestehende Gerüst des Compilers superponiert. Bevor wir diesen Schritt in Angriff nehmen können, ist es allerdings nötig, dass wir uns auf eine Zielmaschine und damit eine Zielsprache der Übersetzung festlegen.

Analog zur Eingabe des Quelltextes, wo die Umwandlung von Zeichen zu Symbolen von einem Scanner übernommen wird, kann bei der Ausgabe des Zielcodes die administrative Aufgabe der Abspeicherung von einem Generator übernommen werden. Dieser wird zweckmässigerweise wiederum als separater Modul formuliert (siehe Programm 7) und bezieht sich auf das durch den Interpreter definierte Befehlsformat Er stellt eine Prozedur Gen(f,1,a) zur Verfügung und reiht den durch die Parameter bestimmten Befehl der bereits gespeicherten Befehlsfolge an.

Programme ganz allgemein sind Beschreibungen von Automaten, die sich strikte nach einer vorgeschriebenen Regel verhalten. Wir betrachten den Computer als Werkzeug, das sich je nach Programm in einen anderen Automaten verwandeln lässt. Im Lichte dieser Betrachtungsweise erscheint das Programmieren als ein Konstruieren von Maschinen aus Bauteilen, die die verwendete Programmiersprache zur Verfügung stellt Nun ist es in keinem anderen Zweig des Ingenieurwesens derart leicht, einmal konstruierte Maschinen abzuändern, zu erweitern, veränderten Bedürfnissen anzupassen. Dies hat zur Folge, dass sich der Programmierer wie kaum ein anderer Ingenieur auf die leichte, scheinbar kostenlose Wandelbarkeit seiner Produkte verlässt So gibt es in der Praxis denn auch eher selten programmierte Systeme, die je den Zustand der Endgültigkeit erreichen. Besonders bei der Konstruktion komplexer Systeme ist es daher wichtig, sie so zu planen, dass ein Ausbau in verschiedenster Art möglich ist Besondere Aufmerksamkeit ist dabei der Modularisierung, d.h. der Aufteilung in einzelne Module zu schenken. Ist eine Grundstruktur glücklich gewählt, so lassen sich Änderungen auf wenige Orte lokalisieren, was für die Übersichtlichkeit und Zuverlässigkeit enorm wichtig ist.

In den vorangehenden Kapiteln wurde ein PL/0 Compiler entwickelt und programmiert. Daraus wird ersichtlich, dass ein Compiler im allgemeinen ein komplexes Programm ist, und dass deshalb die Verwendung einer höheren Programmiersprache zur Implementierung besonders zu empfehlen ist. Selbstverständlich gelten auch die Regeln und Praktiken der systematischen Programmentwicklung genau wie für jeden anderen komplizierten Algorithmus. Es gibt aber doch einige Punkte, die für Compiler spezifisch sind und deshalb hier noch erwähnt werden sollen. Insbesondere beziehen sich diese auf den relativ häufigen Fall der Erweiterung. Da ein Compiler, ja selbst eine Programmiersprache selten von Anfang an in endgültiger Fassung in Angriff genommen wird, wird vielmehr ein Kern der Sprache implementiert, worauf das Endziel schrittweise angenähert wird. Auf diese Technik soll nachfolgend näher eingegangen werden, doch führen wir vorerst noch eine Notation zur Darstellung von Programmentwicklungen ein. Das Bild soll andeuten, dass Eingabedaten E mittels eines Programms P, formuliert in der Sprache M und daher interpretierbar durch einen Computer M, in Ausgabedaten A verwandelt werden. Handelt es sich beim Programm P um einen Compiler, der Sätze aus der Sprache Sl in die Sprache S2 übersetzt, so wird dieser Compiler, der selbst in der Sprache M formuliert ist, durch die Figur dargestellt.