Amikor a SpaceBang 2-t publikáltam, sokan megkérdezték, hogy mivel csináltam a scriptnyelvét, meg úgy egyáltalán hogyan lehet saját scriptnyelvet (vagy akár fordítóprogramot) írni. A delikvensek valószínüleg beijedtek a válaszként belinkelt bison dokumentáció miatt, meg egyébként is aki elötte még sosem hallott formális nyelvekröl, annak problémás lehet a nem éppen szokványos logikája (és a meglehetösen fapados használata).

Ebben a tutorialban ismertetem azt a minimális tudást ami egy interpreter írásához kell. Írhatnék fordítóprogramot is, de annak a játékfejlesztésben nincs túl sok szerepe (és a különbség csak a szemantika értelmezésében rejlik).

Röviden összefoglalva az alábbi dolgokból fog állni a program:

• lexikális elemzö flex-el
• szintaktikus/szemantikus elemzö bison-al
• az elöállított bájtkódot feldolgozó interpreter
• néhány teszt script

Elöre megjegyezném, hogy a flex és bison bár külön-külön is müködnek, csak együtt lehet öket értelmesen használni. Egyik sem library, nincsenek headerjerik, mindkettö egy C kódot fog generálni, amit nekünk csak használnunk kell.

A flex letölhetö itt, a bison pedig itt (a dependencyket is le kell szedni). Az ezek által generált programok mindenféle megszorítás nélkül használhatóak commercial cuccokhoz is, de maga a flex/bison GPL licenszes.

Egyelöre nem fogok még kódokat írni, hanem megpróbálom összefoglalni, hogy hogyan is épül fel egy fordítóprogram. A legelsö szint nyilván maga a forrásfájl, nevezzük ezt most inputnak. A lexikális elemzö feladata, hogy az inputból elöállítson egy token sorozatot. Például az alábbi kódból:

a következö token sorozatot állítja elö: IF LEFTBRACKET IDENTIFIER LESS IDENTIFIER RIGHTBRACKET IDENTIFIER EQUAL IDENTIFIER SEMICOLON ELSE IDENTIFIER EQUAL IDENTIFIER SEMICOLON. A lexer bizonyos dolgokat átugorhat, például a whitespaceket, de akkor úgy kell kitalálni a programnyelvet, hogy a whitespacek kiszedése után is értelmes maradjon (pl. a Python nem ilyen).

Az alapszabály az, hogy a lexer mindig a lehetö leghosszabb stringet próbálja illeszteni, tehát a szabályok sorrendje nem mindegy! Az emlegetett szabályok reguláris kifejezések, például az azonosítókat így lehet a lexerrel felismertetni:


Eszerint egy azonosító kezdödhet betüvel vagy aláhúzással, egyébként lehet benne betü, szám, vagy aláhúzás. A konkrét megvalósítást flex-el majd késöbb fogom megadni.

Erröl a témáról könyvtárakat lehet megtölteni, ezért ide csak a lényeges részeket írom le, azt is csak olyan pongyolán amennyire emlékszem a záróvizsga óta. Generatív nyelvtannak nevezünk egy G = <T, N, P, S> négyest, ahol T a terminális szimbólumok halmaza (értsd: betük), N a nyelvtani jelek vagy másként nemterminálisok halmaza, P szabályok véges halmaza és S ∈ N pedig a nyelvtan kezdöszimbóluma.

Az alábbi megszorítások alapértelmezettnek tekintendöek:

• T ∩ N = ∅
• minden szabály bal oldalán van legalább egy nyelvtani jel

A nyelvtan által generált nyelv azoknak a szavaknak az összessége, amik S-böl a szabályok véges sokszori alkalmazásával levezethetöek.

A szabályokra egyéb megszorításokat adva lehet eljutni a Chomsky 1, 2, és 3 típusú nyelvekhez illetve ezek kiterjesztett változataihoz. Ami az ügy szempontjából érdekes, hogy a reguláris kifejezések 3-as típusúak, a program szintaxisa pedig 2-es típusú (környezetfüggetlen). Ez utóbbi úgy néz ki, hogy a szabályok bal oldalán egy nyelvtani jel van, a jobb oldalon pedig nyelvtani jelek és terminálisok sorozata. Például:


