Systematische Programmentwicklung

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

Gehen Sie zunächst von der Produktion

integer

digit  |  integer 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, führen Sie an den inneren Knoten des Ableitungs­baumes, je nach angewendeter Produktion, bestimmte Übersetzungs­aktionen aus. An einem digit-Knoten erstellen Sie per Typ­umwandlung aus einer Ziffer eine Integer-Zahl. An einem integer-Knoten übernehmen Sie, wenn die Produktion integer digit angewendet wird, den von digit gelieferten Zahlenwert. Wenn dagegen die Produktion integer integer digit angewendet wird, multiplizieren Sie den von integer gelieferten Wert mit 10 und addieren den von digit gelieferten Wert hinzu. In Bild 1b sehen Sie den ent­sprechenden Daten­fluss­graphen.

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

Sie erhalten hierdurch die Produktion

integer

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

Auswertung von links nach rechts oder von rechts nach links

Mehrstellige ganze Zahlen werten Sie am einfachsten in der angegebenen Weise von links nach rechts aus. Die verwendete Produktion integer digit digit* ermöglicht in einfacher Weise die Auswertung von links nach rechts.

Die Nach­komma­stellen einer Kommazahl werten Sie dagegen am einfachsten von rechts nach links aus. Verwenden Sie daher die rechts­rekursive Produktion

fraction

digit  |  digit fraction

und faktorisieren diese:

fraction

digit (ε  |  fraction)

Die ent­sprechende Implementierung lautet

Es bleibt nur noch, dass Sie die vollständige Grammatik für mehrstellige Zahlen mit oder ohne Nach­komma­stellen und mit oder ohne Vorzeichen zusammenstellen und in einen ent­sprechenden Recursive-Descent-Copiler umsetzen.