Aus ProgrammingWiki

Inhaltsverzeichnis 1 RAM-Berechenbarkeit 1.1 Aufgabe 1.2 Lösung 2 RAM-Interpreter 2.1 Aufgabe 2.2 Lösung 3 LOOP-Berechenbarkeit 3.1 Aufgabe 3.2 Lösung 4 LOOP- und WHILE-Interpreter 4.1 Aufgabe 4.2 Lösung 5 GOTO-Interpreter 5.1 Aufgabe 5.2 Lösung

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.

R0 = 5
R1 = 3
R3 = 1
R2 = R1
IFZERO R2 GOTO 9
R4 += R0
R2 -= R3
GOTO 5
R0 = R4
STOP

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.

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

Anschließend wird die Grammatik in VCC exportiert. Hier werden die S-Ausdrücke der einzelnen Regeln hinzugefügt. Der Interpreter kann unter [1] 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 AtoCC entwickelt wurde, kann im CompilerWiki mit verschiedenen Aufrufen getestet werden. Auch die WHILE-Aufrufe 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 , denen jeweils eine Anweisung getrennt durch einen Doppelpunkt folgt. Marken, auf die kein GOTO-Befehl verweist, können weggelassen werden.

Es stehen 5 verschiedene Anweisungen zur Auswahl:

• Wertzuweisung:
• Wertzuweisung: (, wenn )
• unbedingter Sprung: GOTO
• bedingter Sprung: IF THEN GOTO
• Stop: HALT

Es gilt:

• sind Variablen ()
• ist eine Konstante ()
• 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

     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.