Notatki do wykładu
Wstęp do programowania
(2)
1 Maszyny RAM
Maszyna RAM składa się z procesora, pamięci oraz taśmy wejściowej i taśmy wyjściowej. Dzi-
ałanie RAM polega na wykonywaniu rozkazów programu, który musi być napisany w znanym
maszynie języku - w naszym przypadku - kodzie RAM. Schemat maszyny RAM przedstawia
Rysunek 1.
Taśma
wejściowa
Acc
0
r(1)
1
r(2)
2
PROCESOR
r(3)
3
Rejestry
...
P .
.
R
.
O
G
P
Licznik
R
A
rozkazów
A
M
M
I


Ć
Taśma
wyjściowa
Klatki
Rysunek 1: Schemat maszyny RAM.
1.1 Elementy maszyny RAM
Procesor - rozpoznaje i wykonuje instrukcje programu zwane rozkazami; określa też, który
rozkaz ma być wykonany jako następny.
Licznik rozkazów LR - zawiera numer rozkazu, który ma być wykonany jako kolejny.
1
Pamięć - ciąg rejestrów ponumerowanych kolejnymi liczbami naturalnymi, liczba numerująca
rejestr nazywa się jego adresem; każdy rejestr może przechowywać dowolną liczbę całkowitą.
Akumulator Acc - rejestr pamięci o adresie 0, przystosowany do wykonywania operacji aryt-
metycznych, pośredniczy także w przesyłaniu danych pomiędzy rejestrami.
Taśma wejściowa - podzielona na klatki, służy do przechowywania danych dla programu;
wyposażona jest w głowicę czytającą, która wskazuje bieżącą klatkę; po wczytaniu danej z
klatki, głowica automatycznie przesuwa się do następnej klatki.
Taśma wyjściowa - podzielona na klatki, służy do zapisywania wyników działania programu;
wyposażona jest w głowicę piszącą; wyprowadzany wynik jest pisany w klatce, w której znajduje
się głowica, po czym automatycznie przesuwa się ona dalej.
1.2 Program w kodzie RAM
Program jest to ciąg ponumerowanych rozkazów. Każdy rozkaz ma postać:

Rozkazy można podzielić na grupy:
1. rozkazy przesyłania:
LOAD (pobranie do akumulatora),
STORE (przesłanie z akumulatora),
2. operacje arytmetyczne:
ADD (dodawanie),
SUB (odejmowanie),
MULT (mnożenie),
DIV (dzielenie całkowite),
3. rozkazy wejścia/wyjścia:
READ (czytanie danej),
WRITE (pisanie wyniku),
4. rozkazy skoków:
JUMP (skok bezwarunkowy),
JZERO (skok jeśli 0),
JGTZ (skok jeśli większe niż 0),
5. rozkaz zatrzymania:HALT (zatrzymanie programu)
Przyjmijmy oznaczenia:
1. i, j, n  liczba całkowita,
2. a  argument
3. e  etykieta (nazwa, ciąg liter lub cyfr),
4. ri  rejestr o adresie i, (jego zawartość, też będziemy używać ri lub r(i).
2
Element rozkazu oznaczony powyżej jako może mieć jedną z następujących
postaci:
ńł
i oznacza ri  rejestr o adresie i,
�ł
�ł
�ł
=i oznacza wartość liczby i,
a =
Ći adresowanie pośrednie; oznacza rejestr, którego adresem jest zawartość rejestru ri,
�ł
�ł
ół
e oznacza numer rozkazu poprzedzonego etykietą e.
1.3 Wykonanie programu
Wykonanie programu maszyny RAM polega na kolejnym wykonywaniu kolejnych rozkazów
programu.
Oznaczmy przez r funkcję zwaną mapą pamięci; r(i) jest liczbą całkowitą umieszczoną w
rejestrze i. W trakcie wykonywania programu funkcja r może się zmieniać, gdyż zmieniają
się zawartości rejestrów. Początkowo, r(i) = 0 dla i = 0, 1, 2, . . ., taśma wyjściowa jest pusta,
a licznik rozkazów wskazuje na pierwszy rozkaz programu: LR = 1. Zdefiniujmy funkcję
v : Zbiór argumentów Z, v(a) nazywa się wartością argumentu a:
ńł
r(i) jeśli a = i,
�ł
�ł
�ł
i jeśli a = = i,
v(a) =
r(r(i) jeśli a =Ći,
�ł
�ł
ół
nr rozkazu poprzedzonego etykietą jeśli a = e.
Poniższa tabela definiuje znaczenie (sposób wykonania) rozkazów.
3
Rozkaz Arg. a Wykonanie LR
LOAD i, = i,Ći Acc �! v(a) LR �! LR + 1
STORE i,Ći v(a) �! Acc LR �! LR + 1
ADD i, = i,Ći Acc �! Acc + v(a) LR �! LR + 1
SUB i, = i,Ći Acc �! Acc - v(a) LR �! LR + 1
MULT i, = i,Ći Acc �! Acc " v(a) LR �! LR + 1
DIV i, = i,Ći Acc �! Acc/v(a) LR �! LR + 1
READ i,Ći v(a) �! zawartość bieżącej klatki na taśmie wejściowej; LR �! LR + 1
głowica przesuwa się o jedną klatkę w prawo,
WRITE i, = i,Ći v(a) wypisane jest na klatkę taśmy wyjściowej w LR �! LR + 1
miejscu położenia głowicy; głowica przesuwa się o
jedną klatkę w prawo,
JUMP e jako następny jest wykonywany rozkaz poprzedzony LR �! v(e)
etykietą e  skok bezwarunkowy,
JZERO e jeżeli Acc = 0, to jako następny jest wykony- LR �! v(e)
wany rozkaz poprzedzony etykietą e; przeciwnie jest lub LR �!
wykonywany kolejny rozkaz programu   skok przy LR + 1
zerze ,
JGTZ e jeżeli Acc > 0, to jako następny jest wykony- LR �! v(e)
wany rozkaz poprzedzony etykietą e; przeciwnie jest lub LR �!
wykonywany kolejny rozkaz programu   skok przy LR + 1
wiekszym od zera
HALT rozkaz zatrzymuje i kończy wykonywanie programu
4