Programmiersprachen
LVA 185.208, VL 2.0, 2006 S

1. Übungsaufgabe

Entwickeln Sie in Java, C# oder C++ einen programmierbaren Taschenrechner entsprechend folgenden Spezifikationen und lösen Sie damit die weiter unten beschriebene Testaufgabe (Primzahlberechnung):

Allgemeine Beschreibung:

Alle Eingaben erfolgen in Postfix-Notation (auch UPN-Logik genannt - zuerst kommen die Argumente, danach der Operator). Die Anzahl der benötigten Argumente hängt vom Operator ab. Argumente sind ganze Zahlen oder Ausdrücke in eckigen Klammern (siehe unten). Zum Beispiel ist 1 2+ eine Anwendung des Operators + auf 1 und 2, die als Ergebnis 3 liefert. Der Ausdruck 1 2 3 4+*- wird zu 1-(2*(3+4)) = -13 ausgewertet: Der (von links gelesen) erste Operator addiert die direkt davor stehenden Argumente 3 und 4 zu 7, der Operator * wird auf die nach der Addition direkt davor stehenden Argumente 2 und 7 angewandt, und schließlich wird - auf 1 und 14 angewandt.

Ausdrücke in eckigen Klammern werden nicht gleich ausgewertet. Einige Operatoren verarbeiten geklammerte Ausdrücke als Argumente. Zum Beispiel wird [2*] als Argument des Operators a selbst als Operator gesehen, der ein Argument mit 2 multipliziert. Der Ausdruck 3[2*]a wird zu 3 2* bzw. 6 ausgewertet.

In den Taschenrechner sollen Ausdrücke direkt eingegeben werden können, und Ergebnisse sollen nach jedem Tastendruck neu berechnet und ausgegeben werden, ohne spezielle Taste mit der Bedeutung jetzt bitte berechnen. Da es in Java schwierig ist, Tastendrücke direkt abzufragen, können Sie die Auswertung von Eingaben verzögern, bis die Eingabetaste gedrückt wird. Danach soll die Abarbeitung jedoch für jeden eingegebenen Buchstaben getrennt erfolgen.

Architektur:

Die Architektur des programmierbaren Taschenrechners besteht aus folgenden Teilen:

Stack

Ausdrücke in Postfix-Notation können mit Hilfe eines Stacks einfach berechnet werden: Jedes Argument wird als neuer Eintrag am Top-of-Stack abgelegt. Die Ausführung eines Operators nimmt die benötigte Anzahl von Argumenten vom Stack und legt Ergebnisse auf den Stack. Die Ausgabe der Ergebnisse soll den gesamten Stackinhalt (oder bei einem großen Stack zumindest die obersten Stackeinträge) umfassen.

Eingabeliste

Sie enthält die eingegebenen, aber noch nicht abgearbeiteten Eingaben (nur ASCII-Zeichen). Alle Eingaben werden in der Reihenfolge in dieser Liste abgearbeitet. Außer durch Tastatureingaben werden auch durch den Operator a Eingaben in diese Liste geschrieben. Der Inhalt der Liste kann, muss aber nicht als Teil des Ergebnisses ausgegeben werden (enthält eventuell wichtige Debug-Information).

Argumentspeicher

Zur Vereinfachung der Eingabe von Zahlen und geklammerten Ausdrücken verwenden wir diesen Speicher, der zwischen dem Stack und der Eingabeliste steht. Eingegebene Ziffern wandern in den Argumentspeicher und werden dort zu ganzen Zahlen zusammengesetzt. Erst wenn ein anderes Zeichen als eine Ziffer in der Eingabe steht wandert die bis dahin zusammengesetzte Zahl vom Argumentspeicher (als zumindest 64 Bit große Zahl) auf den Stack. Ebenso kommen nach einer öffnenden eckigen Klammer alle Eingaben bis zu einer passenden schließenden Klammer in den Argumentspeicher und werden von dort erst bei Abarbeitung der entsprechenden schließenden Klammer als ein Argument (z.B. als String) auf den Stack gelegt. Klammern können geschachtelt werden. Erst bei Schließen der letzten offenen Klammer ist das Argument abgeschlossen. Es ist möglicherweise sinnvoll, den Inhalt eines nichtleeren Argumentspeichers bei der Ausgabe als oberstes Stackelement anzuzeigen.

