Zásobníkový počítač
Zásobníkový počítač je výpočetní stroj pracující pouze s celými čísly a oproti běžným počítačům má velká omezení v práci s paměťovými buňkami. I když má paměť dostatečně velkou, tudíž vyhovující, je ovšem zpracována a organizována zásobníkovým způsobem.
Charakteristika zásobníkového počítače
Charakteristický rys zásobníku je ten, že má neomezenou hloubku a ukládají se do něj celá čísla. Tato čísla se v něm uchovávají v tom pořadí, v jakém do něj byla uložena. Zároveň to číslo, které je do zásobníku uloženo je umístěno na vrcholu zásobníku a tudíž jediné způsobilé a dostupné pro čtení nebo mazání. Po odstranění toho čísla ze zásobníku se dostává na vrchol číslo uložené pod ním. Tak se děje do plného vyprázdnění zásobníku. Důležitý je fakt, že na začátku je zásobník zcela prázdný.
Kromě zásobníkové paměti má počítač k dispozici i jeden pracovní registr procesoru, kam si může uložit jedno celé číslo. V tomto registru lze provádět základní celočíselné aritmetické operace. Registr slouží také ke čtení ze vstupu nebo zápisem, resp. výpisem, na výstup.
Jednoduché příkazy
Programovací jazyk zásobníkového počítače obsahuje základní příkazy pro elementární operace:
- IN – čtení ze vstupu a uložení do registru
- OUT – výpis na výstup, registr nezměněn
- CONST n – do registru se uloží n
- PUSH – číslo z registru uloženo do zásobníku
- POP – odstranění položky zásobníku (prázdný zásobník = chyba)
- TOP – uložení ze zásobníku do registru, zásobník nezměněn
- EXCH – záměna čísel v registru a na vrcholu zásobníku
Základní aritmetické operace
- ADD – k číslu v registru se uloží číslo z vrcholu zásobníku (sčítání)
- SUB – od čísla v registru se odečte číslo z vrcholu zásobníku (odčítání)
- MUL – číslo v registru se vynásobí číslem z vrcholu zásobníku (násobení)
- DIV – číslo v registru se vydělí číslem z vrcholu zásobníku (dělení)
Testování podmínek
Zásobníkový počítač může provádět testy podmínek nebo jejich negací. Lze je využít pouze v místě podmínky složeného příkazu.
- ZERO – číslo v registru rovno nule
- POS – číslo v registru je kladné
- NEG – číslo v registru je záporné
- EMPTY – zásobník je prázdný
- EOF – end of file (žádné číslo na vstupu)
Negaci zapíšeme přidáním slova NOT před podmínku.
Složené příkazy
Program zásobníkového počítače je tvořen posloupností příkazů. Složené příkazy se vytváří pomocí následujících řídících konstrukcí:
- IF podmínka THEN příkaz
- IF podmínka THEN příkaz1 ELSE příkaz2
- WHILE podmínka DO příkaz
- BEGIN příkaz1 příkaz2 END
Existuje zde i systém podobný návěští (programovací jazyk BASIC), kdy pomocí příkazu GOTO s číslem řádku se dostaneme na daný řádek kódu.
Obecný příklad
Následující příklad ukáže, jak se dá programovat zásobníkový počítač. Úkolem programu bude přečíst ze vstupu posloupnost čísel a určit, zda posloupnost obsahuje sudý počet čísel menších než 10. Pokud ano, vypíše 1, v opačném případě vypíše 0.
while NOT EOF do
begin
IN (načte číslo)
if POS then (pokud je číslo kladné)
begin
PUSH (uložíme do zásobníku)
CONST 10 (do registru se uloží hodnota 10)
SUB (odečte od hodnoty v registru hodnotu v zásobníku)
if NOT POS then POP (pokud číslo není menší než 10, smaže se)
end
end (všechna čísla splňující podmínky jsou uložena v zásobníku)
CONST1 (do registru uložena hodnota 1)
while NOT EMPTY do (vybíráme čísla po dvou)
begin
POP (smaže hodnotu ze zásobníku)
if EMPTY then CONST 0(lichý počet čísel v zásobníku)
else POP (v opačném případě vymaže hodnotu ze zásobníku)
end
OUT (v registru je uložena hodnota výsledku programu)
Jazyk Stackal
Tento jazyk je velice podobný Pascalu s úpravami vhodnými pro tento typ počítače. Odlišnosti od Pascalu jsou například:
- Proměnné
- Boolean – hodnoty true nebo false
- Char – znak z konečné množiny znaků
- a..b – celá čísla z intervalu a až b
- stack of a – zásobník hodnot typu a
- Nesmí se užívat příkaz :=
- Po napsání klíčového slova se uvádí vždy specifikace, např. (PUSH(S,x) – do zásobníku se uloží hodnota x)
Příklad programu v jazyce Stackal
Máme vytvořit program, který zjistí, zda se v daném řetězci vyskytuje stejný počet znaků a a znaků b. Pokud je počet stejný, program vypíše 1, pokud naopak, vypíše 0.
program ab;
var a, b: stack of char; (zásobníkové znaky)
c: char; (právě načtený znak)
begin
while read(c) do (čteme ze vstupu dokud EOF)
begin
if c='a' then push(a,c); (když je znak roven a, uložíme ho do zásobníku a)
if c='b' then push(b,c);
end;
while not empty(a) and not empty(b) do (opakuj dokud nebudou zásobníky prázdné)
begin
pop(a);
pop(b); (odebíráme po znaku z každého zásobníku zároveň)
end;
if empty(a) and empty(b) then (pokud jsou oba prázdné,....)
write('1') (....tak vypiš 1)
else
write('0'); (jinak 0)
end;
Toto řešení potřebuje ke svému řešení dva zásobníky, ale je poměrně přehledné a jasné i pro mírně pokročilé začátečníky. Ovšem tato úloha se dá řešit i pomocí jednoho zásobníku, což ukáže druhý příklad:
program ab2;
function look(var s:stack of char):char; (funkce, která zjišťuje, co je na vrcholu zásobníku)
var c:char;
begin
if empty(s) then c='0' (pokud je prázdný, do c se uloží 0)
else
begin
c=pop(s); (jinak odebereme prvek ze zásobníku)
push(s,c); (a ihned ho zase vrátíme zpět)
end;
look=c;
end;
var r:stack of char; (ukládá se rozdíl mezi a a b)
c:char;
begin
while read(c) do
begin
if c='a' then (přečtený znak je a a zvýšíme rozdíl mezi a a b)
begin
if look(r)='-' then
pop(r)
else
push(r,'-');
end;
if c='b' then (přečtený znak je b a snížíme rozdíl mezi a a b)
begin
if look(r)='+' then
pop(r)
else
push(r,'+');
end;
end;
if empty(r)then (pakliže je rozdíl uložený v r 0....)
write('1') (...vypíšeme 1)
else
write('0'); (v opačném případě 0)
end;