Frage zu Java Beispiel (Compilerbau)

[Thomas (Gast)]

Hallo,
auf der Suche nach Beispielprogrammen für einen einfachen Interpreter 
bin ich auf diese Seite mit einem Java-Beispiel gestoßen:
http://www.javaseiten.de/ch04s01.html

Und zwar geht es mir um das Listing 4.1. Mit dem Programm sollen 
einfache arithmetische Ausdrücke in die postfix Notation gewandelt 
werden (geht mir nur um die Umwandlung in diese Notation, der Rest mit 
dem Java Bytecode ist nicht von Belang).

Das Beispiel wird mit dem Ausdruck "3+7*5-9/3" getestet, was da auch 
funktioniert.
Ich kann das Programm jetzt nicht testen, da ich keinen Java Compiler 
auf meinem Rechner habe.

Aber wenn ich das im Kopf durchgehe, würde das Programm aber einen 
Ausdruck wie
"3+7+5*9"
nicht in korrekte Postfix Notation wandeln, welche meiner Meinung nach
"3 7 5 9 * + +" wäre.

Oder habe ich da etwas übersehen?

Eine andere Frage die ich dazu habe:
Im Wikipedia-Artikel zur UPN steht, dass ein Stapelregister mit 4 
Einträgen für alle Operationen ausreicht.
Mit dem Einfach-Compiler aus dem Java-Beispiel wäre diese Anzahl nicht 
ausreichend, da ich bei diesem theoretisch unendlich viele 
Stapelregister bräuchte.
Oder man müsste in einem zweiten Schritt die Notation umsortieren. Wie 
wird sowas am besten gemacht?

[Jasch (Gast)]

Thomas schrieb:
> Hallo,
> auf der Suche nach Beispielprogrammen für einen einfachen Interpreter
> bin ich auf diese Seite mit einem Java-Beispiel gestoßen:
> http://www.javaseiten.de/ch04s01.html
>
> Und zwar geht es mir um das Listing 4.1. Mit dem Programm sollen
> einfache arithmetische Ausdrücke in die postfix Notation gewandelt
> werden (geht mir nur um die Umwandlung in diese Notation, der Rest mit
> dem Java Bytecode ist nicht von Belang).
>
> Das Beispiel wird mit dem Ausdruck "3+7*5-9/3" getestet, was da auch
> funktioniert.
> Ich kann das Programm jetzt nicht testen, da ich keinen Java Compiler
> auf meinem Rechner habe.
>
> Aber wenn ich das im Kopf durchgehe, würde das Programm aber einen
> Ausdruck wie
> "3+7+5*9"
> nicht in korrekte Postfix Notation wandeln, welche meiner Meinung nach
> "3 7 5 9 * + +" wäre.
>
> Oder habe ich da etwas übersehen?

Das ist nicht die einzige mögliche Variante.

"5 9 * 7 + 3 +"

"5 9 * 3 7 + +"

"7 5 9 * + 3 +"

usw.

[Thomas (Gast)]

Ah, glaub das hab ich übersehen.
Das Programm würde aus:

"3+7+5*9"
ein
"3 7 + 5 9 * +"
machen.

Wenn ich jetzt annehme, dass eine Operation (+-*/) immer mit den unteren 
beiden Werten des Stapels arbeitet, und daraufhin die beiden Operanden 
vom Stapel löscht und das Ergebnis wieder auf den Stapel schiebt, sollte 
das so funktionieren.
Demnach bräuchte für diesen Fall nur 3 Einträge auf dem Stapel.

[Yalu X. (yalu) (Moderator)]

Der Parser in Listung 4.1 wertet mehrere Operationen gleichen Vorrangs
von links nach rechts aus, d.h. die Operationen werden als linksasso-
ziativ angesehen. So machen das auchalle gängigen Programmiersprachen.

D.h. a+b+c wird als (a+b)+c interpretiert und nicht als a+(b+c). Bei
Integer-Zahlen mach das keinen Unterschied, bei Float-Zahlen wegen der
Rundungsfehler aber schon.

Wenn man dies berücksichtig, ist die Umsetzung in Postfix eindeutig:

  (a+b)+c  ->  a b + c +

  a+b(+c)  ->  a b c + +

Also ist auch dein Beispiel eindeutig umzusetzen:

  3+7+5*9  -> (3+7)+5*9 -> 3 7 + 5 9 * +

Thomas schrieb:
> Im Wikipedia-Artikel zur UPN steht, dass ein Stapelregister mit 4
> Einträgen für alle Operationen ausreicht.

Die klassischen HP-Taschenrechner haben meist nur 4 Stack-Ebenen. In der
Praxis ist dies meistrens ausreichend, wenn man komplizierte Rechnungen
im Kopf vorher so umsortiert, das der längste Teilausdruck zuerst
berechnet wird. Bei mehr als 4 Stack-Ebenen besteht sowieso die Gefar,
dass man den Überblick verliert.

Ein Compiler sollte aber solche Beschränkungen nicht haben, so dass man
auch wie Ausdruck diesen ohne Umsortieren berechnen kann:

  1+2*(3+4*(5+6*7))  -> 1 2 3 4 5 6 7 * + * + * +