Register

Der Taschenrechner soll über mehrere (genaue Anzahl in der Aufgabenstellung nicht vorgegeben) durchnummerierte Register verfügen, in denen Zahlen und geklammerte Ausdrücke abgelegt werden können. Die Initialisierung der Register ist nicht festgelegt und kann frei gewählt werden. Dadurch können gleich beim Programmstart häufig benötigte Zahlen und Ausdrücke hier abgelegt werden. Wenn es viele Register gibt ist es wohl kaum möglich, alle Registerinhalte als Teil der Ausgabe anzuzeigen.

Zur Vereinfachung können für den Stack, die Eingabeliste, geklammerte Ausdrücke und Zahlen (vernünftig gewählte) Maximalgrößen festgelegt werden, bei deren Überschreitung eine Fehlermeldung ausgegeben wird. Nach Fehlermeldungen kann die Programmausführung jedenfalls abgebrochen werden.

Operationen:

Die Bedeutung folgender Eingaben ist vordefiniert:

Ziffern 0 bis 9:

Diese werden stets nur in den Argumentspeicher verschoben.

[:

Bewirkt, dass alle folgenen Eingaben bis zur entsprechenden schließenden Klammer in den Argumentspeicher verschoben werden. Falls vor Abarbeitung dieser Klammer keine Klammerebene offen war und der Argumentspeicher eine Zahl enthält, wird diese Zahl auf den Stack gelegt und der Argumentspeicher gelöscht.

]:

Falls genau eine Klammerebene offen ist wird der Ausdruck im Argumentspeicher auf den Stack gelegt und der Argumentspeicher geleert. Wenn mehrere Klammern offen sind wird das Zeichen in den Argumentspeicher geschrieben (wie bei allen anderen Eingaben auch). Sonst (keine Klammer offen) wird eine Fehlermeldung ausgegeben.

alle anderen Eingaben:

Falls mindestens eine Klammer offen ist wird das Zeichen in den Argumentspeicher geschrieben und es erfolgt keine weitere Abarbeitung. Sonst wird vor den (im Folgenden beschriebenen) eigentlichen Aktionen bei nichtleerem Argumentspeicher die Zahl im Argumentspeicher auf den Stack gelegt und der Argumentspeicher geleert.

white space (Leerzeichen, Tabulator, Newline, Return):

Es wird keine weitere Aktion ausgeführt.

arithmetische Operatoren und Vergleichsoperatoren (+, -, *, /, %, &, |, =, <, >)

Diese zweistelligen Operatoren entsprechen den Grundrechenarten und einfachen Vergleichen, wobei % für die Modulo-Operation steht und & bzw. | sowohl als logisches als auch als bitweises UND bzw. ODER verwendbar sind. Diese Operatoren nehmen die zwei obersten Argumente vom Stack und legen das Ergebnis auf den Stack. Wenn ein Argument keine Zahl ist soll ein Fehler gemeldet werden. Ausgenommen hiervon ist nur =: Wenn = auf zwei gleiche geklammerte Ausdrücke oder zwei gleiche Zahlen angewandt wird, soll als Ergebnis wahr zurückgegeben werden, sonst falsch. Dabei wird wahr durch die Zahl -1 dargestellt und falsch durch 0. Bei nichtassoziativen Operationen ist auf die Reihenfolge der Argumente zu achten: 4 2-, 4 2/ und 6 4% sollen jeweils 2 ergeben, und 4 2> und 2 4< sollen -1 liefern. Das Ergebnis einer Modulo-Operation soll dasselbe Vorzeichen wie das zweite Argument haben und betragsmäßig (also ohne Berücksichtigung von Vorzeichen) kleiner als das zweite Argument sein. Ein Fehler soll gemeldet werden, wenn das zweite Argument von / oder % gleich 0 ist.