Ha egy nyelvtani jelböl többminden is levezethetö, akkor | jellel szokás ezeket elválasztani. Ez a nyelvtan ilyen szavakat állít elö: ab, abb, abbb, stb. Rögtön észre is lehet venni, hogy a második szabály balrekurzív, azaz a szavakat ezzel a szabállyal lehet "pumpálni". Nyilván akkor van jobbrekurzív szabály is, például A -> bA egy ilyen.

Egy fontos fogalom a szintaxisfa, például az abbb szónak így néz ki a fája:


Ha most a leveleket balról jobbra összelvassuk, akkor az abbb szót kapjuk meg. Nyilván most az lesz az érdekes, hogy egy input tokensorozatból el lehet-e jutni S-ig (a program szintaktikusan helyes-e). Azaz valahogyan visszafelé kell alkalmazni a szabályokat és közben felépíteni a szintaxisfát.

Nagyon nem ezzel kéne kezdeni, de megintcsak nem akarok könyvet írni a különféle elemzökröl, ezért rögtön azt fogom bemutatni amit a bison is használ. Ez a LALR annak a röviditése, hogy Look Ahead Left to Right, tehát az inputot balról jobbra haladva olvassa, az (1) pedig azt jelenti, hogy 1 szimbólumot olvas elöre az inputból. Bár önmagában a bisonhoz nem kéne ezt tudni, nem árt ha tisztában vagyunk azzal, hogy mi történik a háttérben (föleg hibakeresésnél lehet hasznos).

Ez most egy eléggé bonyolult algoritmus lesz, én is rendszeresen elrontom (söt, egy csomó idöbe telt mire újra megértettem). Talán a legegyszerübb fogalom a FIRST1(α), ezért azzal kezdem, a lehetö legpongyolábban:

FIRST1(α) = { az α-ból kisakkozható szavak elsö terminálisa }

α itt terminálisokból és nemterminálisokból álló string. Például a fenti nyelvtanban FIRST1(S) = { a }, FIRST1(A) = { a }, FIRST1(ABa) = { a }. Nyilván ha α terminálissal kezdödik, akkor az lesz az elsö. Fontos, hogy bár erre a nyelvre egyelemüek ezek a halmazok, könnyen lehet olyat mondani amiben van több elemü is.

Maga az elemzö egy automata, aminek az állapotátmeneteit egy táblázattal fogom megadni. Ennek a táblázatnak az elkészítéséhez viszont egy esetenként baromi hosszú írkálást kell müvelni. Legeslegelsö dolog, felveszel egy S' -> S új szabályt, és minden szabályt megszámozol (az átláthatóság érdekében az összevagyolt szabályokat szétszedtem):

Ezek után elö kell állítani az elemzö kanonikus halmazait. Ezek a halmazok ún. LR(1) elemeket tartalmaznak, amik ilyen alakúak:

[X -> α.β, z]

ahol a . azt próbálja jelezni, hogy hol tartunk egy szabály illesztésével, z pedig az elöreolvasási szimbólum. Két fontos egyéb halmazt kell bevezetni egy H kanonikus halmazra:

closure(H): H minden elemét tartalmazza, ezen kivül ha
     [X -> α.Yβ, z] eleme H-nak és Y -> δ egy szabály, akkor
     [Y -> .δ, q] -t is vegyuk hozzá, minden q eleme FIRST1(βz) -re

Úristen...hát igen, bár így leírva elég szörnyü, valójában arról van szó, hogy ha . jobb oldalán nyelvtani jel van, akkor az abból levezethetö szabályokat is vegyük hozzá a halmazhoz, a megfelelö elöreolvasási szimbólummal. A példából minden ki fog derülni, de elöbb a másik halmaz:

read(H, Y): ha [X -> α.Yβ, z] eleme H-nak, akkor legyen ez a halmaz closure([X -> αY.β, z])

