Vaje - Zbirnik SIC/XE sklad

Vaje - Zbirnik SIC/XE sklad

Sklad

Prvi poskus

  • Ste opazili, da SIC/XE stroj nima ukazov za delo z skladom?
  • Zakaj sklad (nujno) potrebujemo?
  • Kje se shrani naslov ob izvedbi ukaza JSUB na katerega s vrnemo iz rutine z ukazom RSUB.
  • Kako bi v SIC/XE implementirati neko rekurzivno rutino?
  • Kako višji programski jeziki navadno prevedejo klice funkcij? Kako prenašajo parametre?

Navadno je delo s skladom v zbirniku podprto z ukazi PUSH/POP za dodajanje in odvzemanje registrov na/s sklad/a. Tako bi v SIC/XE potrebovali rutine kot so:

  • PUSHA, POPA, PUSHS, POPS, PUSHT, POPT, PUSHL, POPL

Bi znali implementirati take rutine?

  • Kakšna bi bila razlika med PUSHA in PUSHL?
  • V čem je težava s PUSHL?
  • Za kakšne vrste rutin nujno potrebujemo PUSHL in POPL.

Sedaj pa zares

Implementacija vseh zgornjih rutin je precej duhamorna in morda sploh ne potrebujemo vseh. Zato bomo izziv malce poenostavili in shranjevanje na sklad razbili v dve podoperaciji: kopiranje registra na sklad, povečevanje/zmanševanje kazalca na sklad.

  • Za implementacijo sklada potrebujemo kazalec na vrh sklada stackptr, ki naj kaže na prvo nezasedeno besedo sklada.
  • Namesto kopice rutin, bomo raje implementirali le dve: za povečevanje in zmanjševanje kazalca na vrh sklada.
  • Registre pa bomo pred oz. po uporabo teh rutin sami ročno zapisali/prebrali iz sklada.

Porivanje na sklad bomo torej izvedli z dvema ukazoma. Tako bo izvedba operacije PUSHA zgledala takole:

STA   @stackptr    . na vrh sklada zapišemo A
JSUB   stackpush   . povečamo kazalec na vrh sklada

Vsakemu push-u mora nekje v programu slediti ustrezen pop, npr. POPA bo zgledal takole:

JSUB   stackpop    . zmanjšamo kazalec na vrh sklada
LDA   @stackptr    . z vrha sklada preberemo A

Potrebno bo implementirati le tri rutine:

  • stackinit - inicializacijo sklada (inicializira stackptr glede na nek rezerviran kos pomnilnika);
  • stackpush - povečanje kazalca na vrh sklada; in
  • stackpop - zmanjšanje kazalca na vrh sklada.

Ne pozabite tudi rezervirati prostora za sklad.

Faktoriela

S pomočjo rutin iz predhodne naloge napišite rutino za (rekurziven) izračun faktoriele n! Število n prenesete v registru A. Rezultat naj rutina vrne v A.

  • S pomočjo rutin za izpis iz prejšnjih vaj, izpišite nekaj faktoriel.
  • Za vajo faktoritelo napišite rekurzivno, seveda pa je faktorielo bolje implementirati iterativno. Lahko napište še to.

* Hanojski stolpi

Kateri računalničar ne pozna uganke Hanojski stolpi?

S pomočjo rutin iz predhodne naloge in rutin za izpis napišite rutino, ki izpiše rešitev uganke. Rešitev je zaporedje potez, npr. A>B, ki so potrebne za prestavitev vseh obročev iz solpa A na stolp C.

Namigi:

  • Število diskov prenašamo v registru A.
  • Oznake obročev pa v registru S - za vsak stolp en bajt. Npr. 'ACB' je začetna konfiguracija: premikamo iz A na C preko B.
  • Po želji lahko program dopolnite, da začetno število diskov na obroču prebere iz naprave

Kako že rešujemo Hanojske stolpe?

Vhod: število obročev n, oznake 1., 2., 3. stolpa (začetni, končni, vmesni)

  • Prestavi n-1 obročev iz 1. na 3. (preko 2.)
  • Prestavi 1 obroč iz 1. na 2.
  • Prestavi n-1 obročev iz 3. na 2 (preko 1.)
Last modified: Monday, 27 October 2014, 1:17 PM