bitweise Negation !

Diese einstellige Operation angewandt auf eine Zahl (am Top-of-Stack) negiert die Zahl bitweise (z.B: ist 0! gleich -1, entspricht also der logischen Negation). Anwendungen auf geklammerte Ausdrücke führen zu Fehlermeldungen.

Vorzeichenänderung ~

Diese einstellige Operation angewandt auf eine Zahl (am Top-of-Stack) ändert das Vorzeichen der Zahl. Anwendungen auf geklammerte Ausdrücke führen zu Fehlermeldungen.

Kopieren c

Diese Operation ersetzt das oberste Argument am Stack, das eine positive Zahl n sein muss, durch eine Kopie des n-ten Arguments am Stack. Eine Fehlermeldung wird ausgegeben wenn das oberste Argument keine positive Zahl ist oder der Stack nicht ausreichend viele Argumente enthält.

Löschen d

Diese Operation nimmt das oberste Argument vom Stack, das eine positive Zahl n sein muss, und entfernt zusätzlich das n-ten Argument vom Stack. Eine Fehlermeldung wird ausgegeben wenn das oberste Argument keine positive Zahl ist oder der Stack nicht ausreichend viele Argumente enthält.

Anwenden a

Diese Operation nimmt das oberste Argument vom Stack. Ist das Argument ein geklammerter Ausdruck, dann wird dieser (ohne umschließende Klammern) an vorderster Stelle in die Eingabeliste geschrieben, damit die darin enthaltenen Eingaben als nächste abgearbeitet werden. Ist das Argument eine Zahl, dann wird das Register mit der entsprechenden Nummer ausgelesen. Falls kein Register mit dieser Nummer existiert oder das Register keinen geklammerten Ausdruck enthällt, wird eine Fehlermeldung ausgegeben. Sonst wird der Ausdruck im Register (ohne umschließende Klammern) an vorderster Stelle in die Eingabeliste geschrieben.

Lesen r

Das oberste Argument am Stack muss eine Zahl sein, die ein Register bezeichnet, andernfalls erfolgt eine Fehlermeldung. Dieses oberste Argument wird durch den Inhalt des Registers ersetzt.

Speichern s

Das oberste Argument am Stack muss eine Zahl sein, die ein Register bezeichnet, andernfalls erfolgt eine Fehlermeldung. Das zweite Argument am Stack wird in das durch das erste Argument bezeichnete Register gespeichert. Beide Argumente werden vom Stack genommen.

Ausschalten q

Schaltet den Taschenrechner aus bzw. beendet das Programm.

Beispiele:

Einige Beispiele sollen die Verwendung dieser Operatoren verdeutlichen. Wir beschreiben einen Zustand des Taschenrechners durch den Stackinhalt (links vom Zeichen |, Top-of-Stack direkt neben |, Einträge durch Leerzeichen getrennt) und die Eingabeliste (rechts von |, nächstes zu verarbeitendes Zeichen direkt neben |). Inhalte des Argumentspeichers und der Register werden nicht angezeigt. Pfeile zwischen solchen Zustandsbeschreibungen zeigen Zustandsänderungen durch Ausführung von Operationen an.

Das erste Beispiel speichert den Ausdruck [2+c2d2da] als bedingte Anweisung im Register 7 und wendet diesen Ausdruck auf [0] (ausgeführt wenn die Bedingung falsch ist), [1~] (ausgeführt wenn die Bedingung wahr ist) und 0 (als Wahrheitswert falsch) an. Da bedingte Anweisungen leicht zu implementieren sind, braucht man dafür keine eigene Operation im Taschenrechner.

    |[2+c2d2da]7s[0][1~]0 7a
--> [2+c2d2da] |7s[0][1~]0 7a
--> [2+c2d2da] 7 |s[0][1~]0 7a
--> |[0][1~]0 7a
--> [0] |[1~]0 7a
--> [0] [1~] |0 7a
--> [0] [1~] 0 |7a
--> [0] [1~] 0 7 |a
--> [0] [1~] 0 |2+c2d2da
--> [0] [1~] 0 2 |+c2d2da
--> [0] [1~] 2 |c2d2da
--> [0] [1~] [0] |2d2da
--> [0] [1~] [0] 2 |d2da
--> [0] [0] |2da
--> [0] [0] 2 |da
--> [0] |a
--> |0
--> 0 |

Das nächste Beispiel verwendet Register 7 im Ausdruck [[][1c1-8a*]3c2>7a] zur Berechnung von Faktorielle, speichert diesen Ausdruck in Register 8 und wendet ihn auf die Zahl 4 an. Damit wird eine Möglichkeit gezeigt, wie man rekursive Routinen realisieren kann.

    |[[][1c1-8a*]3c2>7a]8s4 8a
--> [[][1c1-8a*]3c2>7a] |8s4 8a
--> [[][1c1-8a*]3c2>7a] 8 |s4 8a
--> |4 8a
--> 4 |8a
--> 4 8 |a
--> 4 |[][1c1-8a*]3c2>7a
--> 4 [] |[1c1-8a*]3c2>7a
--> 4 [] [1c1-8a*] |3c2>7a
--> 4 [] [1c1-8a*] 3 |c2>7a
--> 4 [] [1c1-8a*] 4 |2>7a
--> 4 [] [1c1-8a*] 4 2 |>7a
--> 4 [] [1c1-8a*] -1 |7a
... wende 7a (if-then-else) an
--> 4 [1c1-8a*] |a
--> 4 |1c1-8a*
--> 4 1 |c1-8a*
--> 4 4 |1-8a*
--> 4 4 1 |-8a*
--> 4 3 |8a*
--> 4 3 8 |a*
--> 4 3 |[][1c1-8a*]3c2>7a*
--> 4 3 [] |[1c1-8a*]3c2>7a*
--> 4 3 [] [1c1-8a*] |3c2>7a*
--> 4 3 [] [1c1-8a*] 3 |c2>7a*
--> 4 3 [] [1c1-8a*] 3 |2>7a*
--> 4 3 [] [1c1-8a*] 3 2 |>7a*
--> 4 3 [] [1c1-8a*] -1 |7a*
... wende 7a (if-then-else) an
--> 4 3 [1c1-8a*] |a*
--> 4 3 |1c1-8a**
--> 4 3 1 |c1-8a**
--> 4 3 3 |1-8a**
--> 4 3 3 1 |-8a**
--> 4 3 2 |8a**
--> 4 3 2 8 |a**
--> 4 3 2 |[][1c1-8a*]3c2>7a**
--> 4 3 2 [] |[1c1-8a*]3c2>7a**
--> 4 3 2 [] [1c1-8a*] |3c2>7a**
--> 4 3 2 [] [1c1-8a*] 3 |c2>7a**
--> 4 3 2 [] [1c1-8a*] 2 |2>7a**
--> 4 3 2 [] [1c1-8a*] 2 2 |>7a**
--> 4 3 2 [] [1c1-8a*] 0 |7a**
... wende 7a (if-then-else) an
--> 4 3 2 [] |a**
--> 4 3 2 |**
--> 4 6 |*
--> 24 |

Testaufgabe:

Entwerfen Sie (zum Testen des Taschenrechners) einen möglichst kurzen und effizienten Ausdruck (in einem Register) der entscheidet, ob eine Zahl eine Primzahl ist oder nicht, und testen Sie mit mehreren, auch längeren Zahlen.

Zusatzaufgaben für Interessierte:

Die Lösung dieser Zusatzaufgaben ist nicht verpflichtend und hat keinen Einfluß auf die Beurteilung.

Turing-Äquivalenz:

Es stellt sich die Frage, ob man mit diesem Taschenrechner wirklich alles Programmieren kann. Ist es damit möglich, eine Turing-Maschine zu bauen?

Bedeutung von Registern:

Register vereinfachen einige Programmieraufgaben zweifellos. Aber sind sie wirklich nötig? Kann man rekursive Routinen auch ohne Register realisieren? Kann man auch ohne Register eine Turing-Maschine bauen?