Hogyan írjunk interpretert 90 perc alatt, ~ 200 sorban

A "Why Not" fantázanevű virtuális gépről (és a gép assembleréről) szóló korábbi posztokban az érdeklődők megismerhettek egy végletesen szimpla processzort, valamint egy olyan assemblert, ami ehhez a processzorhoz alakított át forráskódot ún. gépi kóddá, a processzor által végrehajtható programmá.

 Az  közismert, hogy az ilyen tevékenységet végző programokat nevezzük compiler-nek .
   
   Az interpreterek a  compilerektől annyiban különböznek, hogy a folyamat eredeménye nem egy futtatható program, hanem annak kimenete, produktuma, terméke.

Az interpreterek és a compilerek útja addig a pontig közös, amíg a forráskód tokenekre tördelése, azonosítása meg nem történik. Ezután a compiler általában transzkódol, azaz, a beérkező forráskódból egy másik fajta kódot állít elő, későbbi futtatás céljából.        
Az interpreter jellemzően nem állít elő semmiféle kódot a forrásból, hanem azt valamilyen egységekre (mondjuk sorokra) bontva azonnal kiértékeli és végre is hajtja. Az interpreter lényegében egy résznyi compilernek és egy rész processzornak a sajátos ötvözete.

   Mivel a forrás feldolgozásának kezdeti lépései az interpreter és a compiler esetében is ugyanazok, az interpreterünk építéséhez a korábbi assembler (Why not asm) forrásából fel fogunk használni néhány programrészt.

   Ezek leginkább a karakterek tipusát meghatározó függvények, mint az Alphabet és a Numeric függvény (Itt most Alfa és Numr lesz a nevük). Ezek abban segítenek, hogy képesek eldönteni egy-egy beérkező karakter hovatartozását. Például azt, hogy a karakter egyáltalán szám-e (0..9), avagy betű ('A'..'Z').

Na de, hogyan is működött az az assembler?

   Minden programnyelvnek, így az assemblereknek is van egy nyelvtanuk. Ez a nyelvtan egy szimplább/bonyolultabb szabályrendszer. Olyan, mint az élő nyelvek esetében. Ami leírja, meghatározza, hogy egy mondat miből állhat (alany, állítrmány, határozó, jelző, stb.).  Tekintve, hogy ez a terület, hogy nyelvtan, elég sokakat frusztrál, így nem is bocsátkozok bele mélyebben. Csakis annyira, amennyire az feltétlenül szükséges.

   A "why not" assembler grammatikája, nyelvtana szerencsére igazán egyszerű.
Nézzük:
 
- Egy sorban csak egy mondat szerepelhetett.
- A mondatok végén, pont helyett egy pontosvesszőnek kellett állnia.
- Minden mondat csak egy kulcsszóból és szintén egy mögé írt számból állhatott.
- A kulcsszavak egyike sem lehetett hosszabb, vagy rövidebb három karakternél. Továbbá, ezek a karakterek csakis betűk lehettek.
 

wnASM forrás

A kulcsszavak mennyisége is csekély volt, mindössze kilenc (9) lefedte a teljes kulcsszó-készlet egészét.
A kulcsszavak utáni  paraméterek, amelyek kivétel nélkül számok voltak, nem lehettek nagyobbak 255-nél és kisebbek 0-nál.

A fenti szabályrendszer alól  is csak egyetlen egy képezett kivételt, a RET kulcsszó.  Ez volt az, amelyik mögé nem kellett számot (paramétert) írni. ám a szabály többi része, a három karakteres hossz, a mögé írt pontosvessző, erre az egyre is vonatkozott.
Az assembler nyelvének teljes eszközkészlete egy fél sorban is elfér. Ez az alábbi:

DAT, ADD, SUB, STA, LDA, CMP, JMP, JZR, RET 

   Plusz még ehhez - paraméterként - a nullától kétszázötvenötig (0..255) terjedő pozitív egész számok halmaza. Igazán nem sok. Ez az egyszerűség két előnyt biztosított. Szolgálta a befogadhatóságot, a megtanulhatóságot és a forráskód könnyű feldolgozhatóságát.Ez utóbbit  nevezzük assemblálásnak. Nekünk most erre kell kitérnünk. Az assemblálás folyamatára.
