Notatki do wykładu
Wstęp do programowania
1
1
Maszyny RAM
Maszyna RAM składa się z procesora, pamięci oraz taśmy wejściowej i taśmy wyjściowej. Działanie
RAM polega na wykonywaniu rozkazów programu, który musi być napisany w znanym maszynie języku
- w naszym przypadku - kodzie RAM.
1.1
Elementy maszyny RAM
Procesor - rozpoznaje i wykonuje instrukcje programu; określa też, która instrukcja ma być wykonana
jako następna.
Licznik rozkazów LR - zawiera numer rozkazu, który ma być wykonany jako kolejny.
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 arytmety-
cznych, pośredniczy także w przesyła- niu 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ą daną; po wczytaniu danej, głowica automatycznie
przesuwa się do następnej danej.
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 miejscu, w którym 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ć:
<Etykieta> <Kod rozkazu> <Argument>
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),
1
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. r
i
– rejestr o adresie i, (jego zawartość, też będziemy używać ri lub r(i).
Element rozkazu oznaczony powyżej jako <Argument> może mieć jedną z następujących postaci:
a =
i oznacza r
i
– rejestr o adresie i,
=i oznacza wartość liczby i,
ˆi adresowanie pośrednie; oznacza rejestr, którego adresem jest zawartość rejestru r
i
,
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 7→ Z, v(a) nazywa
się wartością argumentu a:
v(a) =
r(i) jeśli a = i,
i jeśli a = = i,
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.
2
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 ← bAcc/v(a)c
LR ← LR + 1
READ
i, ˆi
v(a) ← zawartość bieżącej klatki na taśmie wejściowej;
głowica przesuwa się o jedną klatkę w prawo,
LR ← LR + 1
WRITE
i, = i, ˆi
v(a) wypisane jest na klatkę taśmy wyjściowej w miejscu
położenia głowicy; głowica przesuwa się o jedną klatkę w
prawo,
LR ← LR + 1
JUMP
e
jako następny jest wykonywany rozkaz poprzedzony etyki-
etą e – skok bezwarunkowy,
LR ← v(e)
JZERO
e
jeżeli Acc = 0, to jako następny jest wykonywany rozkaz
poprzedzony etykietą e; przeciwnie jest wykonywany kolej-
ny rozkaz programu – ”skok przy zerze”,
LR ← v(e) lub
LR ← LR + 1
JGTZ
e
jeżeli Acc > 0, to jako następny jest wykonywany rozkaz
poprzedzony etykietą e; przeciwnie jest wykonywany kolej-
ny rozkaz programu – ”skok przy wiekszym od zera”
LR ← v(e) lub
LR ← LR + 1
HALT
rozkaz zatrzymuje i kończy wykonywanie programu
3