Informatik

Der Computer als System

Der Computer als System

Von der Hochsprache zur Maschinensprache

Struktur und Arbeitsprinzip des von Neumann-Rechners

Die geniale Idee von v. Neumann bestand darin, Programme und Daten in einem gemeinsamen Speicher abzulegen. Dieser Speicher ist linear strukturiert und besteht aus gleich großen, eindeutig identifizierbaren Speicherzellen. Die Identifizierung erfolgt über Adressen, d.h. jeder Operand und jeder Operationscode (Befehl) ist über eine Adresse abruf- und veränderbar. Um an die einzelnen Operanden- und Operationscode zu gelangen, bedarf es eines gleich bleibenden Zyklus, der aus Holen, Dekodieren und Ausführen besteht:
1. Befehl holen: Im Befehlszähler (PC – program counter) steht die Adresse des Befehls, der bearbeitet werden soll. Das Steuerwerk bewirkt nun, dass dieser Befehl zum Befehlsregister gebracht wird.
2. Befehl dekodieren: Im Befehlsdekodierer wird der Befehl analysiert. Durch eine Mikroprogrammsteuerung wird dafür gesorgt, dass die Operanden in die entsprechenden Register gelangen und die zur Bearbeitung notwendigen Steuersignale erzeugt werden.
3. Befehl ausführen: Die Steuersignale werden von den Einheiten (Register, Rechenwerk, usw.) verarbeitet.
4. Befehlszähler ändern: Am Ende der Ausführungsphase wird der Befehlszähler so verändert, dass er die Adresse des nächsten Befehls erhält.
Alle Befehle und Operanden sind binär codiert. Sie bilden das Maschinenprogramm

Reduktion der Hochsprache

Ein Hochsprachenprogramm wie Pascal wird vor seiner Ausführung durch den Compiler in ein Maschinenprogramm übersetzt. Maschinenbefehle richten sich an den Mikroprozessor und gliedern sich in Transportbefehle, Arithmetikbefehle, Vergleiche, Sprungbefehle, Unterprogrammbefehle, Kellerbefehle und Ein- und Ausgabebefehle. Für Maschinenbefehle gibt es zwei Darstellungsarten: die Assemblerschreibweise und die Hexadezimalcodierung. Assembler benutzt Abkürzungen (Mnemonics), die auf die Wirkung der Befehle Bezug nimmt. Zur Umsetzung dieses Mnemonics benutzt man die Hexadezimalcodierung. Als Code für Zahlen wird deren Dualdarstellung benützt, negative Zahlen werden durch ihr Zweierkomplement codiert. Der Prozessors selbst benutzt nur Dualzahlen.
Damit man ein Pascalprogramm in eine maschinentaugliche Form bekommt, muss es in eine adress- bzw. zeilenorientierte Form mit Sprunganweisungen gebracht werden. Rechenanweisungen müssen als Dreiadressbefehle der Form Variable:= Operand1 Operator Operand2 vorliegen. Der Mechanismus der Übersetzung lässt sich durch feste Regeln, sog. Übersetzungsschablonen beschreiben und kann ohne Probleme in Pascal dargestellt werden (Spaghetti-Code). Die zeilenorientierten Programme können dann relativ einfach in Assemblercode umgesetzt werden, wobei natürlich einige Regeln zu beachten sind.

Sprachumfang einer Zwischensprache

Um ein Programm einer Hochsprache in eine maschinenausführbare Form zu bringen, nutzt man eine Zwischensprache. Das Programm in dieser Zwischensprache muss nicht lauffähig sein; es dient als Vorraussetzung für die Übersetzung in Mnemonics. Als Datentyp ist nur Integer erlaubt. Mögliche Operatoren sind +,-, * und DIV sowie die Vergleichsoperatoren <,<=,>,>=, = und <>. Logische Ausdrücke sind nur in der Form Ausdruck1 Vergleichsoperator Ausdruck 2 erlaubt. Zuweisungen erfolgen wie schon erwähnt im „Drei-Adress-Format“. Als Anweisungen sind die Zuweisung „:=“, Read und Write, GOTO n und IF Bedingung THEN GOTO n erlaubt.

Zerlegung von arithmetischen Ausdrücken

