Aus ProgrammingWiki

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

RAM-Berechenbarkeit

Aufgabenstellung

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

Lösung

Die einzelnen Zahlen der Gleichung werden wie folgt auf die Variablen verteilt.

Somit kann für das Beispiel und dann folgendes Programm angegeben werden.

0 R1 = 2 1 R2 = 3 2 R3 = 1 3 IFZERO R2 GOTO 4 R0 += R1 5 R2 -= R3 6 GOTO 3 7 STOP

RAM-Interpreter

Aufgabenstellung

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

Lösung

Der entsprechende Interpreter ist im 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 werden wie folgt auf die Variablen verteilt.

Somit kann für das Beispiel und dann folgendes Programm angegeben werden.

x1 = 2; LOOP x1 DO x0 := x0 + 3; END

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:

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:

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 CompilerWiki zu finden.