A program (assembler) a forrásfájlt karakterenként dolgozta fel. Első lépésként beolvasott a fájlból egy karaktert. Második lépésként a Gettoken függvénnyel megvizsgáltatta a beolvasott karaktert és ha az betűből állt, akkor addig olvasta tovább a forrás karaktereit, amíg azok betűk voltak, ha számból, akkor addig, amíg számok voltak. Ezeket a beolvasott karaktereket egymás mellé illesztve, azokból egy stringet (ez a token) képezve adta át a főprogramnak, ahol a főprogram a token-t annak jellege, milyensége szerint dolgozta fel. Ha számok voltak, akkor egy "string to integer" konverzió után kerültek a memóriába, ha betűk, tehát kulcsszavak, akkor az éppen aktuális kulcsszóhoz párosított opkód került a memóriába, a megfelelő helyre.

   A dolog lényege, hogy a kommenteken kívül minden egyes karakter ugyanazon a folyamaton ment át. A főprogramon keresztül lett meghívva a GetToken függvény, ami a beolvasott karakter tipusától függően vagy a getKeyWord, vagy a GetNumber függvényt hívta meg, ami aztán összerakta a következő tokent, feltéve ha nem volt hiba a forráskódban. ha a forráskód a nyelv szabályrendszerének (grammatikájának, nyelvtanának) megfelelt.

   Na de miért kell ilyesmi, hogy grammatika, nyelvtan, szabályrendszer?
   Azért, hogy a kommunikáció zavartalanul végbemehessen. Mert valójában a fordítóprogramok is kommunikációt valósítanak meg. Ők a tolmácsok a küldő és a fogadó fél között. A küldő fél a programozó, aki a forrást megfogalmazza, a fogadó pedig az a gép, ami a programozó sorait - immár valamilyen átalakított formában - futtatja. Az interpreter esetében ilyen tolmácsra nincs szükség.  Az interpreter ugyanis a forráskód értelmezésére és annak végrehajtására egyaránt képes.

   A fentiekből két dolog következik. Az egyik, hogy az interpreterünk megalkotásához nekünk is szükségünk lesz egy programnyelvre. A másik, hogy a programnyelvünknek meg kell határozzuk a grammatikáját, a nyelvtanát. Aggódásra tényleg semmi ok, ez a nyelvtan-alkotás egy nagyon könnyű folyamat lesz, szinte szórakoztató. Sőt, nem is csak szinte.

Na de miféle programnyelvet alkossunk?

Nézzük, mások hogyan csinálják:
A programnyelvek alkotásának általában két fő célja van.
- Az egyik, valamilyen logikára épülő ún. általános cél. Ez azt jelenti, hogy a készülő nyelv széles határok között alkalmas kell legyen szinte bármilyen program megalkotására.
- A másik a specializált nyelv, amelyik egy bizonyos problémakörre kínál megoldást és ami ezen a területen hatékonyabb is annál, mint amit egy általános célú nyelv kínál.

   A dolog jól szemléltethető egy franciakulcs és egy villáskulcs segítségével. A franciakulcs széles határok között minden csavar ki és becsavarásához megfelel, viszont egész napos használatra f'árasztó, nehéz darab. Ráadásul, a nagyon erősen meghúzott csavarok kicsavarásához alkalmatlan és túlságosan erősen meghúzni sem lehet vele a csavarokat. A villáskulcs ezzel szemben, bár csak két csavar-mérethez felel meg, de azokhoz legalább full service-t biztosít. Könnyű, kis helyekre is befér, jól meg lehet vele húzni a csavarokat és az erősebben behajtottakat is könnyebb, egyáltalán, esélyesebb vele kicsavarni mint a franciakulccsal.
 

speciális, általános

 

A franciakulcs az általános, széles körben használatos, a villáskulcs pedig a speciális, szűkebb körben alkalmazható.

   A mi programnyelvünket is speciális igényekre fogjuk tervezni, mivel egy általános célú nyelv megalkotásához még meglehetősen kevesek vagyunk. Persze nem feltétlenül a képesség, hanem inkább a szükséges tudás hiánya okán.

Na de mit is alkossunk?
Hiszen már legalább négy-ötezer féle programozási nyelv létezik. Mi olyat csinálhatnánk mi, amiből nincs még legalább kettő-három jobb, profibb annál, amire mi jelen pillanatban képesek vagyunk. Hát, nem sok ilyen terület akad, ha akad egyáltalán. Azonban mégis van egy szeglet, ami megfelelhet az igényeinknek. Ez pedig a programozott rajzolás. Gondoljunk bele. Volt-e az életünkben olyan eset, amikor úgy kellett, vagy kellett volna egynél legalább eggyel több rajzot, illusztrációt létrehoznunk, hogy a rajzok közötti különbség csak elenyésző volt?

   Most készíthetünk egy olyan eszközt, tool-t magunknak, ami a jövőben, ilyen célra bármikor bevethető és szükség esetén (vagy akár csak hobbiból) még bővíthető is. Rengeteg időt lehet vele megspórolni. A rajzolás folyamata elmenthető és bármikor megismételhető, vagy megváltoztatható. A rajzolás szakaszai is fájlba menthetőek, ezzel animációkat, prezentációkat is létrehozhatunk. 

A létező nyelvek közül talán a LOGO az, ami a legközelebb áll ahhoz, amit csinálni fogunk, bár meg kell valljam, az én életemből a LOGO teljességgel kimaradt, így amit tudok róla, az szinte a nullával egyenlő.

   Fogalmazzuk meg a problémát.  Mi is kell ahhoz, hogy programozottan rajzolhassunk?
Először is, valamilyen hordozó, egy rajzlap. Ez nem más mint egy - célszerűen fehér szinű - felület.
Kell még ceruza (PEN) is. Ez jó, ha változtatható vastagságú vonalak rajzolására is képes.

De egyáltalán, mi magának a rajzolásnak a folyamata?

 A ceruza (PEN) hegyének a rajzlap egy adott pontjáról egy másik pontba való átmozgatása.
Ez menne is, egyszerűen, na de mi van, ha párhuzamos vonalakat szeretnénk rajzolni?
Hát olyankor el kell emelni a ceruza (PEN) hegyét a rajzlaptól.

A rajzlapunk egy meghatározott méretű - mondjuk .bmp formátumú - grafikus file rajzfelülete lesz, amit úgy hívnak, hogy canvas (ez magyarul vászon).

A ceruza (PEN) pedig egy, a rajzlapon valamilyen színnel nyomot hagyni képes metódus. Ez lehet olyan, ami egy vonalat képes rajzolni (LineTo függvény) vagy olyan, ami a rajzlap egy apró pontját festi meg (SetPixel függvény).

Szó esett a párhuzamos vonalak rajjzolhatóságának igényéről is, ezért fontos, hogy a ceruzát képesek legyünk legalább virtuálisan elemelni a rajzlaptól (PEN UP) majd vissza is helyezni a rajzlapra (PEN DOWN).

A fentebb soroltakat már akár össze is foglalhatjuk. Lássuk, mik is az igények?

- rajzlap méretének (pl. 640x480 pixel) meghatározhatósága (CANVAS X,Y)
- toll (ceruza) vastagságának (pl.1,3,8 pixel) változtathatósága (PENWIDTH n)
- toll (ceruza) felemelése és leengedése (PENUP/PENDOWN).
- toll pozícionálásának lehetősége (GOTO X,Y).
- toll irányának meghatározása (LEFT,RIGHT,UP,DOWN (bal,jobb, fel, le)).
- toll lépésének mérete pixelben (STEP n). Ez a legkisebb egység (szakasz, vagy pont), amit rajzol a toll egy lépésben.

Ha ezeket az igényeket utasításokba szervezzük (lásd a zárójelezett részeket), akkor kapunk egy komplett, programozható rajzgépet. Pontosabban, annak vezérlését megvalósító utasítás-szettet, ami már-már egy programnyelv megvalósításához is elég.

