Parser und Übersetzer
Recursive-Descent-Compiler für mehrstellige Zahlen
Es sollen nun mehrstellige ganze Zahlen ausgewertet werden. Der Übersetzer übersetzt also beispielsweise das Eingabewort "123" in die Zahl 123. Im weiteren Verlauf kommen auch Kommazahlen hinzu, sodass der Übersetzer in der Lage ist, auch Eingabewörter wie "123.05" oder "000.567" in die entsprechenden Zahlenwerte zu übersetzen.
Die Aufgabe bei der Konstruktion eines Recursive-Descent-Übersetzers besteht darin, einen entsprechenden Recursive-Descent-Parser um geeignete Übersetzungsaktionen anzureichern.
Funktion integer mit Rückgabewert
Wir gehen zunächst von der Produktion
| integer |  | digit | integer digit |
für Integer-Zahlen aus, auch wenn diese aufgrund ihrer Linksrekursivität nicht für die Recursive-Descent-Methode geeignet ist.
Der Ableitungsbaum für das Eingabewort "123" hat die folgende Gestalt (Bild 1a). Um den zugehörigen Zahlenwert zu ermitteln, werden an den inneren Knoten des Ableitungsbaumes, je nach angewendeter Produktion, bestimmte Übersetzungsaktionen ausgeführt. An einem digit-Knoten wird per Typumwandlung aus einer Ziffer eine Integer-Zahl erstellt. An einem integer-Knoten wird, wenn die Produktion integer digit angewendet wird, der von digit gelieferte Zahlenwert unverändert übernommen. Wird dagegen die Produktion integer integer digit angewendet, so wird der von integer gelieferte Wert mit 10 multipliziert und der von digit gelieferte Wert hinzuaddiert. Ein entsprechender Datenflussgraph ist in Bild 1b dargestellt.
Auf diese Weise wird das Eingabewort von links nach rechts ausgewertet. Wie bereits erwähnt, sind linksrekursive 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 | | digit digit* |
Die Übersetzungsfunktion ermittelt zunächst den Zahlenwert v der ersten digit. Wenn keine weiteren digits mehr folgen, wird dieser Wert v zurückgegeben. Ansonsten wird der Wert v mit 10 multipliziert und der Zahlenwert der nächsten digit hinzuaddiert usw. Die Programmvariable v tritt im Datenflussgraphen also an die Stelle von integer (Bild 1c).
v=digit()
while comesDigit():
v=v*10+digit()
return v
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 digit digit* ermöglicht in einfacher Weise die Auswertung von links nach rechts.
Die Nachkommastellen einer Kommazahl lassen sich dagegen am einfachsten von rechts nach links auswerten. Wir verwenden daher die rechtsrekursive Produktion
| fraction | | digit | digit fraction |
und faktorisieren diese:
| fraction | | digit (ε | fraction) |
Die entsprechende Implementierung lautet
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 Nachkommastellen, 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]
H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 16.08.2012 Updated: 17.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden