Parser und Übersetzer

Recursive-Descent-Übersetzer

 aufwärts

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 übersetzen1).

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).

Bild 1: Ableitungsbaum für -5 und entsprechender Datenflussgraph
Bild 1: Ableitungsbaum für -5 und entsprechender Datenflussgraph

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

number geht über nachsign digit return sign()*digit()
sign geht über nach+ return +1
sign geht über nach- return -1
sign geht über nachε return +1
digit geht über nach0 return 0
    drei Punkte übereinander      drei Punkte übereinander 
digit geht über nach9 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.

def digit():
    if comesDigit():
        return int(getSymbol())
    else:
        raise Exception("Ziffer erwartet")

 

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

def sign():
    if comes("+"):
        consume()
        return +1
    elif comes("-"):
        consume()
        return -1
    else:
        return +1

 

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

def number():
    return sign()*digit()

Modul SimpleNumberCompiler

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

from Parser import *

def number():
    return sign()*digit()

def sign():
    if comes("+"):
        consume()
        return +1
    elif comes("-"):
        consume()
        return -1
    else:
        return +1

def digit():
    if comesDigit():
        return int(getSymbol())
    else:
        raise Exception("Ziffer erwartet")

def comesDigit():
    return comesAnyOf("0123456789")

 

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.

from SimpleNumberCompiler import *

v=compile("-5", number)
showErrorPosition()
print "Ergebnis:", v

1)  Übersetzer, die Programmcode in anderen Programmcode übersetzen, werden als Compiler bezeichnet

 

Weiter mit:   [Recursive-Descent-Compiler für mehrstellige Zahlen]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 16.08.2012   Updated: 10.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik