Prof. Dr. Ralf Der - Institut für Informatik - Universität Leipzig

Übungsblätter zur Vorlesung Digitale Informationsverarbeitung

(Magister)

Wintersemester 2002/03 - Serie 4

Für die ersten drei  Aufgaben können Sie die Simulation simneu eines Ein-Adress-Rechners verwenden, die als C-Quellprogramm heruntergeladen werden kann.

  1. Schreiben Sie ein Programm für den in der Vorlesung vorgestellten Ein-Adress-Rechner zur Berechnung der Fakultät n!=1 * 2 * … * n. (4 Pkte.)
    Protokollieren Sie die Veränderung der Speicherbelegung bei für den Fall n = 3.  (1 Pkte.)
  2. Schreiben Sie ein Programm für den in der Vorlesung vorgestellten Ein-Adress-Rechner zur Berechnung der Funktion f(n), die bei Eingabe von n die n-te Fibonaccizahl zurückgibt. Die Fibonaccizahlen sind rekursiv definiert, es ist f(1) = 1, f(2) = 1 und für n>2 gilt f(n+1) = f(n-1) + f(n). (4 Pkte.)
    Protokollieren Sie die Veränderung der Speicherbelegung für n = 5.  (1 Pkte.)
  3. Schreiben Sie ein Programm für den in der Vorlesung vorgestellten Ein-Adress-Rechner der die Reihenfolge der Elemente eines Feldes der Länge n invertiert. Nach Abarbeiten des Programms soll das Feld (in umgekehrter Reihenfolge der Elemente) den gleichen Speicherbereich belegen wie vorher.  Für die indirekte Adressierung verwenden Sie, dass das Befehlswort als natürliche Zahl kodiert wird. Diese hat wie in der Vorlesung besprochen den Wert A*16 + O  wobei A die Adresse des zweiten Operanden und O der Code der Operation sei. Verwenden Sie für wiederkehrende Teilfunktionen die Unterprogrammtechnik. (8 Pkte.)
  4. G sei eine Grammatik mit Startsymbol <S>, der Menge der Nichtterminalsymbole N={<S>,<A>,<B>}, der Menge der Terminalsymbole T={a,b} und den Produktionsregeln<S> -> a<B>, <A> -> a, <A> -> a<S>, <A> -> b<A><A> , <S> -> b<A>, <B> -> b, <B> -> b<S>, <B> -> a<B><B>
    Aufgaben: