61. fejezet - Scriptnyelv készítése GNU flex & bison-al (második rész)


Az interpreter írása közben kiderült pár olyan dolog, amire eddig nem is gondoltam, de sokkal könnyebbé teszik a munkát. Nem egészen a tutoriál érdekében csináltam ezeket, hanem mert ezt a kis scriptnyelvet fel fogom használni az enginemben is. Az egyik ilyen dolog a szemétgyüjtés; a fordítási hibák után ugyanis tipikusan ottmaradnak a levegöben az allokált dolgok (és az életbe nem lehet öket felszabaditani). Bár a bisonban van egy speciális error nevezetü token, nem sikerült értelmesen használnom (ennek ellenére egy picit igényesebb fordítónak illene használnia). A szemétgyüjtéshez segítségül hívtam jó öreg template metaprogramming barátomat, úgyhogy a kóddal nem fárasztok most senkit. Minden fordítás közbeni memóriafoglalás és felszabadítás ezen keresztül kell történjen (most már a stringek is!).

A bájtkód egyszerübb kezeléséhez létrehoztam egy bytestream nevezetü osztályt, amibe lehet bájtot (opkód) vagy intet (argumentumok) pakolni. A használata tök egyszerü, ennyit kell csak mondani (példa): code << OP(OP_MOV_RS) << REG(EAX) << (int)5; ami majd végrehajtáskor az EAX regiszterbe irja, hogy 5. Ebböl már feltünhet, hogy a bájtkód erösen hasonlitani fog az x86 assemblyre, de a hatékonyság érdekében bizonyos megszorításokat illetve könnyítéseket eszközöltem.

Ezen kivül egy fontos dolog amit nem kellett volna elfelejtenem, hogy a lexerben követni lehet az aktuális kódsort, mégpedig így:

CODE
"\r\n" { ++yylloc.first_line; } // win "\n" { ++yylloc.first_line; } // unix

A megkülönböztetés azért kell, mert windowson az újsorba ugrás két karakterböl áll. A bison is ad lehetöséget a kódsor nyomonkövetésére a @ operátorral (hasonló mint a $), de ezt nem volt kedvem kipróbálni.

Az elözö részbe is utólag beletuszkoltam, de megemlítem mégegyszer, hogy a lexerben elég nagy marhaság volt str-nek nevezni a stringes állapotot, mert így remekül összeütközött a STL-beli stringstream::str() metódussal. Persze át nem javítom, mert lusta vagyok (az új kódban ki van javítva).


Deklaráció

A megnyugtató bevezetés után akkor bele is csapnék a lecsóba: írjunk fordítóprogramot! Eddig tudunk printelni, amivel mindenki nagyon jól elszórakozott, de gyorsan meg lehet unni. Szeretnénk leírni valami ilyesmiket:

CODE
int i; int j = 2, k;

Jobb helyeken a típus után álló kifejezést init-declarator-nak hívják, az ebböl álló listát pedig init-declarator-list-nek. Az itt bemutatott nyelv erösen típusos, tehát többszörös deklarációt nem engedek meg (kivéve belsö scopeokban, de azt majd késöbb). Nézzük meg elöször, hogy hogyan kell kifejezni a fenti utasítást.

CODE
declaration: typename init_declarator_list ; init_declarator_list: init_declarator | init_declarator_list COMMA init_declarator ; init_declarator: IDENTIFIER | IDENTIFIER EQ expr ;

Az expr egyelöre legyen csak NUMBER (késöbb majd tetszöleges kifejezés állhat ott). Rögtön felmerül a kérdés, hogy hogyan tároljuk el a már deklarált változókat (hiszen ellenörizni kell majd, hogy léteznek-e). Ehhez nyújt segítséget a szimbólumtábla, ami tetszöleges konkténer lehet ami tud kulcs-érték párokat tárolni (pl. std::map). Egy kicsit viszont elöre kell gondolkodni. Egy szimbólum ugyanis nem csak változó lehet, hanem függvény is (vagy még más), itt viszont elökerül az élettartam, láthatóság és a névelfedés fogalma. Ezekkel most különösebben nem foglalkozva fogadjuk el, hogy van egy globális scope a függvényeknek, a függvényeken belül pedig tetszöleges mélységü scope lehet (akár elágazás vagy ciklus által).

