Turbo Toolbox

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

/ Turbo Toolbox / Turbo_Toolbox.iso / spezial / 02 / texte / pascomp.1 < prev next >

Wrap

Text File | 1988-09-19 | 43.6 KB | 1,008 lines

PASCOMP PASCAL baut einen Pascal-Compiler Teil 2: Einführung und Grundlagen zum Compilerbau von Johannes Velmans Nach dem in der letzten Ausgabe unser Pascal-Compiler PASCOMP sowie der 'Schlachtplan' zu dieser Serie vorgestellt wurde, soll sich nun dieses Kapitel mit einer Einführung 'Rund um den Compilerbau' befassen. Sind erst einmal die Grundlagen des Compilerbaus vermittelt - das Drumherum, das Wie, Warum und Wieso geklärt, kann es mit vollem Elan an's 'Eingemachte' gehen. Nun gut. Was ein Compiler (zu deutsch: Übersetzer) ist, dürfte eigentlich jeder unserer Leser im Prinzip wissen - es sei hier deshalb auch nur der Vollständigkeit halber noch einmal erwähnt: Ein Compiler ist ein Werkzeug, mit dessen Hilfe Sätze einer Quellsprache (Programmiersprache mit im allgemeinen für uns Menschen einigermaßen verständlichen Formulierungen) in gleichbeutende Sätze einer Zielsprache (im allgemein die Maschin ensprache eines Computers) transformiert werden können. Die Zielsprache muß dabei allerdings nicht unbedingt die Befehlssprache einer solchen, real existierenten Maschine sein. Wird nämlich die Quellsprache auf eine theoretische Zwischensprache einer abstrakten Maschine als Zielsprache abgebildet, so benötigt man zur 'Abarbeitung' dieser Zwischensprache einen Interpreter, der die Implementierung dieser abstrakten Maschine auf dem wirklich vorhandenen Computer darstellt und das Zwischensprachenprogramm anweisungsweise ausführt. Ein Beispiel hierfür ist das UCSD-PASCAL, welches auf einen P-Code (Pseudo-Code) hin compiliert, der dann zur Programmausführung einen Interpreter für diesen P-Code benötigt. Diesem Prinzip wird auch PASCOMP folgen, wodurch er auf eine Vielzahl von Maschinen leicht implementiert werden kann. Noch eine Anmerkung zur generellen Implementierung von modernen Programmiersprachen: Compiler werden heutzutage nicht mehr in Ma- schinensprache (man erinnere sich an FORTRAN-Zeiten), sondern sehr oft in höheren Programmiersprachen ausgeführt. Dabei werden schon bestehende Programmiersprachen zum 'Bau' eines minimalen 'Kerns' der neuen Sprache verwendet, so daß aufbauend auf diesen Kern der vollständige Sprachumfang mit all seinen Besonderheiten und Raffinessen in der neuen Sprache selbst implementiert werden kann. Diese Vorgehensweise hat, wie alles in der Informatik, auch eine entsprechende englische Bezeichnung: 'Bootstrapping' - oder frei übersetzt: die Sprache zieht sich á la Münchhausen am eige- nen Schopf aus dem Sumpf. Für dieses Verfahren gibt es auch eine besondere Darstellungsweise, welche diese Technik kurz und präg- nant veranschaulicht: die T-Diagramme (Abb. 1). ┌─────────┐ │ Q Z │ └──┐ ┌──┘ │ │ │ i │ └───┘ Das T-Symbol hat dabei die folgende Bedeutung: Eine Quellsprache Q wird von einem Compiler, der selbst in der Sprache I implementiert ist, in die Zielsprache Z überführt. Wenn man nun einen Compiler für eine Sprache Q in der Sprache Y der Z ielmaschine implementieren möchte, so geschieht dies ziemlich einfach mit Hilfe eines schon bestehenden Compilers für beispielsweise eine Quellsprache H. Es braucht also nicht mehr der gesamte Compiler von Hand in der Zielsprache - das kann im Extremfall Maschinensprache sein - geschrieben werden. Die T- Diagramme in der Abbildung 2 verdeutlichen diese Vorgehensweise. Compiler - Implementierung ┌─────────┐ ┌─────────┐ ┌─────────┐ │H Y│ │Q Y│ │Q Y│ └──┐ ┌──┘ └──┐ ┌──┘ └──┐ ┌──┘ │ │ │ │ │ │┌─────────┐ │ Y │ │ H │ │ H ││H Y│ └───┘ └───┘ └───┘└──┐ ┌──┘ │ │ existiert herstellen │ Y │ └───┘ ┌─────────┐ │Q Y│ └──┐ ┌──┘ ========> │ │ │ Y │ └───┘ Unabhängig von der gewählten Programmiersprache zur Implementie- rung des Compilers haben sich im Laufe der Zeit immer stärker zwei für die Programmentwicklung wichtige Kriterien herauskri- stallisiert: Zum einen sollte sich die grammatikalisch e Struktur einer Pro- grammiersprache in der Struktur ihres Compilers widerspiegeln - und zum anderen die Tatsache, daß eine komplizierte Programmier- sprache einen komplizierten Compiler mit sich bringt (nach N.Wirth). Gerade letzteres wird se hr deutlich, wenn man Imple- mentierungen von PASCAL mit denen von ADA vergleicht. PASCAL- Implementierungen kommen im Durchschnitt auf 3000-5000 Zeilen Programmtext, eine ADA-Implementierung benötigt dagegen ein Viel- faches davon. Der Untersc hied ist auch anhand der Größe der je- weiligen Systeme zu sehen: Pascal gibt es mittlerweile fast auf jedem auch noch so kleinen Heim-Computer, ADA ist dagegen erst auf den neuen 16/32-Bit- Rechnern mit entsprechender Speicherka- pazität einsetzbar. Vorzüge und Nachteile der Übersetzung bzw. Interpretation Was ist denn da nun besser? Compiler oder Interpreter? Gibt es überhaupt einen Favoriten? Am besten kann man diese tiefgreifende Frage mit der Antwort eines Schülers während einer Abiturprüfung beantworten: 'Das kommt ganz darauf an'. Nun, einen generellen Vorteil des Compilers gegenüber dem Interpreter gibt es nicht: Beide können in Abhängigkeit der jeweiligen spezifizierten Fragestellung die besseren Lösungen bieten. Mit solchen Fragen schlagen wir uns aber nicht herum, sondern verweisen nur kurz auf einige Vor- und Nachteile: Die Nachteile der Interpretation klar. Die längere Ausführungszeit lassen die Benutzer von rechenintensiven Programmen meist lieber auf einen Compiler umsteigen, da für sie nur die schnelle Ausführung eines Programmes zählt. Außerdem sind ie Programmentwicklungszeiten für solche Mathe-Programme meist so klein, daß sich auch in der Entwicklungsphase keine gravierenden Unterschiede in der Verwendung von Compilern und Interpretern ergeben. Der Grund für die geringere Ausführungsgeschwindigkeit eines Interpreters ist einleuchtend: Er übersetzt bzw. interpretiert ein Programm stückchenweise - Anweisung für Anweisung wird analysiert und ausgeführt. Gerade darin liegt aber auch schon eine der Stärken des Interpre- ters: Er bietet ein höheres Maß an Flexibilität gegenüber über- setzten Sprachen - Programmteile können schnell getestet, geän- dert und schrittweise ausgeführt werden. Da sind außerdem die größere Absturzsicherheit des Systems sowie die einfache Imple- mentierung von Post-Mortem-Dumps (PMD) bei Programm-Fehlern zur Fehlererkennung und -behebung zu nennen. Ein einfaches schritt- weises Ausführen und verfolgen eines Programms auf der Ebene der Quellsprache ist bei compilierten Sprachen in dieser Form derart einfach nicht möglich. Noch eines zur langsameren Ausführungsgeschwindigkeit: Sie wird nicht nur durch den relativ langsamen Vorgang des schrittweisen interpretierens hervorgerufen, sondern auch durch einen Umstand, der am besten durch ein Beispiel verdeutlicht wird. Gegeben seien folgende PASCAL-Stücke: var x : array(1..1000)of t y : t; BEGIN .... x[5] := y; .... END. Die Zuweisung des Wertes der Variablen y an das fünfte Element des Feldes x erzwingt generell eine Grenzbereichsüberprüfung durch einen Interpreter. Ein halbwegs intelligenter Compiler wür- de bei dieser Zuweisung aber schon während der Übersetzungszeit feststellen, daß eine solche Prüfung während der Programmausfüh- rung überflüssig ist: Zur Indizierung wird eine Konstante und keine Variable verwendet - und der Wert dieser Konstanten liegt im definierten Bereich des Feldes. Ein Interpreter kann dieses nicht erkennen und müßte bei jeder Indizierung eines Feldes mit oder ohne Konstante eine 'Laufzeitüberprüfung' durchführen. Ein erheblicher Zeitverlust tritt natürlich auf, wenn die obige Zu- weisung noch zusätzlich in einer Schleife liegen würde. Bei all den Nachteilen eines Interpreters darf man aber nicht vergessen, daß er in der Regel den Quelltext sofort ausführt und somit die langen Übersetzungszeiten eines Compilers wegfallen. In der Tat ist dies in der Test- und Entwicklungsphase eines Programms von großer Bedeutung. Profitieren doch gerade hier die Anwender des Interpreters von den Möglichkeiten der Trace- und Debug-Optionen. Daher wird oftmals ein Programm quasi 'interaktiv' implementiert, getestet und nach erfolgreichem Abschluß mit einem Compiler auf Geschwindigkeit optimiert. Dies wird in den Ohren unzähliger Turbo-Pascal-Programmierer befremdend klingen, da hier die Entwicklungszeit mit einem Compiler wohl schneller vonstatten geht als mit manchem Interpreter, doch ist die Programmiersprache Pascal nicht das 'non plus ultra' für jedes Implementierungsproblem. Schließlich gibt es ja auch noch andere Sprachen als Pascal. Man denke da beispielsweise an die funktionalen Programmiersprachen, deren lange Reihe von LISP angeführt wird. Zu PROLOG-losen Zeiten waren LISP-Interpreter die Sprache für die Entwickler von KI- Programmen (Expertensysteme, automatische Beweiser, ....). LISP hat ein weit über Pascal hinausgehendes, sehr mächtiges Konzept - nämlich Funktionen als Ergebnisse von Funktionsaufrufen zu über- geben. In der KI verdrängte LISP imperative Programmiersprachen wie Pascal für derartige Problemstellungen von der Liste der mög- lichen Implementierungssprachen. Es ist bekannt, daß auch LISP mittlerweile erfolgreich übersetzt wurde und kommerziell zu be- ziehen ist, so daß auch hier nach dem Motto 'Entwickeln mit In- terpreter, compiliert anwenden' verfahren werden kann. PROLOG wurde bereits erwähnt. Diese Sprache gehört zu den objektorientierten Programmiersprachen. Die Sprache ist dabei, die Stellung von LISP in der KI zu übernehmen. Obwohl PROLOG für Informatikverhältnisse relativ alt ist (LISP übrigens auch), hat die Sprache die Stellung, die ihr in der Programmiersprachenwelt eigentlich gebührt, noch nicht erreicht. Gründe dafür gibt's vie- le. Compiler gibt es für PROLOG zwar schon, aber nur mit großen Einschränkungen. Den mit Turbo-PROLOG übersetzten Programmen fehlt beispielsweise die Eigenschaft, sich während der Laufzeit zu verändern - was für einen Interpreter eine der leichtesten Übungen ist. Das heißt, es können keine neuen Regeln und Fakten zur bestehenden Regelmenge hinzugefügt werden. Damit hat man aber auf eines der mächtigsten Konzepte von PROLOG verzichten müssen. Für vollständiges PROLOG bleibt bis jetzt also nur der Interpre- ter. An diesem Beispiel sieht man deutlich, daß Interpreter nicht unbedingt ein Stiefkind der Sprachenimplementierung sind, sondern auch eine echte Alternative zum Compiler darstellen können. Aufbau eines Compilers ┌────────────────┐ (Programmtext) │ Symbol │ ──────┬─────── ┌─> │ ├─>─────────────┐ │ │ │ Tabelle │ │ │ │ └────────────────┘ │ │ │ │ │ │ │ │ │ │ │ │ │ ┌──────────────┐ │ ┌────────────────┐ ┌─────────┐ │ lexikalische │ │ │ syntaktische │ │ seman- │ │ ├────┴─> │ ├────────> │ tische │ │ Analyse │ │ Analyse │ │ Analyse │ └──────────────┘ └────────────────┘ └─────────┘ │ │ │ ┌───────────┐ │ Code- │ │ │ │ erzeugung │ └───────────┘ 1. Der Scanner Der Scanner stellt die erste Verarbeitungsphase in der Compilie- rung eines Quellprogramms dar. Kurze Anmerkung: Eine Phase (engl. Pass) ist ein gesamter Zyklus in der Verarbeitung einer Datei, der Eingabe, Verarbeitung und Ausgabe beinhaltet. Die Aufgabe des Scanners besteht darin, die Grundsymbole des Programms - das sind Bezeichner (von Variablen, Prozeduren etc.), Literale (Zeichen- ketten wie z.B. 'Was nun ?'), Schlüsselwörter (z.B. BEGIN, END usw.) und Separatoren (Semikolon, Leerzeichen...) zu erkennen und auf eine Symbolfolge (Tokenfolge) abzubilden. Dabei wird außerdem noch analysiert, ob der Quelltext lexikalisch korrekt ist, d.h. entsprechen die unterschiedlichen Bestandteile einer Programman- weisung der Sprachdefinition und sindkeine undefinierten Zeichen enthalten. Durch die Abbildung von ganzen Wörtern auf ein Symbol wird erheblich Speicherplatz gespart und die Zugriffszeit auf ein beliebiges Symbol des Quelltextes im Verlauf der weiteren Übersetzungsschritte deutlich verkürzt. Ein weiterer Vorteil dieser Vorgehensweise ist, daß für die Übersetzung nicht relevan- te Zeichenfolgen (Kommentare, Leerzeichen) eliminiert werden kön- nen. Nach der Scanner-Phase ist der Quelltext für die weitere Übersetzung dann nicht mehr notwendig, da sämtliche weiteren Ope- rationen auf die vom Scanner hergestellte Symbolfolge angewendet werden. Eine Ausnahme bilden hier protokollierte Fehlerausgaben mit Quelltext-Listings. Oft wird die Frage gestellt, ob es überhaupt lohnenswert ist, die lexikalische Analyse separat zu betrachten. Warum wird sie nicht direkt mit in die syntaktische Analyse (s. Parser) aufgenommen? Die Antwort ist relativ einfach: Die Trennung dieser beiden Verarbeitungschritte erlaubt eine Optimierung bezüglich der je- weiligen Aufgabenstellung, so daß insgesamt eine Zweiteilung des Problems den Compiler schneller macht als eine Vermischung der beiden Aufgaben. Denn: Die lexikalische Analyse ist in der Lage, effizientere Er- kennungsstrategien (z.B. Erkennung von längsten Mustern) durchzu- führen als die Syntaxanalyse. Außerdem arbeitet die Syntaxanalyse dann auf einer Symbolfolge, die keine Kommentare oder Separatoren mehr enthält, wodurch der Leseprozeß der vom Scanner erzeugten 'Token'-Datei beschleunigt und der Speicherplatzbedarf gering gehalten wird. Im Übrigen gilt auch hier die Devise, daß ein stark modularisiertes Programm die Lesbarkeit und spätere Wart- barkeit des Programms sehr fördert. Die Trennung in diese beiden Verarbeitungsphasen im Sinne von Datei lesen, verarbeiten und Ergebnis ausgeben ist aber nicht unbedingt notwendig. Eine Modularisierung muß nämlich nicht unbedingt einen Mehrphasen-Algorithmus zur Folge haben. In vielen Compilerimplementierungen ist es so, daß die Syntaxanalyse die gesamte Übersetzung steuert und nach Bedarf jeweils die lexikali- sche Analyse 'anstößt' - und das alles in einer Phase der Über- setzung. Dies trifft auch für PASCOMP zu. Für diejenigen, die sich schon damit auskennen: in ihm ist ein 'recursiv descent Parser' (LL(1)) implementiert, der als Steueralgorithmus für die einzelnen Verar- beitungsschritte durch den Aufruf der dazugehörigen Prozeduren zuständig ist. Der Parser (Zerteiler) Wie die Syntax einer lebendigen Sprache (z.B. Englisch) wird auch die Syntax einer Programmiersprache (in unserem Fall Pascal) durch eine Grammatik spezifiziert. Der Parser hat nun die Synta- xanalyse zur Aufgabe: Ist der eingegebene Satz (in unserem Fall der Quelltext) aus dieser Grammatik ableitbar?. Er muß sich also anhand des Satzes durch die Grammatikregeln wühlen und entschei- den, ob eine Folge von Regeln existiert, die diesen Satz erzeu- gen. Ein Beispiel für einen (un)typi schen Syntaxfehler in PASCAL wäre etwa: ... VAR a : ARRAY (1..10) OF INTEGER; î syntax error ('['expected) ... Schaut man sich diezugehörige Grammatikregel im User-Manual & Report an, so steht da: <array type> ::= ARRAY [ <indextype> { , <indextype> } ] OF <com- ponent type>. Das heißt also, daß dem ARRAY-Symbol ein [-Symbol folgen muß, wenn der obigen Grammatikregel entsprochen werden soll. Eine run- de Klammer führt hier somit zum Syntaxfehler. Mehr zu den Grundlagen von Grammatiken gibt es etwas später im Abschnitt 'Elemente formaler Systeme'. Bleibt noch zu berichten, was denn nun eigentlich das Ergebnis der Parser-Arbeit ist. Nun, es ist im Grunde genommen ganz ein- fach. Wurde für einen Satz eine Ableitung gefunden, so gibt der Parser diese in der Form eines Baumes für den nächsten Verarbei- tungsschritt aus. Diese Ausgabe kann eine Folge von Regelnummern sein, wobei jede Grammatikregel genau eine Regelnummer erhält. Es kann aber auch der gesamte Ableitungsbaum mit seinen Symbolen sein. Man beschränkt sich dabei allerdings nur noch auf die relevanten Symbole und Informationen, die für die weiteren Verarbeitungs- schritte im Compiler benötigt werden. Symbole wie :=, [, ], etc. werden dann nämlich nicht mehr benötigt und einfach aus dem Ab- leitungsbaum gestrichen. So ein gestutzter Baum wird auch als Strukturbaum bezeichnet und hat gegenüber dem Ableitungsbaum den Vorteil, daß er nur noch semantisch wichtige Informationen ent- hält und somit redundante (mehrfach vorhandene , gleiche) Symbo- le bei der weiteren Verarbeitung nicht mehr berücksichtigt werden müssen. Dieser Strukturbaum repräsentiert nun natürlich nicht mehr eine korrekte Ableitung gemäß der in der Sprachgrammatik definierten Syntax. Die Syntax, die dem Strukturbaum an dieser Stelle der Übersetzung zu Grunde liegt, ist eine abgemagerte Form der konkreten Syntax. Sie wird mit 'abstrakter Syntax' bezeich- net. Zur Erläuterung der abstrakten Syntax sei die Pascal-Gramma- tikregel für die CASE-Anweisung gewählt. Konkrete Syntax : <case statement> ::= CASE <expression> OF <case list element> { ; <case list element> } END. abstrakte Syntax : ,,l <case statement> ::= <expression> <caselist element> { <ca se list element> }. Die Symbole CASE, OF und ; sind nach der Syntaxanalyse nicht mehr relevant und treten daher auch nicht mehr in der abstrakten Syn- tax auf. Wenn das Quellprogramm die Übersetzung bis zu diesem Punkt ohne Fehlermeldungen überstanden haben sollte, dann geht's nun in die letzte Phase der Analyse. Semantische Analyse Die Aufgabe der semantischen Analyse besteht in der Überprüfung der statischen Semantik von Programmen. Auch hier soll die Pro- blemstellung durch ein Beispiel in einem Pascalprogramm verdeut- licht werden. Gegeben sei das folgende lexikalisch und syntak- tisch korrekte PASCAL-Programm: PROGRAM demo; VAR a : ARRAY [Real] OF Integer; BEGIN a[1.23] := 0; END. Laut den Grammatikregeln ist syntaktisch zwar alles korrekt, aber die Indizierung eines Feldes mit Realzahlen ist dennoch nicht möglich. Ein weiterer Blick in das User-Manual & Report schafft da sofort Klarheit. Dort steht nämlich: TYPE A = ARRAY [T1] OF T2; ...... and T1 is a scalar or subrange type (where type integer and real are not allowable index type).... Alles klar? Neben solchen Kleinigkeiten wird in der semantischen Analyse auch die Gültigkeit von Definitionen und Typregeln ge- prüft. Man kennt's: Typ A ist kompatibel zu Typ B genau dann, wenn... usw. Neben der statischen Semantik, die während der Über- setzungszeit geprüft werden kann, gibt es noch die dynamische Semantik, deren Überprüfung während der Laufzeit stattfinden muß. Hier ist es die Aufgabe der Codeerzeugung, entsprechende Codese- quenzen für die Prüfungen während der Programmausführung bereit- zustellen. Beispiele für dynamische Semantik sind: (i) x(k) Liegt der Wert innerhalb der vereinbarten Indexgrenzen des Arrays x ? (ii) x/y: Ist der Wert von y gleich 0 ? (iii) VAR y : INTEGER; x: 1..100; x := y: Liegt der Wert von y innerhalb des für x festgelegten Bereichs? Prinzipiell geschieht in der semantischen Analyse folgendes: Der vom Parser übergebene Strukturbaum wird mit einer Reihe von At- tributen 'geschmückt'. Das können Typattribute, Grenzwerte für Ausschnittstypen usw. sein. Mit diesem attributierten Struktur- baum und unter Zuhilfenahme von verschiedenen Tabellen, die in früheren Schritten der Übersetzung angelegt wurden (Konstantenta- belle, Symboltabelle usw.), ist die Codeerzeugung in der Lage, Code für die Zwischensprache herzustellen. Codeerzeugung Als Schnittstelle zwischen der semantischen Analyse und der Code- Erzeugung steht der sogenannte Berechnungsgraph, der aus dem at- tributierten Strukturbaum hergestellt wird, indem die Struktur dieses Baumes vereinfacht wird. Dies geschieht z.B. durch Weglas- sen von deklarativen Teilen des Strukturbaumes. Deklarationen von Variablen tragen ja nicht direkt zur Codeerzeugung bei. Durch das Hinzufügen der Ausführungsreihenfolge (z.B. von geklammerten Aus- drücken) entsteht so aus dem attributierten Strukturbaum ein Be- rechnungsgraph, aus dem dann der Maschinencode für die reale Ma- schine gewonnen werden kann. Wie anfangs schon erwähnt, erzeugt PASCOMP einen Zwischencode (P- Code), der später von einem Interpreter ausgeführt werden soll. Wie diese virtuelle P-Code-Maschine im Gegensatz zu den realen Maschinen funktioniert wird natürlich noch deutl ich ausgeführt. Soviel vorweg: Sie besitzt keine ('Prozessor'-)Register und führt sämtliche Operationen auf dem Laufzeitkeller (Stack, Stapel) aus. Ansonsten arbeitet die P-Code-Maschine vergleichbar mit einer realen Maschine. Bevor jedoch der Maschinencode erzeugt wird, ist es zweckmäßig, sich die Eigenschaften der realen Maschine vor Augen zu führen (Maschinenbefehle, Register, Adressierungsarten, Speicherklassen usw.). In den meisten Fällen reicht es aus, wenn nur ein Teil der zu Verfügung stehenden Maschinen-Befehle Verwendung finden. Dazu wird meist ein Dokument erstellt, das die Abbildung der Sprache L (Zwischensprache aus dem Berechnungsgraphen) auf die Maschine M spezifiziert. In diesem Dokument sollten folgende Punkte beachtet werden: 1. Die Eigenschaften der realen Maschine M: - Speicherklassen - Adressierungsarten - Maschinenbefehle 2. Speicherabbildungen: Wiewerden Standardtypen (INTEGER, REAL, BOOLEAN etc.) abgebil- det? 3. Maschinenzustände, Register und Speicherverwendung: - Codespeicher - globale Daten - Laufzeitkeller - Halde (Heap) - Vorbelegung von Registern (Keller- pegel, aktuelle Laufzeit- schachtel, Adresse des Displayvektors, ... ) Wer sich von den einzelnen Fachbegriffen überrumpelt fühlt, braucht keine Sorge zu haben - in den entsprechenden Kapiteln wird noch näher auf diese Begriffe eingegangen. Elemente Formaler Systeme Die Überschrift dieses Abschnitts deutet es schon an: jetzt kommt ein bißchen Theorie. Wer bis hierhin durchgehalten hat, sollte unbedingt weiterlesen, da die folgenden theoretischen Grundlagen unentbehrlich für das Verständnis der weiteren Folgen sind. Außerdem: Ein wenig Theorie am Anfang erspart später mühevolles Ausprobieren und Neuentwickeln. Denn wem ist es nicht schon so ergangen, daß er tagelang ein Problem in den Griff zu bekommen suchte, dessen Lösung schon seit Jahren in der obersten Ecke des Bücherregals verstaubte. Ein kleines bißchen Vorbereitung hilft da schon enorm... Den Anfang unserer Theoriestunde soll der Begriff des 'endlichen Automaten' machen. Endlicher Automat? Jeder, der sich intensiver mit der Computerei beschäftigt, hat diesen Begriff sicherlich schon einmal gehört. Für diejenigen, die nichts damit anfangen können, sei er hier kurz erklärt: Man kann sich einen endlichen Automaten als eine Maschine vor- stellen, die bei einem gegebenem Eingabestring jedesmal genau ein Zeichen aus dem Eingabepuffer in ihr 'endliches Gedächtnis' liest und - abhängig vom jeweiligen internen Zustand und dem eingelese- nen Zeichen - ihren Zustand verändert (s.Abb.4). endlicher Automat ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬──────────────┐ │ x │ y │ z │ y │ y │ z │...│...│...│...│ ............ │ └─┬─┴─┬─┴───┴───┴───┴───┴───┴───┴───┴───┴──────────────┘ │ Eingabestring │ │ │ │ │ │ │ │ ┌─────────────────┬─────────> neuer interner │ ┌──────┴─────────┐┌──────┴───────┐ Zustand │ └> │ endliches ││ Interner │ └────> │ ││ │ │ Gedächtnis ││ Zustand │ └────────────────┘└──────────────┘ Wenn mit dem Paar (interner Zustand, gelesenes Zeichen) ein neuer interner Zustand bestimmt wurde, so wird der Zeiger auf den Ein- gabepuffer genau um eine Position weiter gesetzt, so daß dieser Zeiger auf das nächste Element der Eingabe verweist. Wer die Informatik ein wenig kennt, weiß, daß das hier in Worten dargestellte Modell des endlichen Automaten nicht nur sehr schön, sondern vor allen Dingen auch kurz in formaler Art und Weise be- schrieben werden kann: Ein endlicher Automat A, auch Akzeptor genannt, ist als ein 5-Tu- pel wie folgt definiert: A = (T,Q,R,q[0],F) Dabei haben T, Q, R, q[0], n und F folgende Bedeutung: - T ist ein festes, aber beliebiges Alphabet. Es darf nur endlich viele Element enthalten und kann nicht leer sein. Ein Alphabet kann zum Beispiel der Zeichensatz einer Maschine, die Grundsymbo- le einer Programmiersprache, syntaktische Begriffe usw. sein. Fügt man eine endliche Anzahl von Zeichen aus T zusammen, so er- hält man eine Zeichenreihe (String) über T. Die Menge, die alle diese Zeichenreihen enthält, wird mit T,,h+,,n bezeichnet und ist formal definiert durch : T+ := {x[t1]...x[n] |n>= 1; x[i] aus T} Die leere Zeichenreihe wird mit e bezeichnet und T* := {x[1]...x[n]| n >= 0; x[i] aus T} = T+ U {e} Die Länge einer Zeichenreihe x[1]...x[n] wird mit |x| = n no- tiert. Spezialfall |e| = 0. - Q Ist eine endliche Menge von internen Zuständen des endlichen Automaten, deren Elemente im Folgenden immer mit q[i],i >= 0, bezeichnet werden. Interne Zustände werden im weiteren Verlauf zur Vereinfachung auch 'Zustände' genannt. Befindet sich der endliche Automat im Zustand q[i] aus Q und ist die noch nicht abgearbeitete Zeichenfolge y[1]...y[n] =: y, y[i] aus T, so schreibt man dies auch als q[i]y. - R ist eine endliche Regelmenge. Sie gibt an, auf welchen neuen Zustand das Paar aus Eingabezeichen und aktuellen interen Zustand abgebildet wird. Wenn der endlicher Automat zum Beispiel im Zu- stand q[1], das gelesene Zeichen ein 'x' ist und das Paar (q[1]x) auf q[4] abgebildet wird, so schreibt man dies als: q[1]x -> q[4] Das heißt: Ein Automat A geht genau dann von Zustand q[i] in den Zustand q[j] über (bei Eingabe x, q[i] -> q[j], wenn x = ty (t aus T) und q[i]t -> q[j] ein Element der Regelmenge R ist. Zur besseren Übersicht wird diese Regelmenge im allgemeinen in Ta- bellenform dargestellt (Beispiel siehe weiter unten). - q[0] ist der Anfangszustand des Automaten. Darin befindet sich der Automat, bevor er das erste Zeichen gelesen hat. Man kann auch an dieser Stelle mehrere Anfangszustände zulassen, aber es soll ja nicht noch schwerer werden .... - F ist eine echte Teilmenge von Q. Sie enthält die Endzustände des endlichen Automaten. Wenn es bei einer Eingabe x = x[1]...x[n], x[i] aus T vorkommt, daß sie Schritt für Schritt abgearbeitet wurde (d.h. bis kein neues Zeichen mehr in das end- liche Gedächtnis des Automaten übernommen werden kann), und der aktuelle interne Zustand q[j] auch in F liegt, so sagt man, der Automat A akzeptiert das Eingabewort x (Daher auch die Bezeich- nung Akzeptor anstelle von endl icher Automat). Alle von einem Automaten akzepierten Wörter werden zur Sprache L(A) (L = Langua- ge) zusammengefaßt. Formal schreibt man dies so: L(A):= {x aus T* | q[0]x ->*q[j], q[j] aus F} Der * über dem ->-Symbol soll andeuten, daß der Übergang in end- lich vielen Schritten stattfinden muß (es muß nicht unbedingt nur ein Übergang sein ). So, dies war nun eine ganze Menge Theorie - es wird Zeit für ein paar Beispiele.... Diejenigen, die schon einmal etwas von endlichen Automaten gehört haben, werden sich sicherlich in diesem Zusammenhang an das Bei- spiel des Zigarettenautomaten erinnern (es seien hiermit auch die Raucher unter den Lesern begrüßt!). Bei den n achfolgenden Über- legungen wird davon ausgegangen, daß beim Erscheinen dieses Arti- kels eine Packung Zigaretten immer noch 4,- DM kosten wird (für etwaige Preissteigerungen übernehmen wir keine Haftung!). Also - Sie stehen vor so einem Zigarettenautomaten mit einer Handvoll des nötigen Kleingeldes und wollen diesem Gerät die er- sehnten Glimmstengel abgewinnen. Vorausgesetzt, daß es sich um ein funktionstüchtiges Gerät handelt, welches nicht die eingewor- fenen Münzen ohne Gegenleistung trotz lautstarken Beschwörungen und massiven Androhungen in seinem Geldschlund verschwinden läßt, widerfährt Ihnen doch als ungeduldiger Raucher im Normalfall fol- gendes: Sie geben dem Automaten 4 deutsche Mark, er Ihnen die Zigaretten. Die Reihenfolge, in der 1,- DM oder 2,- DM Stücke eingeworfen werden, ist dabei für Sie uninteressant. Wendet man nun den Formalismus des endlichen Automaten auf unse- ren Zigarettenautomaten an, so ist bei einem Einwurf von 4,- DM der endliche Automat Zigarettenautomat = (T,Q,R,q[0],F) ... im Endzustand - es gibt Zigaretten. Solange jedoch nicht ge- nügend Münzen eingeworfen wurden, ist der Endzustand nicht er- reicht - es gibt nichts! Die von unserem Beispielautomaten akzeptierte Sprache ist ganz einfach zu bestimmen: L(A) ist eine beliebige Folge von 1 und 2, deren Summe 4 ergeben muß. Eine vollständige Anwendung des formalen Konzepts des endlichen Automaten auf unser Beispiel ergibt dann: Zigarettenautomat: A =(T,Q,R,q[0],,n,F) mit T = {1,2} (1,- u. 2,- DM Stücke) Q = {q[0],q[1],q[2],q[3],q[4]} (interne Zustände) F = {q[4]} und R = {q[0]1 -> q[1],q[0]2 -> q[2], q[1]1 -> q[2],q[1]2 -> q[3], q[2]1 -> q[3],q[2]2 -> q[4], q[3]1 -> q[4]} Man sieht: Man sieht nichts! Die Notation der Regelmenge ist zwar sehr konkret und platzspa- rend, aber eben dadurch auch sehr un- übersichtlich. Im allgemei- nen beschreibt man daher die Elemente der Regelmenge (das sind Abbildungen) durch einen Übergangsgraphen, der den Vorteil der Übersichtlichkeit bietet. Ein solcher Graph sieht dann, auf unser Beispiel bezogen, wie in Abbildung 5 aus. Zigarettenautomat 2 ┌───────────>──────────┐ │ │ │ │ 1 1 1 1 ┌──────┐ Start > (q[0])─────>(q[1])─────>(q[2])─────>(q[3])─────>│ q[4] │ └──────┘ │ │ └───────────>────────────┘ 2 Diesen Graphen bezeichnet man häufig auch als Transitionsgraphen (ein Wort, das in Insidergesprächen immer sehr gut ankommt). Zum besseren Verständnis enthält Abbildung 6 noch ganz kurz die Er- klärung der verwendeten Symbole. Legende der benutzten Symbole ┌───────┐ │ │ │ │ Endzustand └───────┘ ( ) Zwischenzustand m (q[i]) ─────> (q[j]) (q[i]m ──>q[j]) aus R mit q ,q aus Q und m aus T Aus dem Graphen wird auch leicht ersichtlich, daß es in q[4] kei- nen Übergang zu einem anderen Zustand gibt. Endliche Automa- ten, die diese Eigenschaft besitzen, werden als unvollständige endli- che Automaten bezeichnet. Übrigens: Natürlich kann jeder unvoll- ständige endliche Automat durch Hinzufügen eines neuen 'Fehlerzu- standes' in einen endlichen Automaten überführt werden. Soweit zum Zigarettenautomaten. Im zweiten Beispiel geht es be- sonders für die Programmierer um ein wesentlich praxisorientier- teres Thema - und zwar um den Kommentarautomaten für Pascal-Kom- mentare. Hier gilt ja bekanntlich folgende Regel: - Kommentare werden durch ("*" eingeleitet und mit "*") beendet. Dazwischen können beliebige Zeichen stehen. Entwickelt man den Automaten direkt nach "Gefühl", so erhält man in etwa den Graphen in Abbildung 7. Der Pascal - Kommentarautomat S \ {*} ┌─<┐ │ │ │ │ │ │ ( * │ * ) ┌──────┐ Start > (q[0])────>(q[1])────>(q[2])└────>(q[3])─────> │ q[4] │ │ └──────┘ │ │ └<────────<─┘ S \ {)} S vertritt hier den gesamten Zeichenvorrat der verwendeten Ma- schine. Formalisiert ergibt dies: Kommentarautomat: A = (T,Q,R,q[0],F) mit T = S (Zeichenvorrat der Maschine) Q = {q[0],..,q[4]} F = {q[4]} und R (diesmal als Tabelle) in Abbildung 8. Regelmenge R in Tabellenform ┌────┬────┬─────┬────┬───┐ │ │ k │ ( │ * │ ) │ k ist S \{(,),* } ├────┼────┼─────┼────┼───┤ │q0 │ / │ q1 │ / │ / │ ├────┼────┼─────┼────┼───┤ │q1 │ / │ / │q2 │ / │ ├────┼────┼─────┼────┼───┤ │q2 │ q2 │ q2 │q3 │q2 │ ├────┼────┼─────┼────┼───┤ │q3 │ q2 │ q2 │q2 │q2 │ ├────┼────┼─────┼────┼───┤ │q4 │ / │ / │ / │ / │ └────┴────┴─────┴────┴───┘ Leuchtet doch alles irgendwie ein, oder? Es bleibt zum Schluß noch zu klären, wie man in der Praxis so ei- nen endlichen Automaten implementiert. Zwei mögliche Lösungen bieten sich da sofort an. Einmal kann der Automat sehr leicht ausprogrammiert werden. Eine Schleife wird konstruiert, die eine Fallunterscheidung über sämtliche Zeichen des Alphabets macht - fertig. Für Automaten mit vielen Übergängen und großen Alphabeten wird es dann natürlich sehr aufwendig. Eine andere Möglichkeit besteht darin, die Regelmenge als Matrix irgend wo im Speicher abzulegen. Einen neuen Zustand erhält man dann, indem man jeweils die Matrix mit aktuellem Zustand und eingelesenem Zeichen indi- ziert. In Pascal sähe ein e solche Matrix etwa so aus: TYPE Zustände = (q0,q1,q2,....); Alphabet = (a,b,c,d,.....); Übergang = ARRAY[Zustände,Alphabet] OF Zustände; Allerdings gibt es in der Regel Probleme mit der Matriximplemen- tie- rung. Aufgrund der Tatsache, daß die Alphabete doch recht umfan- greich sein können, und die Matrix im allgemeinen nicht sehr stark besetzt ist, wird ein Großteil des zu Verfüg ung ste- henden Speicherraumes verschwendet. (Abhilfe können hier dynami- sche Arrays bieten (kein Pascal !)). Das war's auch schon zum Thema Automaten. Ein weiteres Werkzeug, das man in der Informatik fast immer benötigt und das uns späte- stens im Parser des Compilers von großem Nutzen sein wird, sind die Grammatiken. Grammatiken stellen ein Ersetzungssystem für Zeichenreihen dar. Mit Hilfe einer Grammatik ist es möglich, be- ginnend von einem Startsymbol und unter Zuhilfenahme von Erset- zungsregeln, Sätze einer Sprache zu erzeugen, die der Syntax die- ser Sprache genügen. Dabei werden solange Nicht-Terminale (durch Grammatikregeln er- setzbare Zeichen) substituiert, bis ein vollständiger Satz aus Terminalen (nicht weiter ersetzbaren Zeichen) vorliegt. Den von einem Startsymbol bis zum fertigen Satz mit Hilfe der entspre- chenden Grammatikregeln stattfindenden Ersetzungsvorgang nennt man Ableitung. Derartige Ableitungen werden normalerweise gra- phisch in einer Baumform dargestellt (Ableitungsbaum). Ohne auf die formale Definition der Grammatiken ein zugehen, soll hier die dunkle Theorie durch ein Beispiel etwas erhellt werden. Gegeben sei dazu eine Sprache, die durch die folgende Syntax de- finiert ist: (i) Satz ::= Subjekt Prädikat Objekt. (ii) Subjekt ::= 'Studenten' | 'Programmierer' | 'Weihnachtsmänner'. (iii) Prädikat ::= 'lieben' | 'kaufen' | 'essen'. (iv) Objekt ::= 'Computer' | 'Müsli' | 'Weihnachtsbäume'. Die vier Regeln haben dabei die folgende Bedeutung : (i) Ein Satz besteht aus einem Subjekt, gefolgt von einem Prädikat, gefolgt von einem Objekt. (ii) Das Subjekt besteht aus dem Wort 'Studenten', 'Programmierer' oder 'Weihnachtsmänner'. (iii) Das Prädikat kann 'lieben', 'kaufen' oder 'essen' sein. (iv) Das Objekt ist entweder 'Computer', 'Weihnachtsbäume' oder 'Müs- li'. Die Syntax dieser Sprache ist somit durch die Regeln (i) bis (iv) fest definiert. Die Nicht-Terminal-Symbole - das sind zur Erinne- rung die Symbole, die noch ersetzt werden können - sind Satz, Subjekt, Prädikat und Objekt. Alle übrigen Symbo le sind Termi- nal-Symbole (Studenten, Programmierer, Weihnachtsmänner,...). Bei allen Regeln unserer Beispielgrammatik fällt auf, daß auf der linken Seite einer jeden Regel immer genau ein Nichtterminal steht. Diese Art von Regeln haben einen besonderen Namen. Sie werden kontextfreie Regeln genannt. Das heißt: Ein Nicht-Terminal kann immer unabhängig von seinem linken und rechten Nachbarn durch die entsprechende Regel der Grammatik ersetzt werden. Der Vorteil von kontextfreien Grammatiken ist, daß relativ schnell festgestellt werden kann, ob ein Satz zur Sprache gehört oder nicht. Bei einem Compiler bedeutet dies: Ist das eingegebene Pro- gramm, das hier einem Satz der Grammatik der gewählten Program- miersprache entspricht, syntaktisch korrekt oder nicht? Wir werden spätestens beim Parser und in der semantischen Analyse sehen, daß die Verwendung von kontextfreien Grammatiken alleine nicht ausreicht, um Programmiersprachen wie Pascal vollständig zu beschreiben. Wir werden dann weiter erörtern , welche Möglichkei- ten es gibt, die Vorteile von kontextfreien Sprachen zu nutzen und die Nachteile (geringere Mächtigkeit gegenüber kontextabhän- gige Sprachen) durch etwaige 'Tricks' zu beseitigen. Zurück zum Beispiel. Versuchen wir den Satz 'Studenten lieben Müsli' abzuleiten. Das geschieht ganz einfach, indem wir die Re- geln (i) bis (iv) nacheinander anwenden, und zwar folgendermaßen ('-->' soll immer genau ein Ableitungsschritt sein ): Satz --> Subjekt Prädikat Objekt (mit Regel (i)) --> 'Studenten' Prädikat Objekt (mit Regel (ii)) --> 'Studenten' 'lieben' Objekt (mit Regel (iii)) --> 'Studenten' 'lieben' 'Müsli' (mit Regel (iv)) Der zugehörige Ableitungsbaum sieht wie in Abbildung 9 gezeigt aus. Ableitungsbaum ─────── ( Start ) ─────── │ ┌────────────────────┼────────────────────┐ │ │ │ │ │ │ ───┴───── ────┴───── ───┴──── ( Subjekt ) ( Prädikat ) ( Objekt ) ───────── ────────── ──────── │ │ │ │ │ │ │ │ │ │ │ │ ───┴─────── ────┴─── ───┴─── ( Studenten ) ( lieben ) ( Müsli ) ─────────── ──────── ─────── Der Ersetzungsprozeß startet an der Wurzel des Baumes mit dem Nicht-Terminal 'Satz'. Gehört der zu überprüfende Satz zu der von der Grammatik erzeugten Sprache, so ergeben die Blätter des Bau- mes von links nach rechts gelesen gerade eben die sen Satz. In diesem Beispiel ist der Satz 'Studenten lieben Müsli' somit ein gültiger Satz der Sprache, die von dieser Grammatik erzeugt wird. Soweit das Beispiel - und jetzt kurz das Ganze formal: Eine Grammatik G ist ein 4-Tupel G = (T,N,P,Z) mit: - T ist die Menge der Terminal- Symbole. - N ist die Menge der Nicht-Terminal- Symbole. - Z aus N ist das Startsymbol der Grammatik. Das Startsymbol bildet die Wurzel des Ableitungsbaumes. - P ist eine Menge von Ersetzungzregeln. In einigen Grammatikde- finitionen steht hier das Wort 'Produktionen' für Ersetzungsre- geln, womit das Gleiche gemeint ist. - Bezüglich T und N gilt die Vereinbarung, daß beide Mengen dis- junkt sein müssen. Die Sprache L(G), die von einer Grammatik G erzeugt wird, ist definiert als: - L(G) := {x | Z =>*x; x aus T*} Z=>*x bedeutet dabei, daß x aus Z in endlich vielen Schritten ab- leitbar (Ableitungsbaum von der Wurzel zu den Blättern be- trach- ten), bzw. x auf Z in endlich vielen Schritten reduzierbar sein muß (Ableitungsbaum von den Blättern zur Wurzel verfolgen). In unserem Beispiel ist L(G) sogar endlich und kann leicht be- stimmt werden. Zum Schluß noch zur Notation der Grammatikregeln. In aller Regel wird zur Darstellung von Grammatiken die Backus- Naur-Form (BNF) verwendet. Sie wurde zur Definition der Program- miersprache Al- gol60 erstmals benutzt. Auch in unserem 'Müsli'-Beispiel wurde diese Notation verwendet. Die BNF-Struktur ist recht einfach und leuchtet sofort ein. Linke und rechte Regelseiten werden durch '::=' getrennt, Terminal-Symbole werden in Hochkom- mata einge- schlossen, Alternativen stellt man durc h '|' dar. Jede Regel wird mit einem '.' beendet. Zur BNF-Notation existieren noch zahlreiche Erweiterungen hinsichtlich Klammerung, Optional- klam- merung, Konkatenation usw. Diese Spezialform wird mit EBNF (Ex- tended Backus-Naur-Form) bezeichnet. Auf sie soll hier jedoch nur hingewiesen werden. Ebenfalls erinnert werden soll an die Möglichkeit der Darstellung von Grammatiken mit Hilfe von Syntax-Diagrammen. Sie dürften ebenfalls jedem Leser ausreichend bekannt sein. Von ihnen wird im weiteren Verlauf der Serie allerdings kein Gebrauch gemacht. Wir hoffen, daß Sie nun nicht zwischen Automaten und Grammatiken 'verdurstet' sind - mit der Theorie ist jetzt auch erst mal Schluß! In der nächsten Folge geht es dann an's Eingemachte: Der Scanner wird besprochen und wegen seinem im Vergleich zu manch anderen Komponnenten geringen Umfang auch komplett als Listing abgedruckt und erläutert. Dazu wäre es ganz gut, wenn ein paar Dinge über die Automatentheorie 'kleben' bleiben würden. Literatur: N. Wirth Compilerbau Teubner Stuttgart 1981 N. Wirth Systematisches Programmieren Teubner Stuttgart 1985 K. Jensen/N. Wirth Pascal user manual & report Springer Verlag