Programmiersprachen
LVA 185.208, VU, 3 Ects, 2012 S

1. Übungsaufgabe

Aufgabe:

Entwickeln Sie in einer beliebigen Programmiersprache Ihrer Wahl eine Simulation eines programmierbaren Taschenrechners entsprechend folgenden Spezifikationen und lösen Sie damit die weiter unten beschriebene Testaufgabe.

Eingaben in den Taschenrechner:

Eingaben erfolgen in Postfix-Notation (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. 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 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 - auf 1 und 14.

Neben Zahlen sind auch Zeichen als Daten verwendbar (am besten als ASCII-Zeichen, aber andere Codierungen sind ebenso erlaubt). So stehen a und b einfach nur für die entsprechenden Zeichen, und \n steht für Newline, \t für den Tabulator und so weiter. Durch Voranstellen von \ verlieren Operatoren, eckige Klammern (siehe unten) und Ziffern ihre üblichen Bedeutungen und werden als Zeichen betrachtet. Jedoch wird intern nicht zwischen Zahlen und Zeichen unterschieden. Beispielsweise sind A und 65 unterschiedliche externe Darstellungen derselben Zahl.

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 @ selbst als Operator gesehen, der ein Argument mit 2 multipliziert. Der Ausdruck 3[2*]@ wird zu 3 2* bzw. 6 ausgewertet.

Architektur:

Der Taschenrechner besteht aus folgenden Teilen:

Tastatur und Display

Über die Tastatur werden Programme und Daten eingegeben. Das Display zeigt an, was über die Tastatur eingetippt bzw. vom Programm ausgegeben wird.

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.

Eingabeliste

Sie enthält die noch nicht abgearbeiteten Eingaben. Alle Eingaben werden zeichenweise in der Reihenfolge in dieser Liste abgearbeitet. Neben direkten Eingaben über die Tastatur des Taschenrechners werden auch durch den Operator @ Eingaben in diese Liste geschrieben.

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

Operationen:

Die Bedeutung folgender Eingaben ist vordefiniert:

Spezielle Zeichen \...:

Der ASCII-Code (bzw. der Code in der entsprechenden Codierung) des auf \ folgenden Zeichens wird auf den Stack gelegt. Für \n, \t, etc. wird jedoch der Code für Newline, Tabulator, etc. auf den Stack gelegt.

Ziffern 0 bis 9:

Alle direkt hintereinander stehenden Ziffern in der Eingabeliste werden zu einer Zahl zusammengesetzt, die als neuer Eintrag auf den Stack gelegt wird.

[ und ]:

Die öffnende Klammer bewirkt, dass alle folgenden Eingaben bis zur entsprechenden schließenden Klammer als Einheit betrachtet werden, die (beispielsweise in Form eines Strings) als neuer Eintrag auf den Stack gelegt wird. Klammern können geschachtelt sein.

White-Space (Leerzeichen, Tabulator, Newline, Return ohne \ davor):

Diese Eingaben sind zur Trennung zweier Zahlen sinnvoll, haben sonst aber keine Bedeutung und werden ignoriert.

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

Diese zweistelligen Operatoren entsprechen den Grundrechnungen (mit % zur Berechnung des Divisionsrestes) und einfachen Vergleichen, wobei & bzw. | das logische UND bzw. ODER darstellen. Diese Operatoren nehmen die zwei obersten Elemente vom Stack und legen das Ergebnis auf den Stack. Wenn ein Argument keine Zahl sondern ein geklammerter Ausdruck ist, soll ein Fehler gemeldet werden, ebenso wenn ein Argument von & bzw. | kein Wahrheitswert (0 steht für wahr und 1 für falsch) ist. Ausgenommen hiervon ist nur =: Wenn = auf zwei gleiche geklammerte Ausdrücke oder zwei gleiche Zahlen angewandt wird, soll als Ergebnis 0 (wahr) zurückgegeben werden, sonst 1 (falsch). Bei nichtassoziativen Operationen ist auf die Reihenfolge der Argumente zu achten: 4 2- und 4 2/ und 2 4% sollen jeweils 2 ergeben, und 4 2> und 2 4< sollen wahr liefern. Ein Fehler soll gemeldet werden, wenn das zweite Argument von / oder % gleich 0 ist.

Vorzeichenümkehr ~:

ist nur auf Zahlen definiert.

Kopieren !:

ersetzt das oberste Element n am Stack durch eine Kopie des n-ten Elements am Stack (vom Top-of-Stack aus gezählt). Eine Fehlermeldung wird ausgegeben, wenn n keine positive Zahl ist oder der Stack nicht ausreichend viele Elemente enthält.

Löschen #:

nimmt das oberste Element n vom Stack und entfernt zusätzlich das n-te Element vom Stack. Eine Fehlermeldung wird ausgegeben, wenn n keine positive Zahl ist oder der Stack nicht ausreichend viele Elemente enthält.

Anwenden @:

nimmt das oberste Element vom Stack. Ist das Argument ein geklammerter Ausdruck, dann wird dieser (mit den umschließenden Klammern durch White-Space ersetzt) an vorderster Stelle in die Eingabeliste geschrieben, damit die darin enthaltenen Eingaben als nächste abgearbeitet werden. Ist das Argument eine Zahl, dann hat @ keinerlei Auswirkung; das Argument wird wieder unverändert auf den Stack gelegt.

Textausgabe ":

nimmt das oberste Element vom Stack und gibt es im Display aus. Falls das Element eine Zahl ist, die ein Zeichen representiert, dann wird das Zeichen ausgegeben. Wenn die Zahl kein Zeichen darstellt, kommt es zu einer Fehlermeldung. Falls das Element ein geklammerter Ausdruck ist, wird dieser Ausdruck ohne umschließende Klammern ausgegeben.

Zahlenausgabe ':

nimmt das oberste Element vom Stack und gibt es im Display aus. Falls das Element eine Zahl ist, dann wird diese Zahl als Ziffernfolge (eventuell mit vorangestelltem Vorzeichen) ausgegeben. Falls es ein geklammerter Ausdruck ist, wird der Ausdruck zusammen mit den umschließenden Klammern ausgegeben.

Einlesen ?:

unterbricht den normalen Eingabemodus (in dem Eingaben über die Tastatur in die Eingabeliste kommen) und startet den Einlesemodus, in dem Eingaben über die Tastatur in einem neuen geklammerten Ausdruck abgelegt werden. Der Einlesemodus endet durch Eintippen von Enter bzw.\ Return. Alle weiteren Eingaben kommen danach wieder in die Eingabeliste. Der im Einlesemodus erzeugte geklammerte Ausdruck wird (nach Hinzufügen umschließender eckiger Klammern) auf den Stack gelegt.

Beispiele:

Einige Beispiele sollen die Verwendung der 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 ^). Pfeile zwischen solchen Zustandsbeschreibungen zeigen Zustandsänderungen durch Ausführung von Operationen an.

Das erste Beispiel zeigt eine bedingte Anweisung: Auf dem Stack wird 0 (wahr) oder 1 (falsch) erwartet. Abhängig davon soll der eine oder andere geklammerte Ausdruck ausgewertet werden. Wir legen zuerst den Ausdruck für den wahr-Zweig [9] und dann den für den falsch-Zweig [9~] auf den Stack und führen einen Ausdruck [4!5#2+#@] aus, der die eigentliche bedingte Anweisung darstellt. Die folgenden Abarbeitungsschritte zeigen, was passiert, wenn am Stack zuvor 0 gelegen ist:

    0 ^[9][9~][4!5#2+#@]@
--> 0 [9] ^[9~][4!5#2+#@]@
--> 0 [9] [9~] ^[4!5#2+#@]@
--> 0 [9] [9~] [4!5#2+#@] ^@
--> 0 [9] [9~] ^4!5#2+#@ 
--> 0 [9] [9~] 4 ^!5#2+#@ 
--> 0 [9] [9~] 0 ^5#2+#@ 
--> 0 [9] [9~] 0 5 ^#2+#@ 
--> [9] [9~] 0 ^2+#@ 
--> [9] [9~] 0 2 ^+#@ 
--> [9] [9~] 2 ^#@ 
--> [9] ^@ 
--> ^ 9  
--> 9 ^

Das nächste Beispiel zeigt anhand der Berechnung von 3 Faktorielle, wie man rekursive Routinen realisieren kann. Zur Vereinfachung kürzen wir den Ausdruck [3!3!1-2!1=[]5!C@3#*] durch A ab, wobei C für den Ausdruck [4!5#2+#@] aus dem vorigen Beispiel steht. Beachten Sie, dass A und C hier nur zur Vereinfachung der Lesbarkeit dient. Im Taschenrechner sollte statt A und C jeweils der entsprechende geklammerte Ausdruck vorkommen.

    3 ^A3!4#3!@3#
--> 3 A ^3!4#3!@3#
--> 3 A 3 ^!4#3!@3#
--> 3 A 3 ^4#3!@3#
--> 3 A 3 4 ^#3!@3#
--> A 3 ^3!@3#
--> A 3 3 ^!@3#
--> A 3 A ^@3#
--> A 3 ^ 3!3!1-2!1=[]5!C@3#* 3#
--> A 3 3 ^!3!1-2!1=[]5!C@3#* 3#
--> A 3 A ^3!1-2!1=[]5!C@3#* 3#
--> A 3 A 3 ^!1-2!1=[]5!C@3#* 3#
--> A 3 A 3 ^1-2!1=[]5!C@3#* 3#
--> A 3 A 3 1 ^-2!1=[]5!C@3#* 3#
--> A 3 A 2 ^2!1=[]5!C@3#* 3#
--> A 3 A 2 2 ^!1=[]5!C@3#* 3#
--> A 3 A 2 2 ^1=[]5!C@3#* 3#
--> A 3 A 2 2 1 ^=[]5!C@3#* 3#
--> A 3 A 2 1 ^[]5!C@3#* 3#
--> A 3 A 2 1 [] ^5!C@3#* 3#
--> A 3 A 2 1 [] 5 ^!C@3#* 3#
--> A 3 A 2 1 [] A ^C@3#* 3#
--> A 3 A 2 1 [] A C ^@3#* 3#
...
--> A 3 A 2 A ^@ 3#* 3#
--> A 3 A 2 ^ 3!3!1-2!1=[]5!C@3#* 3#* 3#
--> A 3 A 2 3 ^!3!1-2!1=[]5!C@3#* 3#* 3#
--> A 3 A 2 A ^3!1-2!1=[]5!C@3#* 3#* 3#
--> A 3 A 2 A 3 ^!1-2!1=[]5!C@3#* 3#* 3#
--> A 3 A 2 A 2 ^1-2!1=[]5!C@3#* 3#* 3#
--> A 3 A 2 A 2 1 ^-2!1=[]5!C@3#* 3#* 3#
--> A 3 A 2 A 1 ^2!1=[]5!C@3#* 3#* 3#
--> A 3 A 2 A 1 2 ^!1=[]5!C@3#* 3#* 3#
--> A 3 A 2 A 1 1 ^1=[]5!C@3#* 3#* 3#
--> A 3 A 2 A 1 1 1 ^=[]5!C@3#* 3#* 3#
--> A 3 A 2 A 1 0 ^[]5!C@3#* 3#* 3#
--> A 3 A 2 A 1 0 [] ^5!C@3#* 3#* 3#
--> A 3 A 2 A 1 0 [] 5 ^!C@3#* 3#* 3#
--> A 3 A 2 A 1 0 [] A ^C@3#* 3#* 3#
--> A 3 A 2 A 1 0 [] A C ^@3#* 3#* 3#
...
--> A 3 A 2 A 1 [] ^@ 3#* 3#* 3#
--> A 3 A 2 A 1 ^ 3#* 3#* 3#
--> A 3 A 2 A 1 3 ^#* 3#* 3#
--> A 3 A 2 1 ^* 3#* 3#
--> A 3 A 2 ^ 3#* 3#
--> A 3 A 2 3 ^#* 3#
--> A 3 2 ^* 3#
--> A 6 ^ 3#
--> A 6 3 ^#
--> 6 ^

Die Ein- und Ausgabe sollte keine allzugroßen Schwierigkeiten bereiten. Beispielsweise soll der Ausdruck [\n"E"i"n"g"a"b"e":"\ "?@'] zunächst in einer neuen Zeile am Display Eingabe: anzeigen, auf eine Eingabe warten, den eingelesenen Ausdruck ausführen und schließlich das Ergebnis (oberstes Stackelement) ausgeben. Der Ausdruck [[\nEingabe:\ ]"?@'] sollte genau dasselbe machen.

Testaufgabe:

Diese Testaufgabe ist unbedingt durchzuführen: Entwerfen Sie (zum Testen des Taschenrechners) einen möglichst kurzen und effizienten Ausdruck der entscheidet, ob eine über die Tastatur eingelesene Zahl eine Primzahl ist oder nicht und das Ergebnis in lesbarer Form am Display ausgibt. Testen Sie mit mehreren, auch größeren Zahlen (bis zu 1000).

Praktischer Hinweis: Zum Programmieren bzw. Starten des Taschenrechners sind lange und komplizierte Ausdrücke einzugeben. Am einfachsten ist dies zu erledigen, wenn als Display und zur Eingabe eine einfache Textkonsole verwendet wird. Dann kann man Programme rasch durch Copy-and-Paste eingeben.

Zusatzaufgaben für Interessierte:

Es stellt sich die Frage, ob man mit diesem Taschenrechner wirklich alles Programmieren kann. Ist es möglich, damit eine Turing-Maschine zu bauen? Die Lösung dieser Zusatzaufgaben ist nicht verpflichtend und hat keinen Einfluß auf die Beurteilung.