Azaz nem egy darab szimbólumtábla lesz, hanem egy szimbólumtábla lista, és nyilván kell tartani, hogy melyik scope-ban vagyunk éppen. A helyzet egyszerübb mint gondolnánk, söt szinte már magától értetödö:

CODE
struct symbol_desc { std::string name; // név int address; // memoriacim/utasítás címe int type; // tipus/visszatérö érték bool isfunc; // ha függvény }; typedef std::map<std::string, symbol_desc*> symboltable; typedef std::vector<symboltable> scopetable;
CODE
class Interpreter { private: scopetable scopes; bytestream program; size_t current_scope; // ... };

Egyelöre foglalkozzunk csak az 1-es scope-al (egy függvény törzse, most még csak a main törzse lehet). Ha most ránézünk a declaration nevü szabályra, akkor adódik, hogy annak valamiféle listát kéne megkapnia, amiböl elöállít szimbólumokat, illetve ellenörzi, hogy léteznek-e már.

CODE
struct declaration_desc { std::string name; bytestream bytecode; }; typedef std::list<declaration_desc*> decllist;
CODE
init_declarator_list: init_declarator { $$ = interpreter->Allocate<decllist>(); $$->push_back($1); } | init_declarator_list COMMA init_declarator { $$ = $1; $$->push_back($3); } ; init_declarator: IDENTIFIER { $$ = interpreter->Allocate<declaration_desc>(); $$->name = *$1; interpreter->Deallocate($1); } | IDENTIFIER EQ expr { // ... } ;

Hasonló strukturák még várhatóak, de nem mindet fogom leírni. Eddig nem is olyan szörnyü a dolog, csak felépitettünk egy listát arról amit deklaráltunk. Most viszont ideje betenni a szimbólumtáblába, illetve meg kéne határozni a címét is. Mivel valószínüleg mindenki kérdöjelekkel a feje körül várja a kódot, egy rövidke kis interzmezzot fogok tartani az


Assemblyröl

Pontosabban arról, hogy hogyan is müködik egy x86 architekturájú számítógép (merthogy az interpreter is hasonlóan fog). Olyat már biztos mindenki hallott, hogy van olyan, hogy regiszter, meg végrehajtási verem meg valami utasítások is, például mov. A regisztereket képzeljük el 32 bites tárolókként. A regiszterekben levö számok tulajdonságai a bitekböl, illetve az utasításokból határozodnak meg. Az általános célú regiszterek az alábbiak:

  • EAX - akkumulátor regiszter (szorzás/osztás)
  • EBX - index regiszter
  • ECX - számláló regiszter
  • EDX - port cím regiszter
A különbség ott mutatkozik meg, hogy bizonyos utasítások csak bizonyos regiszterekkel müködnek, de olyanokat itt nem fogok használni. A többi (fontosabb) regiszter már szigorúan egy bizonyos dologra használható:
  • EBP - végrehajtási verem alja
  • ESP - végrehajtási verem teteje
  • EIP - utasítás címe
  • FLAGS - müveletekböl adódó extra infók (nem használom)
A regiszterek felsö két bájtját jelöli a regiszter neve és egy X (pl. AX, BC, CX), ez nyilván 16 bites, illetve az alsó 16 biten belül még lehet hivatkozni az azt alkotó 1-1 bájtra (pl. AH, AL).

A végrehajtási verem nem egy szokványos verem, mert elöször is fejjel lefelé áll. Elemet belerakni az ESP regiszteren keresztül lehet, például ha le akarsz foglalni két darab int-et, akkor az egy sub ESP,8 utasítást jelent. Ebböl akkor következik, hogy az elemekre hivatkozni viszont EBP-n keresztül lehet. Például ez a két int [EBP-4] és [EBP-8] lenne (intel assemblyben a szögletes zárójellel lehet egy pointer által mutatott értékre hivatkozni). Ezen kivül még lehet használni a push utasítást, ami egy regisztert (vagy memóriacim által mutatott értéket) pakol be a verembe.

Kiíratni és egyéb érdekes dolgokat pedig kernel hívással lehet, miután beállítottuk a regisztereket. Ez unix alatt int 0x80, windowson int 0x21 (interrupt). A wikipédián lehet találni példa kódokat.

Ezek után nézzük meg hogy kéne kiszámolni a deklarált változók címét: egy globális változóban eltároljuk, hogy mennyi változót foglaltunk eddig le, legyen ennek a neve alloc_addr, ami nyilván minden függvény elején vagy végén kinullázódik. A deklarációk parseolásakor pedig felhasználjuk a (EBP-re nézve relatív) cím kiszámolásához.

CODE
declaration: typename init_declarator_list { parser_out("declaration -> typename init_declarator_list"); int scope = interpreter->current_scope; int size = 0; // csak az aktuális scope-ban nézzük (névelfedés!) symboltable& table = interpreter->scopes[scope]; symboltable::iterator sym; symbol_desc* var; expression_desc* expr; $$ = interpreter->Allocate<statement_desc>(); // végigmegyünk rajtuk for( decllist::iterator it = $2->begin(); it != $2->end(); ++it ) { // ha már deklarálva van, akkor error sym = table.find((*it)->name); nassert(0, "Conflicting declaration '" << (*it)->name << "'", sym != table.end()); // létrehozzuk a szimbólumot var = interpreter->Allocate<symbol_desc>(); var->type = $1; table[(*it)->name] = var; // cím kiszámolása interpreter->alloc_addr += interpreter->Sizeof($1); var->address = -interpreter->alloc_addr; size += interpreter->Sizeof($1); } // ez lesz a memóriafoglalás $$->bytecode << OP(OP_SUB_RS) << REG(ESP) << size; // ... interpreter->Deallocate($2); } ;

Ez az OP és REG egyszerü segéd makrók, hogy nem konvertálgassa a fordító implicit módon az értékeket (pl. a regisztereket unsigned charnak nézi). A Sizeof metódus pedig (ki nem találnátok) egy típus méretét adja meg, bájtokban (egyelöre könnyü a dolog, mert csak int-ek vannak).

Nem is olyan gáz ez. Amint az ember megírt egy-két ilyen programozási elemet, drasztikusan könnyebb lesz a többi megírása (föleg mert a C, mint nyelv baromi jól ki van találva). A kifejezéses deklarációt most egy picit félrerakom, elöbb fejezzük ki, hogy mi is az a kifejezés.


Aritmetikai kifejezések

Általános iskolában hallottunk ilyeneket matekból, hogy precedencia illetve bal- és jobbasszociativitás (honnan értékelödik ki). Bisonban lehetöség van megadni az asszociativitást, ha a %left vagy %right kulcsszóval deklaráljuk a nyelvtani jelet. Például:

CODE
%left add_expr sub_expr %left mul_expr div_expr mode_expr %right pow_expr

Amit késöbb deklarálsz, annak lesz nagyobb a precedenciája. Bár ez elég kényelmesnek hangzik totál fölösleges. 2-es típusú nyelvekben ugyanis baromi egyszerüen ki lehet fejezni mindezeket a szabályok megfelelö hierarchiába szervezésével: aminek nagyobb a precedenciája az lejjebb kell majd legyen a szintaxisfán. A kiértékelést pedig a bal- vagy jobbrekurzivitással lehet kifejezni. Emlékeztetöül az operátorok precedenciája:
  • függvényhívás és zárójelezett kifejezés
  • hatványozás
  • unáris operátorok (-, ++, --)
  • multiplikatív (*, /, %)
  • additív (+, -)
  • relációk (<, <=, >, >=)
  • egyenlöség-vizsgálat (==, !=)
  • logikai és (&&)
  • logikai vagy (||)
  • értékadás (=, +=, -=, stb.)
A szabályokat pont fordított sorrendben kell megadni és teljesen jól fog müködni a dolog. Én hatványozást nem csináltam, de ne felejtsük el, hogy azt jobbrekurzívan kell megadni!

CODE
expr: assignment ; assignment: or_level_expr | lvalue EQ assignment ; or_level_expr: and_level_expr | or_level_expr OR and_level_expr ; // ... unary_expr: term | INC term | DEC term | MINUS term ; term: LRB expr RRB | literal | variable | func_call ;
CODE
struct expression_desc { bytestream bytecode; std::string value; // ha konstans kif. int type; // típus (fontos!) int address; // cím, ha balérték bool constexpr; // konstans kif.-e }; literal: NUMBER { parser_out("literal -> NUMBER"); $$ = interpreter->Allocate<expression_desc>(); $$->type = Type_Integer; $$->value = *$1; $$->address = UNKNOWN_ADDR; $$->constexpr = true; interpreter->Deallocate($1); } ;

A függvényhívást most még hagyjuk. Hatékony programot szeretnék generáltatni a fordítóval, ezért érdemes megkülönböztetni a kifejezéseket aszerint, hogy konstans kifejezések-e (pl. 5 + 3), illetve regiszterben vannak-e tárolva (address == UNKNOWN_ADDR) vagy a stacken (változók). A konstans kifejezéseket a fordító fogja kiszámolni és csak a végeredményt írja a programba. A stacken levö változókat pedig be kell mozgatni egy regiszterbe mielött valamit csinálnánk velük.

Assemblyben többféle lehetöség van, például lehet azt mondani, hogy add EAX, [EBP-4], de például nem lehet olyat mondani, hogy mov [EBP-4], [EBP-8]. Figyelembe véve, hogy az interpreternek minden utasításra egy többszörös elágazáson kell végigmennie (hacsak nem irjuk meg függvénypointerekkel, de most komolyan két utasítás miatt függvény...?), próbáltam minél kevesebb utasítást csinálni, de azokat legalább kicsit kiterjeszteni. Azaz például az utóbbi stacken való buherálást a bájtkód tudja.

Az összeadás/kivonás és a szorzás/osztás/maradékképzés eléggé hasonszörü müveletek, ezért azokat lehet egyben kezelni. Azonban nagyon figyelembe kell venni azt, hogy egy ilyen müvelet mindekét operandusa tetszöleges kifejezés lehet, amiket még ez elött kell kiértékelni. Az ilyen kifejezések bájtkódját az Interpreter::Arithmetic_Expr() metódus végzi el, lekezelve az összes lehetséges esetet.

Egyet bemutatok itt, mondjuk amikor azt írtuk le, hogy (a + b) * c és a szorzást akarjuk kiértékelni. Az elsö operandus két változó összeadása, aminek már van kódja és az eredmény EAX-ben van. A második operandus egy változó, ami valahol a stacken van (de egyébként nem tudjuk egyikröl sem, hogy konkrétan mi). Elsö dolog, hogy bemásoljuk az elsö kifejezés kódját (vegyük észre, hogy nem kell új kifejezést létrehozni, használhatjuk az elsöt) és lementjük az EAX regisztert (hiszen a második kif. esetleg használja). Ezután beirjuk a bájtkódba a másik kif. kódját, a stackröl pedig kivesszük EBX-be. Végül a lementett EAX-ot kivesszük a veremböl és elvégezzük a szorzást.

CODE
// expr1 in EAX, expr2 on the stack expr1->bytecode << OP(OP_PUSH) << REG(EAX) << NIL; expr1->bytecode << expr2->bytecode; expr1->bytecode << OP(OP_MOV_RM) << REG(EBX) << expr2->address; expr1->bytecode << OP(OP_POP) << REG(EAX) << NIL; expr1->bytecode << OP(OP_MUL_RR) << REG(EAX) << REG(EBX); expr1->address = UNKNOWN_ADDR; expr1->constexpr = false;

Sose felejtsük el beállítani az eredménykifejezés tulajdonságait, például az értékadás eredménye a stacken lesz (és nem ez az egyetlen, például ++i is ott van!)!

Ami egy picit elgondolkodtatóbb az az összehasonlítás. Jó lenne ha azt is le lehetne írni, hogy i = (a < 2);, ugyanakkor az if( a < 2 )-t is le kéne valahogy fordítani. Azaz az összehasonlítás eredményét is egy regiszterbe kéne rakni. It eléggé eltérek az assemblytöl, ott ugyanis az összehasonlítás (cmp) a flag regisztert módosítja és az elöjelböl/túlcsordulásból lehet meghatározni, hogy mi is történt. Ez kényelmetlen, úgyhogy a scriptnyelvben nincs cmp, hanem a setl, setg, setle, stb. utasítások fognak máshogy müködni (konkrétan elvégezni az összeahasonlítást). Ez ráadásul baromi kényelmessé is teszi a dolgot, mert a fenti Arithmetic_Expr() metódust lehet használni.

Ami még hátravan az az értékadás, ezt már könnyü kikövetkeztetni: a bal oldal memóriaterületére be kell mozgatni a kifejezés eredményét (szintén mind a három esetet lekezelve).

CODE
assignment: or_level_expr { $$ = $1; } | lvalue EQ assignment { $$ = $1; if( $3->constexpr ) { // konstans kifejezés, berakjuk int a = atoi($3->value.c_str()); $$->bytecode << OP(OP_MOV_RS) << REG(EAX) << a; $$->bytecode << $3->bytecode << OP(OP_MOV_MR) << $1->address << REG(EAX); } else if( $3->address == UNKNOWN_ADDR ) { // kifejezés eredménye EAX-ban $$->bytecode << $3->bytecode << OP(OP_MOV_MR) << $1->address << REG(EAX); } else { // stacken levö érték $$->bytecode << $3->bytecode << OP(OP_MOV_MM) << $1->address << $3->address; } interpreter->Deallocate($3); } ;

Persze létre lehet hozni olyan szabályokat amik külön lekezelik a konstans kifejezéseket. A többi operátor teljesen hasonló elven müködik, de azt meg kell emliteni, hogy a ++i; operátor balértéket kell kapjon és nem csak EAX-be rakja az eredményt, hanem visszaírja a stackbe is! A másik fajta növelést nem írtam meg, legyen höfö.

Ránézve a generált kódra feltünhet, hogy idönként marhaságokat csinál; például beleírja az értéket EAX-ba aztán átrakja EBX-be, hogy szorozzon vele. Ezeket egy külön bájtkód-optimalizáló lépésben el lehet tüntetni (a másik fajta optimalizáció az, amikor a szintaxisfát elemezve dobálsz ki dolgokat).


Elágazás és ciklus

Itt már kezd érdekes lenni a dolog, mert el kell kezdeni ugrálni az utasítások között. Végrehajtáskor nyilván tudjuk, hogy hol vagyunk éppen, ezért relatív címekre érdemes ugrani (a függvényhívásnál ebböl lesz némi gond, de majd látni fogjuk, hogy egyébként se kerülnénk el a megoldását).

Egyelöre nem engedek meg csellengö else-t, tehát mindig kötelezö kitenni a {}-et. Nem azért mert olyan hüdenehéz megcsinálni, de az elözö tutoriál alapján tudjuk, hogy abból mindenféleképpen shift/reduce konfliktus lesz (ez nem hiba persze).

Mit is csinál az elágazás? Ha teljesül a feltétele, akkor végrehajtja a fö ágat. Ha nem teljesül akkor átugorja. Ha az elágazás fordításakor a két ág kódja már ismert, akkor ki lehet számolni, hogy mekkorát kell ugrani. A feltételben szereplö kifejezésre annyit kell megnézni, hogy nulla-e vagy nem.

CODE
conditional: IF LRB expr RRB scope { $$ = interpreter->Allocate<statement_desc>(); $$->bytecode << $3->bytecode; if( $3->constexpr ) { // ha 0 az értéke, akkor nem kell csinálni semmit // ha nem 0, akkor bemásoljuk az utasításokat } else { if( $3->address != UNKNOWN_ADDR ) $$->bytecode << OP(OP_MOV_RM) << OP(EAX) << $3->address; int off = 0; // kiszámoljuk, hogy mennyit kell ugrani, ha nem teljesül a feltétel for( statlist::iterator it = $5->begin(); it != $5->end(); ++it ) { if( *it ) off += (int)(*it)->bytecode.size(); } // ha a kif. értéke 0, akkor átugorjuk az utasításokat $$->bytecode << OP(OP_JZ) << REG(EAX) << off; // egyébként le fognak futni for( statlist::iterator it = $5->begin(); it != $5->end(); ++it ) { if( *it ) { $$->bytecode << (*it)->bytecode; interpreter->Deallocate(*it); } } interpreter->Deallocate($3); interpreter->Deallocate($5); } } | IF LRB expr RRB scope ELSE scope { // teljesen hasonló, de az if végén át kell ugrani az else ágat } ;

Direkt lekezeltem, hogy konstans kifejezések esetén csak az a kód kerüljön be, amelyiknek le kell futni (ez már egy optimalizáció). Höföként meg szabad írni a switch-case-t is, annyit kell megjegyezni, hogy a vizsgált kifejezés hasonlóan bármi lehet, de a case feltételei csak konstans kifejezések (extraként megengedhetünk nem integrált is, pl. float). Ez lehetövé teszi, hogy logaritmikus kereséssel vagy ugrótáblával találjuk meg a megfelelö ágat.

A ciklus teljesen hasonszörüen müködik, viszont a ciklusmag végén vissza kell ugrani a feltétel kiértékeléséhez, illetve ha hamisra értékelödött ki, akkor át kell ugrani a ciklusmagot. A break utasítást egyelöre kihagytam.


Scope-ok

A fentiekben már láthattuk, hogy a kontroll utasítások után kapcsos zárójeleken belüli utasítássorozat (blokk utasítás) kell álljon (ez a scope nyelvtani jel), és nyelvi szinten kötelezö. Önmagában blokk utasítást viszont nem engedek meg (ezt speciel egy megfelelö helyre tett scope-al meg is lehet oldani).

Az kéne, hogy a scope elején megnöveljük a scope számlálót, a végén pedig visszacsökkentsük. Gondoljuk, meg hogy mit jelent ez: a bison akkor fog redukálni egy nyelvtani jelre, ha a teljes jobb oldalát illesztette már. Azaz az utasítások elöbb fognak lefordítódni, minthogy a scope-ba belépnénk! Semmi gond, szedjük szét két részre a szabályt, hogy a scope elejét ismerje fel elöször:

CODE
scope: scope_start statement_block RB { // ha nem top level scope (függvénytörzs), akkor a lefoglalt // változókat deallokálni kell! (add ESP, n) // ... --interpreter->current_scope; } ; scope_start: LB { ++interpreter->current_scope; } ;

Ennyi. Ezzel meg van oldva a névelfedés és az automatikus deallokálás. Egy picit érdemes belegondolni, hogy a kapcsos zárójel nélküli elágazást és ciklust hogyan is oldanánk meg. Kell oda scope? Egy utasítás állhat mögötte! Deklaráció? Nem kell csinálni semmit. Azonban nem ugorhatjuk át csak úgy a deklarációt, hogy "úgysincs értelme", mert mi van, ha ez a ciklusmag: int i = myfunc();? Itt már egy kicsit bonyolódik a helyzet, ezért is raktam még félre a nem kapcsos zárójeles ciklust/elágazást.


Függvényhívás

Az utolsó nehezebb feature van már csak hátra: hogy függvényeket és alprogramokat tudjunk csinálni. A paraméterátadási mód csak érték szerinti lehet (mivel amugyis csak int-eket ismerünk még csak). Meilött belemennénk ebbe van egy fontos fogalom, amit úgy hívnak, hogy cdecl hívási konvenció.

A konvenció azt mondja, hogy a függvényeknek garantálni kell, hogy a visszatérés után a program konzisztens marad, azaz nem írják felül a hívó stack frame-jét. Ezért minden függvénynek van egy prológusa és egy epilógusa, ami az alábbi módon fest:

CODE
push EBP mov EBP, ESP // ... mov ESP, EBP pop EBP mov EAX, <visszatérö érték> // VAGY push

A függvénynek ennyi a dolga. A hívónak viszont az a dolga, hogy lementse a regiszterek értékeit, a stackbe berakja a függvény aktuális paramétereit és az aktuális utasítás címét (visszatérési cím), illetve a függvény visszatérése után kiüritse a stacket. Az elsöt nem kell megcsinálni, mert a kifejezések kódjában garantált, hogy a regiszterek konzisztensek.

Na jó, de hova a rákba kell elugrani, hogy a függvényhez jussunk? Hiszen még azt se tudjuk, hogy hol lesz a kódban (söt, nem is biztos, hogy parseoltuk már, gondoljunk a C-re). Ezen a ponton elökerül a linkelés fogalma, nevezetesen a hivatkozások feloldása.

CODE
struct unresolved_reference { symbol_desc* func; // ha függvényhívás int offset; // ha nem };
CODE
term: func_call { // argumentumok kódja és berakás a stackre // ... // átugorjuk az extra utasításokat és // lementjük a visszatérési címet $$->bytecode << OP(OP_PUSHADD) << REG(EIP) << (int)(ENTRY_SIZE); // beírunk egy unresolved external-t a kódba // (lehetne akár külön is tárolni, de na...) unresolved_reference* ref = interpreter->Allocate<unresolved_reference>(); // ez a függvény tartozik hozzá ref->func = $1; $$->bytecode << OP(OP_JMP) << (int)UNKNOWN_ADDR << ADDR(ref); // stack kitakarítása // (count == ahány argumentum volt) for( int i = 0; i < count; ++i ) $$->bytecode << OP(OP_POP) << REG(EDX) << NIL; } ;

Szemfüles olvasóknak feltünhet, hogy EIP-t nem vettem ki a stackröl. Ezt ugyanis a return utasítás fogja megcsinálni (még akkor is, ha nem írtuk le). Még szemfülesebb olvasók észrevették, hogy szerintem nem csak a függvényhívás lehet unresolved external. Höfö kitalálni, hogy még mi (mert nekem bizony fogalmam nincs, ennek ellenére nem töröltem ki a kódból).

Na de a return... honnan tudjuk, hogy van vagy nincs? Honnan tudjuk, hogy minden végrehajtási ágon van-e? Egy elég egyszerü megoldást választottam: annyit követelek meg, hogy a fö ágon legyen, a többi nem érdekel. Persze void függvényre nem kell megkövetelni.

A return mögött tetszöleges kifejezés állhat, de a típusa meg kell egyezzen a függvény visszatérö értékével. Tehát tudni kéne, hogy melyik függvényben vagyunk éppen. Hasonló meggondolással, mint a scopeoknál eltároltam az aktuális függvényt. A megvalósítás innentöl már könnyü:

CODE
statement: RETURN expr { symbol_desc* func = interpreter->current_func; nassert(0, "In function '" << func->name << "': Invalid return type", func->type != $2->type); $$ = interpreter->Allocate<statement_desc>(); $$->type = Type_Return; $$->scope = interpreter->current_scope; // kiértékelés + berakás EAX-ba // epilógus és visszatérés $$->bytecode << OP(OP_MOV_RR) << REG(ESP) << REG(EBP); $$->bytecode << OP(OP_POP) << REG(EBP) << NIL; $$->bytecode << OP(OP_POP) << REG(EIP) << NIL; interpreter->Deallocate($2); } ;

Az utasításban eltároltam, hogy return-e, illetve a scopeját is, így egy warning formájában jelezni lehet a dead code-okat. A kezdöszimbólum rutinjában már meghatározható a függvények címe, így linkeléskor egyszerüen végig kell menni a bájtkódon, és ha feloldatlan hivatkozást találunk, akkor be kell írni helyette az adott függvény címét.


A babérok begyüjtése

Igen, nagyon sok minden elmagyarázását kihagytam, dehát ezért teszem közzé a kódot...maga a végrehajtás csupa egysoros utasítás, amit egy óvodás programozó is bármikor meg tudna írni. Ennyivel már el tud indulni valamerre az, aki esetleg saját scriptnyelv írására adná a fejét. Na de nézzük akkor, hogy mit föztünk. Rögtön egy jó kis rekurzív programocskával kezdeném: számoljuk ki egy szám faktoriálisát!

CODE
int factorial(int i) { if( i == 0 ) { return 1; } return i * factorial(i - 1); } int main() { int i = factorial(5); print "The factorial of 5 is: "; print i; print "\n"; return 0; } // output: // The factorial of 5 is: 120
CODE
0000: push EBP 0009: mov EBP, ESP 0018: mov EAX, [EBP+8] 0027: sete EAX, 0 0036: jz EAX, 81 0045: mov EAX, 1 0054: mov ESP, EBP 0063: pop EBP 0072: pop EIP 0081: mov EAX, [EBP+8] 0090: sub EAX, 1 0099: push EAX 0108: pushadd EIP, 9 0117: jmp 0 0126: pop EDX 0135: mov EBX, EAX 0144: mov EAX, [EBP+8] 0153: mul EAX, EBX 0162: mov ESP, EBP 0171: pop EBP 0180: pop EIP 0189: mov EAX, 65536 ; ez jelzi a program végét 0198: push EAX ; ha kiveszi, akkor vége 0207: push EBP 0216: mov EBP, ESP 0225: sub ESP, 4 0234: mov EAX, 5 0243: push EAX 0252: pushadd EIP, 9 0261: jmp 0 0270: pop EDX 0279: mov [EBP-4], EAX 0288: print <addr> 0297: mov EAX, [EBP-4] ; ezt például ki lehetne 0306: print EAX ; optimalizálni 0315: print <addr> 0324: mov EAX, 0 0333: mov ESP, EBP 0342: pop EBP 0351: pop EIP ; vége

Ha a rekurzió müködik, akkor nagy gond már nem lehet (piszlicsáré problémák viszont elég könnyen). Csak a rend kedvéért nézzük meg, hogy a névelfedés müködik-e rendesen.

CODE
int main() { int i = 6; int j = 5; if( i > 0 ) { int i = 7; int j = 6; if( i == 7 ) { print "second scope is alive (i == "; } else { print "first scope is alive (i == "; } print i; print ")\n"; } print "(j == "; print j; print ")\n"; return 0; } // output: // Second scope is alive (i == 7) // (j == 5)
CODE
0000: mov EAX, 65536 0009: push EAX 0018: push EBP 0027: mov EBP, ESP 0036: sub ESP, 4 0045: mov EAX, 6 0054: mov [EBP-4], EAX 0063: sub ESP, 4 0072: mov EAX, 5 0081: mov [EBP-8], EAX 0090: mov EAX, [EBP-4] 0099: setg EAX, 0 0108: jz EAX, 261 0117: sub ESP, 4 0126: mov EAX, 7 0135: mov [EBP-12], EAX 0144: sub ESP, 4 0153: mov EAX, 6 0162: mov [EBP-16], EAX 0171: mov EAX, [EBP-12] 0180: sete EAX, 7 0189: jz EAX, 216 0198: print <addr> 0207: jmp 225 0216: print <addr> 0225: mov EAX, [EBP-12] 0234: print EAX 0243: print <addr> 0252: add ESP, 8 0261: print <addr> 0270: mov EAX, [EBP-8] 0279: print EAX 0288: print <addr> 0297: mov EAX, 0 0306: mov ESP, EBP 0315: pop EBP 0324: pop EIP

Ne felejtsük el, hogy ez nem (valid) x86 assembly, csak ahhoz hasonló. Egy tippet viszont adhat ahhoz, hogy hogyan kéne konkrét fordítóprogrammá alakítani a progit.


Summarum

Ez a cikk már kevésbé tekinthetö tutoriálnak, mert feltételezi, hogy bizonyos minimális ismeretekkel rendelkezik már az olvasó. Azoknak szól inkább akik nem akarnak külsö scriptnyelv libeket használni. Még egy fejezetet terveztem, amiben a linkelést egészítem ki úgy, hogy több forrásfájlt is tudjon kezelni, illetve bemutatnám, hogy hogyan integrálom bele ezt a nyelvet az enginebe. Még nem tudom mikor fog ez megtörténni.

A kód letölthetö itt.


Höfö:

  • Írd meg a postfix ++ operátort és társait!
  • Csinálj for és repeat-until ciklusokat!
  • Csináld meg a még kimaradt részeket a kódból (keress rá: not yet implemented)!
  • Hogyan lehetne hatékonyan megoldani a lusta kiértékelést?

back to homepage

Valid HTML 4.01 Transitional Valid CSS!