Parser und Übersetzer

Recursive-Descent-Compiler für mehrstellige Zahlen

 aufwärts

Es sollen nun mehrstellige ganze Zahlen ausgewertet werden. Der Übersetzer übersetzt also beispiels­weise das Eingabewort "123" in die Zahl 123. Im weiteren Verlauf kommen auch Kommazahlen hinzu, sodass der Übersetzer in der Lage ist, auch Eingabe­wörter wie "123.05" oder "000.567" in die ent­sprechenden Zahlenwerte zu übersetzen.

Die Aufgabe bei der Konstruktion eines Recursive-Descent-Übersetzers besteht darin, einen ent­sprechenden Recursive-Descent-Parser um geeignete Übersetzungs­aktionen anzureichern.

Funktion integer mit Rückgabewert

Wir gehen zunächst von der Produktion

integer geht über nachinteger digit  |  digit

für Integer-Zahlen aus, auch wenn diese aufgrund ihrer Links­rekursivität nicht für die Recursive-Descent-Methode geeignet ist.

Der Ableitungs­baum für das Eingabewort "123" hat die folgende Gestalt (Bild 1a). Um den zugehörigen Zahlenwert zu ermitteln, werden an den inneren Knoten des Ableitungs­baumes, je nach angewendeter Produktion, bestimmte Übersetzungs­aktionen ausgeführt. An einem digit-Knoten wird per Typ­umwandlung aus einer Ziffer eine Integer-Zahl erstellt. An einem integer-Knoten wird, wenn die Produktion integer geht über nachdigit angewendet wird, der von digit gelieferte Zahlenwert unverändert übernommen. Wird dagegen die Produktion integer geht über nachinteger digit angewendet, so wird der von integer gelieferte Wert mit 10 multi­pliziert und der von digit gelieferte Wert hinzuaddiert. Ein ent­sprechender Daten­fluss­graph ist in Bild 1b dargestellt.

Auf diese Weise wird das Eingabewort von links nach rechts ausgewertet. Wie bereits erwähnt, sind links­rekursive Produktionen nicht mit der Recursive-Descent-Methode verträglich. Daher wandeln wir die Rekursion in eine Iteration um (siehe Rekursion durch Iteration ersetzen).

Wir erhalten hierdurch die Produktion

integer geht über nachdigit digit*

Die Übersetzungs­funktion ermittelt zunächst den Zahlenwert v der ersten digit. Wenn keine weiteren digits mehr folgen, wird dieser Wert v zurück­gegeben. Ansonsten wird der Wert v mit 10 multi­pliziert und der Zahlenwert der nächsten digit hinzuaddiert usw. Die Programm­variable v tritt im Daten­fluss­graphen also an die Stelle von integer (Bild 1c).

def integer():
    v=digit()
    while comesDigit():
        v=v*10+digit()
    return v
Bild 1: Ableitungsbaum (a) sowie Datenflussgraphen (b) und (c) für das Eingabewort '123'
Bild 1: Ableitungsbaum (a) sowie Datenflussgraphen (b) und (c) für das Eingabewort "123"

Auswertung von links nach rechts oder von rechts nach links

Mehrstellige ganze Zahlen lassen sich am einfachsten in der angegebenen Weise von links nach rechts auswerten. Die verwendete Produktion integer geht über nachdigit digit* ermöglicht in einfacher Weise die Auswertung von links nach rechts.

Die Nach­komma­stellen einer Kommazahl lassen sich dagegen am einfachsten von rechts nach links auswerten. Wir verwenden daher die rechts­rekursive Produktion

fraction geht über nachdigit fraction  |  digit

und faktorisieren diese:

fraction geht über nachdigit (fraction  |  ε)

Die ent­sprechende Implementierung lautet

def fraction():
    v=digit()
    if comesDigit():
        v=v+fraction()
    return 0.1*v

Aufgaben

Aufgabe 4:  Implementieren Sie einen Recursive-Descent-Compiler für Kommazahlen mit oder ohne Vorzeichen sowie mit oder ohne Nach­komma­stellen, also z.B. für Zahlen wie 3.14, -0.5, 17, 17.00, +17. Entwerfen Sie zunächst die Grammatik in erweiterter Backus-Naur-Form und setzen Sie anschließend die Grammatik 1:1 in das Programm um.

 

Weiter mit:   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