Es sei x := c * ( -b ) + ( a – d ) DIV ( 2 * b ). Mit der folgenden Reduktionsschablone kann die Gleichung manuell in das benötigte Drei-Adress-Format umgewandelt werden. Die Anweisung wird dazu wiederholt von links nach rechts gelesen.
1. Man ersetzt negative Vorzeichen durch Subtraktion des Operanden von 0 und streicht positive Vorzeichen: x := c * ( 0 – b ) + ( a – d ) DIV ( 2 * b )
2. Man klammert den Ausdruck möglichst vollständig:
x := ( c * ( 0 – b )) + (( a – d ) DIV ( 2 * b ))
3. Man zerlegt den Term in Teilausdrücke, die nur noch einen Operator enthalten:
x := h1 + h2
h1 := c * h3
h3 := 0 – b
h2 := h4 DIV h5
h4 := a - d
h5 := 2 * b
Die umgekehrte Reihenfolge der Anweisungen ist die Lösung.

Bei der sequentiellen Formelübersetzung wird der Ausdruck nur einmal von links nach rechts gelesen und alle noch nicht ausgewerteten Operanden und Operatoren werden bis zu ihrer Verwendung zwischengespeichert. Als Speicher verwendet man zwei Kellerspeicher: einen Operandenkeller (ODK) zum Speichern von Operanden und Zwischenergebnissen und einen Operatorkeller (OTK) zum Speichern von Operatoren und Klammern.
Es sei x := c * ( -b ) + ( a – d ) DIV ( 2 * b ).
1. Man ersetzt negative Vorzeichen durch Subtraktion des Operanden von 0 und streicht positive Vorzeichen: x := c * ( 0 – b ) + ( a – d ) DIV ( 2 * b ).
2. Erstes Symbol: „x“ kommt in den ODK.
ODK: x OTK:
3. Zweites Symbol: „:=“ kommt in den OTK, da eine Zuweisung noch nicht durchgeführt werden kann.
ODK: x OTK: :=
4. Drittes Symbol: „c“ kommt in den ODK
ODK: c x OTK: :=
5. Viertes Symbol: Da „*“ eine höhere Priorität hat als „:=“, kann eine Zuweisung noch nicht durchgeführt werden. „*“ kommt in den OTK.
ODK: c x OTK: * :=
6. Fünftes Symbol: „(“ Die öffnende Klammer legt den Anfang eines Teilausdrucks fest. Sie wird im OTK gespeichert.
ODK: c x OTK: ( * :=
7. Sechstes Symbol: „0“ wird im ODK festgehalten.
ODK: 0 c x OTK: ( * :=
8. Siebtes Symbol: „-“ wird im OTK gespeichert, da durch die Klammer die Priorität von „*“ unterbrochen wurde.
ODK: 0 c x OTK: - ( * :=
9. Achtes Symbol: „b“ kommt in den ODK.
ODK: b 0 c x OTK: - ( * :=
10. Neuntes Symbol: Eine schließende Klammer zeigt das Ende eines Teilausdrucks an. Es erfolgt die Umsetzung aller Operationen zurück bis zur entsprechenden öffnenden Klammer, die dann aus dem OTK entfernt wird.
h1 := 0 – b
ODK: h1 c x OTK: * :=
11. Zehntes Symbol: „+“ hat eine niedrigere Priorität als „*“ der oberste Operator des OTK. Es wird eine Berechnung mit den beiden letzten Operanden und dem obersten Operator des OTK ausgeführt und das Zwischenergebnis im ODK vermerkt. Danach wird der Operator im OTK festgehalten.
h2 := c * h1
ODK: h2 x OTK: + :=
12. Nächstes Symbol: „(“ wird im OTK abgelegt.
ODK: h2 x OTK: ( + :=
13. Nächstes Symbol: „a“ wird im ODK abgelegt.
ODK: a h2 x OTK: ( + :=
14. Nächstes Symbol: „-“ wird im OTK abgelegt, da es der erste Operator nach einer geöffneten Klammer ist.
ODK: a h2 x OTK: - ( + :=
15. Nächstes Symbol: „d“ wird im ODK abgelegt.
ODK: d a h2 x OTK: - ( + :=
16. Eine schließende Klammer zeigt das Ende eines Teilausdrucks an. Es erfolgt die Umsetzung aller Operationen zurück bis zur entsprechenden öffnenden Klammer, die dann aus dem OTK entfernt wird.
h3 := a – d
ODK: h3 h2 x OTK: + :=
17. Nächstes Symbol: „DIV“ wird im OTK abgelegt, da es eine höhere Priorität als der oberste Operator des OTK hat.
ODK: h3 h2 x OTK: DIV + :=
18. Nächstes Symbol: „(“ wird im OTK abgelegt.
ODK: h3 h2 x OTK: ( DIV + :=
19. Nächstes Symbol: „2“ wird im ODK abgelegt.
ODK: 2 h3 h2 x OTK: ( DIV + :=
20. Nächstes Symbol: „*“ wird im OTK abgelegt, da es der erste Operator nach einer geöffneten Klammer ist.
ODK: 2 h3 h2 x OTK: * ( DIV + :=
21. Nächstes Symbol: „b“ wird im ODK abgelegt.
ODK: b 2 h3 h2 x OTK: * ( DIV + :=
22. Nächstes Symbol: Eine schließende Klammer zeigt das Ende eines Teilausdrucks an. Es erfolgt die Umsetzung aller Operationen zurück bis zur entsprechenden öffnenden Klammer, die dann aus dem OTK entfernt wird.
h4:= 2 * b
ODK: h4 h3 h2 x OTK: DIV + :=
23. Da kein weiteres Symbol ansteht, erfolgt die Ausführung aller noch anstehenden Operationen.
h5 := h3 DIV h4
ODK: h5 h2 x OTK: + :=
h6 := h2 + h5
ODK: h6 x OTK: :=
x := h6
ODK : OTK :
Zusammenfassend hat man dann folgende Befehle:
h1 := 0-b
h2 := c * h1
h3 := a - d
h4 := 2 * b
h5 := h3 DIV h4
h6 := h2 + h5
x := h6

Das oben beschriebene Verfahren lässt sich leicht als Algorithmus formalisieren:
1. Richte zwei Keller ein.
2. Wiederhole
Lies das nächste Zeichen
Falls das Zeichen
ein Operand ist, kellere ihn im ODK ein
ein Operator ist, überprüfe seine Priorität
Falls der Operator keine Priorität gegenüber dem obersten Operator des OTK besitz, werte diesen aus. Speichere den neuen Operator im OTK.
eine öffnende Klammer ist, speichere diese im OTK
eine schließende Klammer ist, führe eine Auswertung aller Operatoren zurück bis zur entsprechenden öffnenden Klammer aus dem OTK.
bis der Ausdruck ganz abgearbeitet wurde
3. Falls der OTK nicht leer ist, werte alle Operatoren aus.

Übersetzungsschablonen

Für die Nutzung der Schablonen sollen folgende Bedingungen gelten:
M1, M2, M3 ... sind Sprungmarken
A1, A2, A3 ... sind Anweisungen
B1, B2, B3 ... sind Bedingungen oder deren Verneinung B1*, B2*, B3*....

Bedingung Verneinung
= <>
<> =
> <=
>= <=
< >=
<= >

1. Regel: IF ... THEN

Pascal reduziertes Pascal
IF B1 THEN A1;
A2;		 IF B1* THEN GOTO M1;
A1;
M1: A2;

2. Regel: IF ... THEN ... ELSE

Pascal reduziertes Pascal
IF B1 THEN A1 ELSE A2;
A3;		 IF B1 THEN GOTO M1;
A2;
GOTO M2;
M1: A1;
M2: A3;

3. Regel: WHILE ... DO

Pascal reduziertes Pascal
WHILE B1 DO A1;
A2:		 M1: IF B1* THEN GOTO M2;
A1;
GOTO M1;
M2: A2;

4. Regel: FOR ... TO

Pascal reduziertes Pascal
FOR i:= a TO z DO A1;
A2;

ist äqivalent zu:

i:=a;
WHILE i <= z DO
BEGIN
A1;
i := i+1;
END;
A2;		 i:=a;
M1: IF i < z THEN GOTO M2;
A1;
i := i+1;
GOTO M1;
M2: A2;

5. Regel: FOR ... DOWNTO

Pascal reduziertes Pascal
FOR i:= a DOWNTO z DO A1;
A2;

ist äqivalent zu:

i:=z;
WHILE i >= a DO
BEGIN
A1;
i := i-1;
END;
A2;		 i:=z;
M1: IF i < z THEN GOTO M2;
A1;
i := i-1;
GOTO M1;
M2: A2;

6. Regel: REPEAT ... UNTIL

Pascal reduziertes Pascal
REPEAT
A1;
UNTIL B1;
A2;		 M1: A1;
IF B1* THEN GOTO M1;
A2;

7. Regel: CASE ... OF

Pascal reduziertes Pascal
CASE n OF
n1: A1;
n2: A2;
n3: A3;
END;
A4;		 IF n=1 THEN GOTO M1;
IF n=2 THEN GOTO M2;
IF n=3 THEN GOTO M3;
GOTO M4;
M1: A1;
GOTO M4;
M2: A2;
GOTO M4;
M3: A3;
M4: A4;

Von der Hochsprache zur Maschinensprache

Um den Prozessor zu programmieren, muss das Pascalprogramm zunächst in ein reduziertes Pascal überführt werden. Dieses reduzierte Pascal wird in Assembler formuliert und anschließend in Maschinensprache umgesetzt. Diese kann dann auf dem Softwarerechner laufen.

Pascal reduziertes Pascal Assembler Adr OP Code/
Operand
procedure TForm1.Button1Click(Sender: TObject);
var a,b,c:integer;
begin
a:= 20;
b:=12;
c:=a+b;
a:=a-b;
edit1.Text:=IntToStr(a)+' '+IntToStr(b)+ ' '+IntTosTr(c);
end;		 var a,b,c:integer;
begin
a:= 20;
b:=12;
c:=a+b;
a:=a-b;
edit1.Text:=IntToStr(a)+' '+IntToStr(b)+ ' '+IntTosTr(c);
end;		 MOV AX,a
ADD AX, b
MOV c, AX
SUB AX,b
MOV a,AX
HALT
a
b
c		 00
01
02
03
04
05
06
07
08		 10 06
20 07
11 08
23 07
11 06
99 00
a
b
c

 

Pascal reduziertes Pascal Assembler Adr OP Code/
Operand
procedure TForm1.Button1Click(Sender: TObject);
var a,b,c:Integer;
begin
a:=StrToInt(edit1.Text);
b:=StrToInt(edit2.Text);
if a>b then c:=a else c:=b;
edit1.Text:=IntToStr(a) + ' ' + IntToStr(b) + ' ' + IntToStr(c);
end;

end.		 label m1,m2;
var a,b,c:Integer;
begin
a:=StrToInt(edit1.Text);
b:=StrToInt(edit2.Text);
if a<=b then goto m2;
c:=a;
goto m1;
m2: c:=b;
m1: edit1.Text:=IntToStr(a) + ' '
+ IntToStr(b) + ' ' + IntToStr(c);
end;		 MOV AX, a
SUB AX, b
JLE m2
MOV AX, a
MOV c, AX
JMP m1
m2:MOV AX, b
MOV c, AX
m1:HALT


 00
01
02
03
04
05
06
07
08
09
0A
0B		 10 09
23 0A
44 06
10 0A
11 0B
40 08
10 0A
11 0B
99 00
a
b
c

 

Pascal reduziertes Pascal Assembler Adr OP Code/
Operand
procedure TForm1.Button1Click(Sender: TObject);
var a,b,t:integer;
begin
a:=StrToInt(edit1.Text);
b:=StrToInt(edit2.Text);
while a <> b do
if a>b
then a:=a-b
else b:=b-a;
t:=a;
edit1.Text:=IntToStr(t);
end;		 label m1,m2,m3,m4;
var a,b,t:integer;
begin
a:=StrToInt(edit1.Text);
b:=StrToInt(edit2.Text);
m1: if a = b then goto m2;
if a>b then goto m3;
b:=b-a;
goto m4;
m3:a:=a-b;
m4:goto m1;
m2: t:=a;
edit1.Text:=IntToStr(t);
end;		 m1:MOV AX,a
SUB AX,b
JEZ m2
MOV AX,a
SUB AX,b
JGZ m3
MOV AX,b
SUB AX,a
MOV b,AX
JMP m4
m3: MOV AX,a
SUB AX,b
MOV a,AX
m4:JMP m1
m2:MOV AX,a
MOV t,AX
HALT


 00
01
02
03
04
05
06
07
08
09
0A
0B
0C
0D
0E
0F
10
11
12
13		 10 11
23 12
41 0E
10 11
23 12
45 0A
10 12
23 11
11 12
40 0D
10 11
23 12
11 11
40 00
10 11
11 13
99 00
a
b
t
V.Berg • Bergisch Gladbach • Impressum • Haftungsausschluss