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