BuK-Übung08 G1

Aus ProgrammingWiki
< BuK < IIm10
Archivierte Version vom 2011-05-30T10:45:04+00:00. Aktuelle Version

Inhaltsverzeichnis

RAM-Berechenbarkeit

Aufgabenstellung

Zeigen Sie, dass die Multiplikationsfunktion für natürliche Zahlen RAM-berechenbar ist.


Lösung

Die einzelnen Zahlen der Gleichung a*b=c werden wie folgt auf die Variablen verteilt.

\begin{array}{ccc} a & \mapsto & R1\\ b & \mapsto & R2 \\ c & \mapsto & R0 \end{array}

Somit kann für das Beispiel a=2 und b=3 dann folgendes Programm angegeben werden.

RAM-Interpreter

Aufgabenstellung

Verwenden Sie VCC aus AtoCC, um einen Interpreter für RAM-Programme zu entwickeln.

Lösung

LOOP-Berechenbarkeit

Aufgabenstellung

Zeigen Sie, dass die Multiplikationsfunktion für natürliche Zahlen LOOP-berechenbar ist.

Lösung

Die einzelnen Zahlen der Gleichung a*b=c werden wie folgt auf die Variablen verteilt.

\begin{array}{ccc} a & \mapsto & x1\\ b & \mapsto & Konstante \\ c & \mapsto & x0 \end{array}

Somit kann für das Beispiel a=2 und b=3 dann folgendes Programm angegeben werden.

LOOP- und WHILE-Interpreter

Aufgabenstellung

Verwenden Sie VCC aus AtoCC, um einen Interpreter für LOOP-Programme zu entwickeln. Erweitern Sie im nächsten Schritt die LOOP-Sprache durch das WHILE-Sprachelement, um einen Interpreter für WHILE-Programme zu erhalten.

Lösung

LOOP-Interpreter

Ein LOOP-Interpreter besitzt die folgenden Syntaxregeln:

  • Variablen: x0, x1, x2,....
  • Konstanten: 0, 1, 2, ...
  • Trennsymbole: := , ;
  • Operstionszeichen: +, -
  • Schlüsselwörter: Loop, Do, End
  • Wertzuweisungen:
x_i := x_j + c
x_i := x_j - c

Dafür wurde die folgende Grammatik definiert:

G = (N, T, P, s) N = {S, P, Körper, Operation, Wertzuweisung, Schleife} T = {End, Variable, :=, +, Konstante, ;, -, Loop, Do} P = {

  S             -> P End 
  P             -> Körper | Körper P 
  Körper        -> Operation 
                 | Wertzuweisung 
                 | Schleife Operation 
                 | Schleife Wertzuweisung 
  Operation     -> Variable := Variable + Konstante ; 
                 | Variable := Variable - Konstante ; 
  Wertzuweisung -> Variable := Konstante ; 
                 | Variable := Variable ; 
  Schleife      -> Variable := Konstante ; Loop Variable Do

} s = S

GOTO-Interpreter

Aufgabenstellung

Verwenden Sie VCC aus AtoCC, um einen Interpreter für GOTO-Programme zu entwickeln.

Lösung