BuK/IIm10/BuK-Übung08 G2

Wiki-Quelltext dieser Seite.

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

==Lösung==
Das folgende Programm berechnet die Multiplikation von 5 und 3. Das Ergebnis steht dann in R0. Alle Zeilen sind durchnummeriert und begonnen wird mit Zeile 1.
<pre>
R0 = 5
R1 = 3
R3 = 1
R2 = R1
IFZERO R2 GOTO 9
R4 += R0
R2 -= R3
GOTO 5
R0 = R4
STOP
</pre>
Werden zu Beginn die Register R0 und R1 mit anderen natürlichen Zahlen belegt, so wird die Multiplikation dieser Zahlen durchgeführt. Die Multiplikationsfunktion ist damit RAM-berechenbar.

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

==Lösung==
Als Erstes wird eine Grammatik mit Hilfe von ''kfG Edit'' entworfen. Die einzelnen Anweisungen werden mit den Regeln ''instr'' abgebildet.
<pre>
P      -> K 
K      -> inst K | EPSILON 
inst   -> R Zahl = R Zahl 
inst -> R Zahl = RR Zahl 
inst -> RR Zahl = R Zahl 
inst -> R Zahl = Zahl
inst -> R Zahl -= R Zahl 
inst -> R Zahl += R Zahl 
inst -> GOTO Zahl
inst -> IFZERO R Zahl GOTO Zahl
inst -> STOP
Zahl -> Digit Zahl | Digit
Digit  -> 0|1|...|9
</pre>
Anschließend wird die Grammatik in VCC exportiert. Hier werden die S-Ausdrücke der einzelnen Regeln hinzugefügt. 
Der Interpreter kann unter [http://michael-hielscher.de/compilerwiki/index.php/Compiler_12345_Demo] getestet werden.

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

==Lösung==
Um die LOOP-berechenbarkeit für die Multiplikationsfunktion zu zeigen, muss ein LOOP-Programm angegeben werden, dass die Multiplikation ausführt. Ein solches Program befindet sich im nächsten Abschnitt.

=LOOP- und WHILE-Interpreter=

==Aufgabe==
Verwenden Sie VCC aus AtoCC, um einen Interpreter fur LOOP-Programme zu ent-
wickeln. Erweitern Sie im nachsten Schritt die LOOP-Sprache durch das WHILE-
Sprachelement, um einen Interpreter fur WHILE-Programme zu erhalten.

==Lösung==

LOOP-Programme können aus folgenden verschiedenen Anweisungen gebildet werden:

* Zählschleife
* Wertzuweisung
** mit Plus-Operation
** mit Minus-Operation

Weiterhin gelten folgende Regeln:

* Zwei, mit einem Semikolon verkettete LOOP-Programme, bilden wieder ein LOOP-Programm.
* Benötigte Variablen werden zu Beginn bereitgestellt.
* Das Endergebnis steht in der Variable x0

Daraus wurde mit kfGEdit die Grammatik erstellt:

 S -> ZEILEN
 ZEILEN -> ANWEISUNG mehrZEILEN
 mehrZEILEN -> ; ZEILEN | EPSILON
 
 ANWEISUNG -> VAR := VAR WZ | LOOPPrgm | WhilePrgm
 
 WZ -> OP ZAHL | EPSILON
 LOOPPrgm -> LOOP VAR DO ZEILEN END
 WhilePrgm -> WHILE ISZERO VAR DO ZEILEN END
 VAR -> x ZAHL
 OP -> + | -

Der Interpreter, welcher mit VCC aus [http://atocc.de/ AtoCC] entwickelt wurde, kann im [http://michael-hielscher.de/compilerwiki/index.php/Compiler_37903_Demo CompilerWiki] mit verschiedenen Aufrufen getestet werden. Auch die <b>WHILE-Aufrufe</b> sind dort mit enthalten.

=GOTO-Interpreter=
==Aufgabe==
Verwenden Sie VCC aus AtoCC, um einen Interpreter für GOTO-Programme zu entwickeln.
==Lösung==
Ein GOTO-Programm besteht aus Marken <math>M_i</math>, denen jeweils eine Anweisung <math>A_i</math> getrennt durch einen Doppelpunkt folgt. Marken, auf die kein GOTO-Befehl verweist, können weggelassen werden.

<blockquote><math>M_1 : A_1; M_2 : A_2; ...; M_k : A_k</math></blockquote>

Es stehen 5 verschiedene Anweisungen zur Auswahl:
* Wertzuweisung: <math>x_i := x_j + c</math> 
* Wertzuweisung: <math>x_i := x_j - c</math> (<math>x_i := 0</math>, wenn <math>x_j - c < 0</math>)
* unbedingter Sprung: '''GOTO <math>M_i</math>'''
* bedingter Sprung: '''IF <math>x_i = c</math> THEN GOTO <math>M_i</math>'''
* Stop: '''HALT'''
Es gilt:
*<math>x_{i,j}</math> sind Variablen (<math>i,j \in \mathbb{N} \backslash \{0\}</math>)
*<math>c</math> ist eine Konstante (<math>c \in \mathbb{N}</math>)
*Eine Variable, der kein Wert explizit zugewiesen wurde, hat den Wert 0.

Ein GOTO-Programm zur Berechnung von 3 * 5. Das Ergebnis befindet sich in <math>x_1</math>

      x2 := x2 + 3
 M1 : IF x2 = 0 THEN GOTO M2
      x1 := x1 + 5
      x2 := x2 - 1
      GOTO M1
 M2 : HALT

Für die Entwicklung des Interpreters mit VCC haben wir zuerst mit kfG-Edit diese Grammatik erstellt.

 G = (N, T, P, s)
 N = {P, LINES, LINE, MARKER, INSTRUCTION, ASSIGNMENT, VARIABLE, OPERATOR, JUMP, IF_THEN}
 T = {:, M, KONSTANTE, HALT, :=, X, +, -, GOTO, IF, =, THEN}
 P = {
   P           -> LINES 
   LINES       -> LINE | LINE LINES 
   LINE        -> MARKER : INSTRUCTION 
                | INSTRUCTION 
   MARKER      -> M KONSTANTE 
   INSTRUCTION -> HALT | IF_THEN | ASSIGNMENT | JUMP 
   ASSIGNMENT  -> VARIABLE := VARIABLE OPERATOR KONSTANTE 
   VARIABLE    -> X KONSTANTE 
   OPERATOR    -> + | - 
   JUMP        -> GOTO MARKER 
   IF_THEN     -> IF VARIABLE = KONSTANTE THEN JUMP 
 }
 s = P

Der daraufhin entwickelte Interpreter kann im [http://michael-hielscher.de/compilerwiki/index.php/Compiler_30816_Demo CompilerWiki] getestet werden.