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 M_i denen jeweils eine Anweisung A_i getrennt durch einen Doppelpunkt (:). Marken, auf die kein GOTO-Befehl verweist, können weggelassen werden.

M_1 : A_1; M_2 : A_2; ...; M_k : A_k

Es stehen 5 verschiedene Anweisungen zur Auswahl:

• Wertzuweisung: x_i := x_j + c
• Wertzuweisung: x_i := x_j - c (x_i := 0, wenn x_j - c < 0)
• unbedingter Sprung: GOTO M_i
• bedingter Sprung: IF x_i = c THEN GOTO M_i
• Stop: HALT

Es gilt:

• x_{i,j} sind Variablen (i,j \in \mathbb{N} \backslash \{0\})
• c ist eine Konstante (c \in \mathbb{N})
• 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 x_1

     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 CompilerWiki getestet werden.