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 Překladač Zásobníkový automat Zásobník (datová struktura) Forth (programovací jazyk)
Externí odkazy Zásobníkový automat Automaty a gramatiky Jazyk Forth a zásobníkové procesory na ROOT.cz Další možné příkazy pro zásobníkové počítače Začátky s jazykem Assembler
Kategorie:Výpočetní modely