A kulcsszavak ezek: Canvas, Penwidth, Goto, Left, Right, Up, Down és Step.
Ez mindössze nyolc szó és talán meglepő, de ezzel a nyolc szóval bármi lerajzolható, programozottan. Igaz, csak két szinben.
Ha színeket is akarunk, akkor egy kilencedik, (pl. PENCOLOR n) utasítással is kiegészíthetjük az utasítás-készletet.

A PenUp és PenDown nyugodtan ki is hagyható.

Ennél egyszerűbben talán nem is lehetne, igaz?
Nem igaz!
A plotter vezérléséhez elég lenne a CANVAS X,Y utasításon kívül a penUP/penDOWN párossal kiegészített GOTO X,Y is, hiszen így is eljuthatunk a CANVAS területének bármelyik pontjára, a rajzol/nem_rajzol mód váltását pedig biztosítja a penUP-penDOWN utasításpár.  
Ezzel a módszerrel az utasításaink száma négyre redukálódna! Igaz, nem lenne lehetőség a toll vastagságának változtatásához, de hát, csak rajtunk áll, hogy milyen új  utasításokkal egészítjük ki az alap-készletünket.

Ezzel a programozhatóság ugyan megvolna, de elég primitív módon lehetne lerajzolni akár csak egy négyszöget is, hiszen hiányoznak a nyelvünkből a változók és a vezérlő szerkezetek is.
A változók - mivel egy programozható rajzgépről van szó, aminek az alapegysége lényegében a pixel - integer tipusúak kell, hogy legyenek. Az érték-tartományuk sem kell, hogy túlságosan bő legyen. Hogy a nyelvünket minél egyszerűbben megvalósíthassuk, az lenne a legjobb, ha a változóink az angol ABC egy-egy betűjével lennének megfeleltetve.
Ez 26 lehetőség, de ennek duplázása (AA, AB, AC, AD, ..) is megvalósítható, ami már  676 (26x26) egyedi változó használatára adna lehetőséget egyetlen programon belül.   

   Számunkra a vezérlő szerkezetek talán legfontosabbika a számlálós ciklus. Egy számlálós ciklus áll a ciklusfejből, a ciklusvégből és az e kettő között elhelyezkedő ciklusmagból.
A ciklusfejnek tartalmaznia kell egy ciklusszámlálót, ami meghatározza, hogy a ciklus magja hány alkalommal kerüljön végrehajtásra. A ciklusvég pedig arra jó, hogy tudjuk, mikor kell visszatérni a ciklusmag első utasításához és mikor kell továbblépni. A ciklusvég lényegében egy feltételvizsgálat, amelyből kiderül, hogy végre kell-e még hajtani a ciklusmagot, vagy sem.   Ha a ciklus számlálója nagyobb egynél, akkor dekrementáljuk (csökkentjük) eggyel és ismét a ciklusmag elejéről folytatódik a végrehajtás, ha nem nagyobb, akkor kilépünk a ciklusból, a következő utasításra.

 

loop, ciklus

Ciklus (loop) lekezelése, feldolgozása:

 1. A 01 sorra lépünk.
 2. Eltároljuk az abban talált számot (ötöt) a LoopCnt változóba.
 3. Eltároljuk a következő sor számát (02) a LoopAddr változóba.
 4. végigmegyünk a ciklus magján (02-06) és végrehajtjuk azt.
 5. A ciklusvéghez (07) érve:  
    * Megvizsgáljuk, hogy a ciklusváltozó 1-nél nagyobb-e?
    * Ha nem nagyobb, akkor tovább lépünk a következő (08) sorra.
    * Ha nagyobb 1-nél, akkor
       a. Csökkentjük (eggyel) a ciklusváltozó (LoopCnt) értékét.
       b. A LoopAddr-ben eltárolt számú  sorra (02) ugrunk.
       c. A 4. ponttól kezdve újra lépkedünk míg LoopCnt > 1.

(Folyt. köv.)

 

next time