Parser und Übersetzer

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. Wir werden im ersten einfachen Beispiel das Eingabewort in eine Zahl übersetzen; man kann aber auch einen regulären Ausdruck in einen Automaten oder ein C-Programm in Maschinen­code übersetzen¹).

Um aus einem Parser einen Übersetzer zu erzeugen, werden jeder Produktion der Grammatik bestimmte Übersetzungs­aktionen zugeordnet. 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 wir zunächst ein sehr einfaches Beispiel. Dem allgemeinen Vorgehen zur Konstruktion eines Übersetzers wenden wir uns dann später zu.

Zahlen mit Vorzeichen

Als erstes formen wir 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 wir 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.

In der Funktion digit arbeiten wir mithilfe der Funktion getSymbol das nächste Zeichen des Eingabe­wortes ab, wandeln es in eine Integer-Zahl um und geben diesen Wert zurück.

Die Funktion sign gibt +1 zurück, wenn ein Pluszeichen gefunden wird, bzw. -1, wenn ein Minuszeichen gefunden wird, ansonsten +1.

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

Modul SimpleNumberCompiler

In folgendem Modul SimpleNumberCompiler sind diese Funktionen zusammen­gefasst. Die Hilfs­funktionen wie etwa comes oder consume finden sich im Basismodul Parser.

Im Haupt­programm wird der SimpleNumberCompiler dann folgender­maßen getestet, hierbei wird die Funktion compile aufgerufen und der Rückgabewert gespeichert. Das Eingabewort und der Name der Funktion, die dem Startsymbol der Grammatik entspricht, werden als Parameter übergeben.