Systematische Programmentwicklung

Ein Übersetzer ist eine Erweiterung eines Parsers. Genau wie ein Parser analysiert ein Übersetzer die syntaktische Struktur eines Eingabe­wortes gemäß einer zugrunde liegenden Grammatik, führt aber nebenbei bestimmte Übersetzungs­aktionen durch. Hierdurch rechnet er syntax­gesteuert das Eingabewort in einen bestimmten Wert einer Zielmenge um.

Ein Übersetzer berechnet also eine Abbildung von der Sprache, die durch die Grammatik erzeugt wird, in die Zielmenge. Darüber hinaus erzeugt der Übersetzer für alle Wörter, die nicht von der Grammatik erzeugt werden, eine Fehler­meldung.

Die Zielmenge kann auch wieder eine Sprache sein, aber genauso gut eine beliebige andere Menge. Im ersten einfachen Beispiel wird das Eingabewort in eine Zahl übersetzt. Andere Beispiele wären, einen regulären Ausdruck in einen endlichen Automaten zu übersetzen oder ein C-Programm in Maschinen­code zu übersetzen¹).

Um aus einem Parser einen Übersetzer zu erzeugen, ordnen Sie jeder Produktion der Grammatik bestimmte Übersetzungs­aktionen zu. Der Übersetzer führt dann parallel zum Parsen die jeweiligen Übersetzungs­aktionen aus. Die geeigneten Übersetzungs­aktionen richten sich nach der gewünschten Abbildung in die Zielmenge; sie lassen sich durch Untersuchung der Ableitungs­bäume von Wörtern ermitteln.

Im Programm unter­scheidet sich ein Übersetzer von einem Parser dadurch, dass jede Funktion, die einer Variablen der Grammatik entspricht, einen Rückgabewert liefert, nämlich das Ergebnis der Übersetzung.

Um dieses Prinzip zu ver­anschaulichen, betrachten Sie zunächst ein sehr einfaches Beispiel. Dem allgemeinen Vorgehen zur Konstruktion eines Übersetzers wenden Sie sich dann später zu.

Zahlen mit Vorzeichen

Als erstes formen Sie den aller­einfachsten Parser für einstellige Zahlen mit Vorzeichen in einen Übersetzer um. Das Ergebnis der Übersetzung beispiels­weise des Eingabe­wortes "-5" soll der Zahlenwert -5 sein.

Die Untersuchung eines Ableitungs­baums etwa für "-5" zeigt, dass der Zahlenwert, den number liefert, durch Multi­plikation von -1 oder +1 mit dem Zahlenwert, den digit liefert, zustande kommt. Hierbei wird der Vorzeichen­faktor -1 oder +1 von sign geliefert. Bild 1 zeigt den Ableitungs­baum (a) und den ent­sprechenden Daten­fluss­graphen (b).

Somit ordnen wir den Produktionen der Grammatik die folgenden Übersetzungs­aktionen hinzu:

number sign digit		return sign()*digit()
sign +		return +1
sign -		return -1
sign ε		return +1
digit 0		return 0
digit 9		return 9

Im Programm gehen Sie vom Parser aus und versehen jede Funktion, die einer Variablen der Grammatik entspricht, mit einem geeigneten Rückgabewert, der sich aus der Anwendung der jeweiligen Übersetzungs­aktionen ergibt.

Die Funktion digit ergänzen Sie, indem Sie für eine jeweilige gelesene Ziffer die ent­sprechende Zahl als Rückgabewert zurückgeben.

In der Funktion sign geben Sie +1 zurück, wenn Sie ein Pluszeichen finden, bzw. -1, wenn Sie ein Minuszeichen finden, ansonsten +1.

Und schließlich fügen Sie in der Funktion number die Ergebnisse von sign und digit in geeigneter Weise zusammen:

Modul SimpleNumberCompiler

In einem Modul SimpleNumberCompiler fassen Sie diese Funktionen zusammen. Die Hilfs­funktionen wie etwa comes oder consume befinden sich im Basismodul Parser.

Funktion compile

Die Funktion parse im Basismodul Parser ändern Sie noch in der Weise, dass sie einen Wert zurückgeben, und benennen sie in compile um. Diese Funktion muss sich im Modul Parser befinden, da hier die globalen Variablen inputstring usw. definiert werden.

Im Haupt­programm testen Sie den SimpleNumberCompiler dann folgender­maßen, hierbei rufen Sie die Funktion compile auf und speichern den Rückgabewert. Das Eingabewort und den Namen der Funktion, die dem Startsymbol der Grammatik entspricht, übergeben Sie als Parameter.