BuK/IIm10/BuK-Übung08 G2

Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
=RAM-Berechenbarkeit=
==Aufgabe==
Zeigen Sie, dass die Multiplikationsfunktion für natürliche Zahlen RAM-berechenbar ist.

==Lösung==

=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 (:). 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:
* Wertzuweisungen: <math>x_i := x_j \pm 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'''

<math>x_{i,j}</math> sind Variablen, <math>c</math> ist eine Konstante (<math>c \in \mathbb{N}_0</math>)

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
BuK/IIm10/BuK-Übung08 G2

Suche
