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;

Související články

Externí odkazy