BuK/IIm10/BuK-Übung08 G1

Wiki-Quelltext dieser Seite.

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

<language>Scheme</language>
== Lösung ==
Die einzelnen Zahlen der Gleichung <math>a*b=c</math> werden wie folgt auf die Variablen verteilt.

<math>
\begin{array}{ccc}
a & \mapsto & R1\\
b & \mapsto & R2 \\
c & \mapsto & R0
\end{array}
</math>

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

<code id="4de36587d26b6">
0  R1 = 2
1  R2 = 3
2  R3 = 1
3  IFZERO R2 GOTO
4  R0 += R1
5  R2 -= R3
6  GOTO 3
7  STOP
</code>

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

== Lösung ==
Der entsprechende Interpreter ist im [http://michael-hielscher.de/compilerwiki/index.php/Compiler_38150_1_Demo CompilerWiki] zu finden.

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

== Lösung ==
Die einzelnen Zahlen der Gleichung <math>a*b=c</math> werden wie folgt auf die Variablen verteilt.

<math>
\begin{array}{ccc}
a & \mapsto & x1\\
b & \mapsto & Konstante \\
c & \mapsto & x0
\end{array}
</math>

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

<code>
x1 = 2;
LOOP x1 DO
x0 := x0 + 3;
END
</code>

= 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:

: <math>x_i := x_j + c</math>
: <math>x_i := x_j - c</math>

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

=== While-Interpreter ===
Unser While-Interpreter besitzt die folgenden Syntaxregeln:

* Variablen: x0, x1, x2,....
* Konstanten: 0, 1, 2, ...
* Trennsymbole: := , ;
* Operstionszeichen: +, -
* Schlüsselwörter: While, !=0, Do, End
* Wertzuweisungen:

: <math>x_i := x_j + c</math>
: <math>x_i := x_j - c</math>

Dafür wurde die folgende Grammatik definiert:

   G = (N, T, P, s)
   N = {S, P, Körper, Operation, Wertzuweisung, Schleife}
   T = {End, Variable, :=, +, Konstante, ;, -, While, !=0, 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 ; While Variable !=0 Do 
      }
   s = S

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

== Lösung ==
Der entsprechende Interpreter ist auch hier im [http://michael-hielscher.de/compilerwiki/index.php/Compiler_38150_2_Demo CompilerWiki] zu finden.