Programmiersprachen
LVA 185.208, VL 2.0, 2007 S

1. Übungsaufgabe

Entwickeln Sie in einer stark typisierten objektorientierten Programmiersprache (Java, C#, C++, etc.) einen programmierbaren Taschenrechner entsprechend folgenden Spezifikationen und lösen Sie damit die weiter unten beschriebene Testaufgabe (Primzahlberechnung):

Allgemeines:

Eingaben des Taschenrechners sind Konstanten sowie ein- und zweistellige Operationen, wobei einstellige Operationen in Postfix- und zweistellige in Infix-Schreibweise angegeben werden. Zweistellige Operatoren können unterschiedliche Prioritäten haben, aber sie sind stets links-assoziativ; das heißt, bei gleicher Priorität wird der linke Operand zuerst ausgewertet. Einstellige Operatoren haben in der Regel Priorität gegenüber zweistelligen. Zum Beispiel ergibt 3-+4*5= durch die höhere Priorität von * gegenüber dem +-Operator 17, wobei - ein Postfix-Operator für die Negation ist. Durch = wird die Eingabe abgeschlossen. Geklammerte Ausdrücke ändern die Auswertungsreihenfolge. Beispielsweise wird (3+4)-*5= zu -35 reduziert. Es gibt Operationen zum Speichern von Werten in Registern und zum Zugreifen auf Registerwerte, und es ist auch möglich, unausgewertete geklammerte Ausdrücke in Registern abzulegen. Zum Beispiel speichert 3+4s5 die Zahl 7 in Register 5 und 6d(5r*5r) den unausgewerteten Ausdruck 5r*5r in Register 6; 5r holt den aktuellen Wert aus Register 5, und eine Eingabe von 6r holt den Ausdruck aus Register 6 und führt ihn aus, wobei das Ergebnis das Quadrat des aktuellen Inhalts von Register 5 ist. Der Taschenrechner unterstützt nur ganze Zahlen, keine Fließkommazahlen.

Zwischenergebnisse werden angezeigt, sobald die Eingabe deren Berechnung erlaubt. 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 jedes eingegebene Zeichen getrennt erfolgen, und es darf keine Fehlermeldung ausgegeben werden, nur weil die Eingabe noch nicht vollständig ist.

Architektur:

Der Taschenrechner besteht aus folgenden Komponenten:

Eingabeliste

Sie enthält die noch nicht abgearbeiteten Eingaben (ASCII-Zeichen). Alle Eingaben werden in der Reihenfolge in dieser Liste abgearbeitet. Außer durch Tastatureingaben werden auch durch den Operator r (wenn der gelesene Registerinhalt ein unausgewerteter Ausdruck ist) Eingaben in diese Liste geschrieben.

Konstantenspeicher

Eingegebene Ziffern wandern in diesen Speicher und werden dort zu ganzen Zahlen zusammengesetzt. Erst wenn ein anderes Zeichen als eine Ziffer in der Eingabe steht, wandert die bis dahin zusammengesetzte positive ganze Zahl (zumindest 64 Bit) in ein Register. Auch geklammerte Ausdrücke als rechter Operand von d wandern in diesen Speicher, bis die entsprechende schließende Klammer (Schachtelungstiefe beachten, da der geklammerte Ausdruck auch Klammern enthalten kann) in der Eingabe steht. Erst dann wandert dieser Ausdruck in sein Register.

Register

Der Taschenrechner soll über viele (genaue Anzahl nicht vorgegeben) durchnummerierte frei verwendbare Register verfügen, in denen Zahlen und geklammerte Ausdrücke (z.B. als Strings) abgelegt werden können. Die Initialisierung der Register ist nicht festgelegt und kann frei gewählt werden. Dadurch können beim Programmstart häufig benötigte Zahlen und Ausdrücke vorgegeben werden.

Stack

Zur Behandlung geklammerter Ausdrücke ist ein Stack notwendig. Jeder Stackeintrag enthält ein (nicht frei verwendbares) Register und einen Operator. Die Operation des obersten Eintrags ist die aktuelle Operation.

Berechnungen werden im Wesentlichen (ohne Details) folgendermaßen ausgeführt: Sobald der Konstantenspeicher eine fertige Zahl enthält wird diese zusammen mit der nächsten Operation in der Eingabeliste auf den Stack gelegt (push). Steht danach ein weiterer Operator in der Eingabeliste, so ist der vorige Operator einstellig und wird sofort auf dem obersten Register am Stack ausgeführt, und das Ergebnis zusammen mit dem nächsten Operator ersetzt den obersten Stackeintrag. Andernfalls (es handelt sich um einen zweistelligen Operator) wird geprüft, ob der oberste Operator am Stack gleiche oder niedrigere Priorität als der zweite Operator am Stack hat und in diesem Fall der zweite Operator auf die oberen beiden Register am Stack ausgeführt, der zweite Stackeintrag entfernt (pop), und das Ergebnis in das oberste Stack-Register geschrieben. Dieser Schritt wird so oft wie möglich wiederholt. Ist keine Ausführung einer zweistelligen Operation mehr möglich, wird das nächste Argument (über den Konstantenspeicher) von der Eingabeliste gelesen.

Zur Vereinfachung können für den Stack und den Konstantenspeicher (vernünftig gewählte) Maximalgrößen festgelegt werden, bei deren Überschreitung eine Fehlermeldung ausgegeben wird. Vermeiden Sie den Fall, dass Stackeinträge stehen bleiben, obwohl unmöglich mehr darauf zugegriffen werden kann.

Anzeige:

Der Taschenrechner verfügt über eine simulierte Anzeige. Am besten geben Sie jedesmal, wenn die Anzeige verändert wird, eine neue Zeile mit dem aktuellen Inhalt der Anzeige in die Standardausgabe aus. Jede verarbeitete Eingabe (egal ob über die Tastatur oder durch den Operator r) kann die Anzeige verändern. Während im Konstantenspeicher eine Konstante entsteht wird der Konstantenspeicher angezeigt, sonst der Inhalt des Registers im obersten Stackelement. Wenn ein Fehler aufgetreten ist, soll in der Anzeige Error (eventuell mit einer Beschreibung des Fehlers) angezeigt und die Berechnung des Taschenrechners unterbrochen werden, bis eine Eingabe von x oder q (siehe unten) erfolgt.

Operatoren und Befehle:

Folgende Operatoren und Befehle sollen vorhanden sein:

Arithmetische Operatoren (+, -, *, /)

Die zweistelligen Operatoren entsprechen den Grundrechenarten. - kann auch als einstelliger Operator zur Negation verwendet werden.

Speichern s (zweistellig)

Der linke Operand wird im durch den rechten Operanden bestimmten Register gespeichert. Die Nummer des Registers kann durch beliebig komplexe Ausdrücke berechnet werden.

Definieren d (zweistellig)

Der rechte Operand muss ein geklammerter Ausdruck sein, der unausgewertet im durch den (beliebig komplexen) linken Operanden bestimmten Register gespeichert wird.

Lesen r (einstellig)

Falls der Inhalt des durch den (beliebig komplexen) Operanden bestimmten Registers eine Zahl ist, wird das Register nur gelesen (das heißt, das oberste Stackregister durch den gelesenen Registerinhalt ersetzt). Andernfalls (Registerinhalt ist ein nicht ausgewerteter Ausdruck) wird der Registerinhalt an vorderster Stelle in die Eingabeliste gestellt (damit dieser Ausdruck vor allen anderen Eingaben in der Eingabeliste ausgeführt wird) und das Oberste Element vom Stack entfernt.

Abschließen = (einstellig)

Diese Operation bewirkt, dass alle Operationen am Stack abgeschlossen werden. Falls es noch offene Klammerebenen gibt, werden diese implizit geschlossen.

Zurücksetzen x

Dieser Befehl umgeht die Eingabeliste und wird immer sofort ausgeführt. Er löscht den Stack, die Eingabeliste und den Konstantenspeicher und erlaubt, nach einem Fehler weiterzuarbeiten. Die frei verwendbaren Register werden dabei nicht geändert.

Ausschalten q

Auch dieser Befehl umgeht die Eingabeliste und wird immer sofort ausgeführt. Er schaltet den Taschenrechner aus, löscht alle Register und beendet das Programm.

Es werden keine fixen Prioritäten von Operatoren vorgegeben. Wählen Sie sinnvolle Prioritäten.

Testaufgabe:

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

Hinweise zur Testaufgabe:

Der Taschenrechner ist absichtlich sehr einfach und unterstützt kaum Funktionen, die in Computern oder modernen programmierbaren Taschenrechnern üblich sind. Bitte vermeiden Sie es, den Taschenrechner so zu erweitern, dass die Lösung der Testaufgabe vereinfacht wird.

Zur Lösung der Testaufgabe benötigen Sie vermutlich Rekursion sowie bedingte Anweisungen. Beides können Sie mit einigen Tricks am Taschenrechner simulieren. Eine Schlüsselrolle spielt dabei die Möglichkeit der indirekten Adressierung von Registern. Beispielsweise führt der Rechner bei Eingabe von 2d(4r+5r)3d(4r*5r)1rr unterschiedliche Operationen aus, je nach dem ob im Register 1 die Zahl 2 oder 3 steht.

Zusatzaufgabe für Interessierte:

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

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