Azaz a pontot eggyel arrébb rakod, és kiszámolod a closure-t. Fontos, hogy mind a kétféle halmazt addig kell böviteni, ameddig csak lehet, mert különben vicces dolgokat tapasztalsz majd az elemzésnél. Rögtön elö is állitanám ezeket a fenti nyelvtanra, lépésenként. Amit meg kell jegyezni, hogy ha számolás közben olyan halmaz jön ki, ami teljesen megegyezik egy korábbival, akkor nem kell új halmazt felvenni. A # az input szó végét jelöli (pl. abbb#).


Látható, hogy vannak olyan elemek, amik csak elöreolvasási szimbólumban különböznek, ezeket helytakarékosságból lehet pl. [A -> .aB, #/b] alakban írni. Nézzük a következö halmazt, mit lehet H0-bol olvasni? (azaz mi van a pont jobb oldalán?). Lehet elöszöris S-et:


Ez mindig egy speciális halmaz, ugyanis azt jelenti ez, hogy ha az 1-es állapotban van az automata és #-ot olvasunk, akkor elfogadtuk az input szót (azaz a szó szintaktikusan helyes). Menjünk tovább, H0-bol lehet olvasni A-t:


Tovább nem lehet böviteni, és még nincs ilyen halmaz, megyünk tovább:


Ilyen halmaz sincs, a többit most már együtt adom meg:


Kész vagyunk, nem lehet már semmiböl se olvasni egyéb szimbólumot. A LALR(1) parsereknek még van egy olyan optimalizálása, hogy azokat a halmazokat amik csak elöreolvasási szimbólumban különböznek össze lehet vonni. Itt most nincs ilyen, de ezt ugy kéne jelölni, hogy H[i,j] = Hi ∪ Hj, és az akkor ez egy ilyen összevont állapota lesz az automatának.

A következö lépésben kitöltjük az elemzö táblázatot, ami üresen valahogy így néz ki:


Az action azt mondja meg, hogy ha az i-edik állapotban van az automata és x-et olvastunk, akkor milyen müveletet kell végrehajtani (léptetést vagy redukciót). A goto táblázat pedig redukció esetén fogja megmondani, hogy melyik állapotba kell átmenni.

A kitöltés úgy történik, hogy megnézed a kanonikus halmazokat, és ha találsz bennük olyan elemet, aminek a végén van pont, akkor abban az állapotban az elembeli elöreolvasási szimbólumra redukciót kell végrehajtani az elem szabálya szerint. Például H4-ben van ilyen elem, hogy [A -> Ab., #], illetve [A -> Ab., b], tehát akkor ha a 4-es állapotban van az automata és # vagy b jön, akkor redukálni kell a 2. szabály szerint:


Hasonlóan lehet eljárni H2, H5, H6 -al is, H1 viszont speciális halmaz, ezért oda accept-et kell írni.


Hátravannak még a léptetések, ezt úgy lehet észrevenni, hogy ha Hj = read(Hi, y), akkor action[i, y] = sj. A goto teljesen hasonló, csak nyelvtani jelekre (ha Hj = read(Hi, Y), akkor goto[i, Y] = j). A végleges táblázat, tehát így néz ki:


Az üres helyeken mindig error értendö. Elöfordulhat olyan eset, amikor a táblázat egyik helyén már van valami, ezt hívja majd a bison shift/reduce illetve reduce/reduce konfliktusnak. Ilyenkor az elsö esetben léptetni fog (ez a tipikus csellengö else).

Az automata kész van, most próbáljuk meg vele szintaktikusan elemezni az abbb szót. Az elemzéshez egy vermet fogok használni, amiben mindig két elem lesz: az olvasott szimbólum és az aktuális állapot. Ezen kivül még megjegyzi azt is, hogy az input szóból mennyi van még hátra. Az automata konfigurációja tehát (verem_tartalma, input_hátralevö_része).


A redukálás ugy történik, hogy megnézed a redukciós szabály jobb oldalának hosszát, és annyi (dupla) elemet kiveszel a veremböl. A helyére pedig berakod a szabály bal oldalát (itt most B) és megnézed, hogy a verem tetején levö állapotból ennek hatására hova kell gotozni. Ilyenkor az inputban nem kell lépni.


Vegyük észre, hogy a verem változásával egyben a szintaxisfát is fel tudjuk rajzolni, alulról építve balról jobbra. Egy értelmesebb IDE ilyenkor végzi el például a syntax highlighting-ot. Szemfülesebb olvasók észrevehetik, hogy a rekurzivitás ott mutatkozik meg, hogy a kifejezéseket balról jobbra, vagy jobbról balra akarjuk-e kiértékelni.

Dióhéjban ennyit a LALR(1) elemzöröl, ha valakit részletesebben érdekel a téma, akkor ajánlom Csörnyei Zoltán: Fordítóprogramok címü könyvét (a szerzö szerint ez a legnépszerübb jegyzet az ELTE-n :)).

Emlitettem, hogy a flex és bison külön is müködnek, de csak együtt érdemes öket használni. A lexikális elemzö meglehetösen egyszerü, ezért azzal nem is lesz sok probléma, a szintaktikus elemzö viszont egy egyszerü nyelvre is elég hosszú lehet. A tutorial kódjában ezért csináltam egy simpleinterpreter projektet, ami egy main() függvényt tud elemezni és az egyetlen utasítás a print. Ez egy ilyen starting point lehet mindenkinek aki nem akar maga szivni a bison használatával.

A programot úgy bontottam le, hogy lehetöleg jól elkülönithetöek legyenek a részek. A lexikális elemzö konvencionálisan .l, a szintaktikus/szemantikus elemzö pedig .y kiterjesztésü. A fájlok a következök:

• lexer.l - lexikális elemzö
• parser.y - szintaktikus/szemantikus elemzö
• interpreter.h - az interpreter osztály definíciója
• interpreter.cpp - az interpreter osztály implementációja
• compiler.cpp - a flex/bison-hoz szükséges segédfüggvények
• special.cpp - speciális script utasítások implementációi
• generate.bat - batch script a generáláshoz

Kezdeném azzal, hogy hogyan épül fel egy flex illetve bison fájl:


A beállításokkal kapcsolatban a dokumentációt érdemes elolvasni, de tipikusan az általam használtakon kivül nem kell más. Ha Visual Studio-t használsz, akkor érdemes bizonyos warningokat kikapcsolni, illetve a projekthez felvenni egy unistd.h nevü fájlt (csak windowson, mert linuxon elfedné a rendszerét!).

A generáláshoz egy batch scriptet dobtam össze, aminek be kell adni a flex/bison elérési útját és legenerálja a megfelelö fájlokat.


Ezt Visual Studio-ban be lehet állítani pre-build eventnek, de nekem csak úgy sikerült, hogy mindig rebuild-ot kell nyomni, hogy le is futtassa. Ami fontos, hogy a generált fájlokat vagy ne add hozzá a projekthez, vagy zárd ki öket a fordításból (jobb klikk/properties/general), hacsak nem akarsz egy rakás external symbolt deklarálni.

CODE #ifndef _INTERPRETER_H_ #define _INTERPRETER_H_ #include <iostream> #include <string> #include <list> // debug makrók #define lexer_out(x) #define parser_out(x) #define assert(r, e, x) #define nassert(r, e, x) class Interpreter { // a bison lássa majd ezt az osztályt friend int yyparse(); friend int yylex(); private: // ebbe tároljuk a szemetet std::list<std::string*> garbage; void Cleanup(); public: // egyelöre csak parsol egy scriptet bool Compile(const std::string& file); };

CODE #include "interpreter.h" #include "lexer.cpp" #include "parser.cpp" bool Interpreter::Compile(const std::string& file) { FILE* infile = fopen(file.c_str(), "rb"); assert(false, "...", infile); // a fájl hossza fseek(infile, 0, SEEK_END); long end = ftell(infile); fseek(infile, 0, SEEK_SET); long length = end - ftell(infile); // beolvassuk a progit egy bufferbe char* buffer = (char*)malloc((length + 2) * sizeof(char)); assert(false, "...", buffer); buffer[length + 1] = buffer[length] = 0; fread(buffer, sizeof(char), length, infile); fclose(infile); std::cout << "Compiling \'" << file << "\'\n"; yy_scan_buffer(buffer, length + 2); // meghivjuk a generált parsert int ret = yyparse(); // takaritás yy_delete_buffer(YY_CURRENT_BUFFER); free(buffer); Cleanup(); nassert(false, "...", ret != 0); return true; }

A bison elvárja, hogy legyen valahol a kódban egy yylex és yyerror függvény (azaz ö fogja hivogatni a lexikális elemzöt). Én ezt a következöképpen szoktam megoldani: a flex belépési pontját felüldefiniálom:


És én implementálom a bison által követelt yylex-et a compiler.cpp-ben:


Hogy mi micsoda, az világos lesz a parser megírásakor.

Vágjunk is bele akkor a sürüjébe, elöször is nézzünk meg egy kódot az egyszerü nyelven és találjuk ki hogyan lehetne tokenizálni:

Itt említeném meg, hogy Unicode karaktereket még nem sikerült parseolnom bison-al, de elvileg megoldható, ha egy preprocessing step-ben UTF-8-ba konvertálod a buffert (és a lexerben definiálod a megfelelö rule-t).

Ami biztos, hogy a kommenteket és a whitespaceket nem kell szintaktikusan elemezni (elég nagy szívás is lenne belöle), ezért olyankor nem ad vissza semmit. Az egyszerüség kedvéért elöre definiáltam, hogy milyen karakterek lehetnek például egy azonosítóban:


Látható, hogy ha egy konkrét karakterosorozatot akarsz illeszteni, akkor azt macskakörmök között kell megadni, deklarált dolgokra kapcsos zárójelekkel lehet hivatkozni, egyébként pedig a reguláris kifejezéseknél szokásos dolgokat lehet használni.

A visszaadott tokenek még nincsenek deklarálva sehol, majd a bison deklarációs részében kell öket megadni a %token kulcsszóval, és a generált parser.hpp-be fognak kerülni.

A speciális karakterek illetve a nyelv kulcsszavai elég egyszerüen elintézhetöek, csak vigyázni kell, hogy az azonosítók szabálya elé rakd öket (különben azonosítónak fogja nézni a flex).


Ami viszont nem annyira trivi az a stringek felismerése. Én annakidején kihoztam egy olyan reguláris kfeiejzést ami mindenféle stringet fel tud ismerni, de késöbb találkoztam olyan esetekkel amiket nem lehet egy kifejezésbe besuvasztani. A flex-ben szerencsére lehetöség van állapotokat definiálni. Egy állapotot a %x kulcsszóval lehet deklarálni a deklarációs részben, a hozzá tartozó szabályokat pedig a <állapotnév> prefixxel kell ellátni. A BEGIN(állapotnév) utasítással lehet új állapotba rakni a lexert, ha pedig vissza akarsz menni a kezdöállapotba akkor BEGIN(INITIAL)-t kell mondani. Ezek után nézzük hogyan kell stringeket matcholni:


Ez viszonylag egyszerü, de a '' féle karaktertömböket ignorálja (höfö kiegésziteni). A macskakörmök nem feltétlenül kellenek a whitespacekhez hasonlóan (én valami érthetetlen oknál fogva meg szoktam tartani). Ami fontos, hogy olyan nevet ne adj meg állapotnévnek, ami bármiféle változó, függvény vagy metódus neve lehet, mert nem fogod megtalálni a fordítási hibából.

A lexer ezzel gyakorlatilag kész is van (az egyszerü nyelvre), késöbb majd ki kell egészíteni egyéb kulcsszavakkal és operátor szimbólumokkal.

Most jön az a rész, amit már nem mindig lehet egyértelmüen leirni, és nem lehet úgy szétdarabolni, hogy minden rész külön fordítható legyen. Ennek ellenére lépésenként fogom ismertetni, hogy mit hogyan kell kifejezni 2-es típusú nyelvtannal. Elsö körben a fenti egyszerü nyelvre írom meg a parsert és utána fogom kiegészíteni egyéb nyelvi elemekkel.

Fent említettem, hogy a tokeneket a parser deklarációs részében kell deklarálni, itt viszont van egy kis csavar. A bison megkülönböztet típusos és típustalan tokeneket. Típusos token például egy szám literál, hiszen a programban használni kell majd az értékét. Típustalan viszont a { és egyéb jelek, söt a nyelv kulcsszavai is, hiszen ezekböl a fordító legenerálja a megfelelö kódot, de a programba csak így kerülnek be. Például az if kulcsszóból fordítódna egy test EAX, EAX assembly utasítás (és egy jz <cím> feltételes ugrás).

A token típusa tetszöleges C vagy C++ pointer típus lehet, ezeket mind az %union {} blokkon belül kell megadni. Ebböl fog legenerálódni a C-s YYSTYPE únió, ezért javasolt, hogy pointerek legyenek (32 bites programokban lehet még egyéb 4 bájtos cucc is). Ha bármiféle hibát kapsz amiben ez az únió szerepel, akkor érdemes a tokeneknél szétnézni (típusosnak deklaráltad-e).

Egyelöre három típusos token lesz: a szám literálok, a string literálok és az azonosítók, söt mind a három string típusú (jéééé):

És akkor most jöjjön a lényeg: a szabályok. Minden bison szabály nyelvtani_jel: levezetés1 | ... | lebezetésN; alakú. Minden levezetéshez tartozhatnak szemantikus rutinok {} között, illetve a nyelvtani jelek is lehetnek típusosak; ezekröl majd késöbb. Ha egy nyelvtani jelböl az üres szót akarod levezetni, akkor azt a levezetési részt üresen kell hagyni (de rutinja attól még lehet). Nézzünk egy konkrét példát: a kezdöszimbólum neve legyen program. Ebböl levezethetö (egyelöre) egy darab függvény, a main.


Mielött valaki félreértené: ez a parser_out egy sima C makró, amit debugolás céljából definiáltam. Nyilván a main nem kulcsszava a nyelvnek, mint ahogy általában egyik fordítónál sem, ezért a function nyelvtani jelböl az alábbi vezethetö le:


Tehát egy függvény áll egy fejlécböl és egy törzsböl, kapcsos zárójelek között. Nézzük elöször a fejlécet:


Ahol a typename-böl nyilván levezethetö az INT token. Az argument_list egyelöre legyen üres. A függvény törzse utasítások sorozatából fog állni. Na jó jó, de hogy fejezzük ki egy nyelvtannal azt, hogy "sorozat"? Természetesen rekurzív szabályokkal, viszont vigyázni kell mert itt a legkönnyebb elrontani a nyelvet. Minden szabály felvétele után ellenörizd, hogy van-e conflict és ha kell papíron vezesd le, hogy miért rossz!


És végül az utasításból levezethetö a print utasítás, aminek egyelöre csak egy string paramétere lehet:


Ugye nem is olyan nehéz? Persze, hogy nem, csak rá kell érezni. Ha most lefuttatod a parsert, akkor hiba nélkül parsolja a fenti programocskát. Rosszabb esetben gönyörü fordítási hibákat kapsz. Ami jó a bisonban, hogy ha valamit elrontasz, akkor nem a generált kódban fogja azt megmutatni, hanem a parser.y fájlban (persze debugolni már nem fogod tudni, de na...).

A már emlegetett rutinok tetszöleges C/C++ kódot tartalmazhatnak, ezek mind bele fognak kerülni a generált kódba. Ha egy nyelvtani jelet vagy tokent típusosnak deklaráltál, akkor hivatkozhatsz rá a $ operátorral. A szabály feje mindig $$, a levezetés elemei pedig 1-töl indexelödnek ($1, $2, stb.). Ahogy a parser illeszti az egyes szabályokat ezek a paraméterek szépen mennek felfelé a szintaxisfán, így egy feljebb levö szabálynak át lehet passzolgatni amit csak szeretél.

Csináljunk egy olyat debug célból, hogy írjuk ki amit ki kéne printelnie majd a programnak. Ehhez a string nyelvtani jelet deklaráljuk típsusosnak, és adogassuk át a parsolt szöveget a print-hez tartozó szabálynak:

Fontos: ez még nem az interpreter, csak debug célból írtam ki dolgokat. Oké, de honnan került érték abba a paraméterbe? Lapozzunk csak vissza az yylex() implementációjához:


Persze most már kiegészítettem a hiányzó részt. Ez az yylval az únió egy példánya, és a kódban a text_t részének adok értéket. Nyilván az escapelt karaktereket le kell cserélni a tényleges escape karakterekre.

Itt csak a típusos tokeneknek kell értéket adni, a típusos nyelvtani jeleknek majd a szemantikus rutinokban hozom létre a memóriaterületét.

Most hogy már tudjuk szintaktikusan elemezni az alap progit, ideje megírni a végrehajtását is. A program bájtkódra fog fordulni, aminek egy bejegyzése a következöképpen néz ki:

opkód arg1 arg2

Az egyszerü nyelvben csak printelni lehet, és annak egyelöre csak egy paramétere lehet, egy string. Vegyünk fel egy függvénypointer tömböt, amivel a speciális kulcsszavaink végrehajtásait lehet meghívni. Beterveztem elég helyet 20 speciális kulcsszónak (de valószínüleg nem fogom kihasználni).

CODE #define NUM_STAT 1 #define OP_PRINT 0x0 class Interpreter { // ... typedef void (*stm_ptr)(void*, void*); static stm_ptr op_special[NUM_STAT]; // special statements static void Execute_Print( void* arg1, void* arg2); // ... };

CODE Interpreter::stm_ptr Interpreter::op_special[NUM_STAT] = { &Interpreter::Execute_Print }; void Interpreter::Execute_Print( void* arg1, void* arg2) { std::string* str = reinterpret_cast<std::string*>(arg1); if( str ) std::cout << *str; }

A bájtkód maga egy sima char* dinamikus tömb, legyen mondjuk maximum 64 KB. Az argumentumok átpasszolásához pedig lefoglaltam egy 256 KB-os heapet. Emellett nyilvántartom, hogy hány bájtnál tart a kód, illetve a heap (és ha esetleg túllépné a határt, akkor legalább egy hibaüzenetet kiír). Az allokálást egy template metódussal és a placement new-al oldottam meg.

CODE print: PRINT string { parser_out("print -> PRINT string"); interpreter->AddCodeEntry( OP_PRINT, interpreter->Allocate<std::string>($2), 0); } ;

CODE #define ENTRY_SIZE (1 + 2 * sizeof(void*)) template <typename T> void* Interpreter::Allocate(T* data) { assert(0, "...", heap); nassert(0, "...", (heapsize + sizeof(T)) >= HEAP_SIZE); char* ptr = (heap + heapsize); new (ptr) T(*data); heapsize += sizeof(T); return ptr; } void Interpreter::AddCodeEntry( unsigned char opcode, void* arg1, void* arg2) { nassert(, "...", (bytesize + ENTRY_SIZE) >= CODE_SIZE); char* ptr = (bytecode + bytesize); *((unsigned char*)ptr) = opcode; *((void**)(ptr + 1)) = arg1; *((void**)(ptr + 1 + sizeof(void*))) = arg2; bytesize += ENTRY_SIZE; }

Remélem nem lett túl bonyolult. Ha ez megvan, akkor már csak futtatni kell a bájtkódot. Mivel tömböt indexelünk a speciális utasítások opkódjai legyenek 0-tól 19-ig. Hogy meddig tart egy utasítás, azt elöre lerögzitettem az ENTRY_SIZE makróban (persze memóriatakarékosságból lehetne változóra hagyni).


Ha mindent jól csináltunk, akkor a Run() metódus meghívására a program kiírja (most már az interpreter által), hogy Hello World!. Ezzel kész a legelsö, kicsit butus de nagyon állat interpreterünk. Ezen a ponton a simpleinterpreter projektet be is zárom, és egy új projektben fogom folytatni a scriptnyelv írását (és orbitális mennyiségü baromságot kell majd kijavítanom...hehe...).

Ennek a picit hosszabb tutorialnak az elsö felét láthattuk/hallhattuk. Ez alapján már egyszerübb scriptnyelveket össze lehet hozni, a következö részben viszont úgy fogom kiterjeszteni a nyelvet, hogy fordítóprogramhoz hasonló legyen.

A kód letölthetö itt. A fordításhoz nem kell a flex/bison, csak ha módosítod a lexert/parsert. Ezeket értelemszerüen a megfelelö helyre kell tenni (vagy írd át a generate.bat-ot).


Höfö:

• Bövítsed ki a print-et úgy, hogy több stringet is ki tudjon írni (vesszövel elválasztva)!