Pokrok :)

Hotový projekt
Náplní tohoto modulu je vygenerování kódu v assembleru Universal Scriptu pro každou funkci. Bude to nějaká posloupnost instrukcí.
Instrukce je v kompileru zastoupena třídou CInstruction , která má jako většina tříd a struktur složku kind, která určuje kterou
z 33 instrukcí které Universal Script Assembler představuje. Třída CInstruction má také ukazel next na další instrukci. Kód dané funkce bude v
paměti tedy uložen jako jednosměrný lineární spojový seznam sestávající z instancí třídy CInstruction. S tím souvisí proměnná opcodes struktury
FUNCTION, která ukazuje na začátek kódu (spojového lineárního seznamu) funkce, kterou představuje. Psát program v assembleru, ať už v jakémkoliv,
není zrovna uživatelsky nejpohodlnější a nejlehčí. Teď chceme aby to dělal stroj, aby cykly a podmínky napsal v assembleru a aby výsledek dělal to samé jako
napsaný skript. Jak ale stroj naučíme programovat v assembleru, nebo aspoň vyjádřit skript, který máme uložený v paměti jako strom, vyjádřit jako program
v assembleru Universal Scriptu? Nejjednodušší řešení je použítí tzv. šablon. Pro každou programovou konstrukci (if, while, for...) a výraz (sčítání, odčítání...)
dáme kompileru šablonu, podle které vygeneruje kód/posloupnost instrukcí. Když bude vědět jak vyjádřit například if, nic mu nebrání aby to udělal.
Kód který vygeneruje tento modul za pomoci šablon nebude nijak optimalizovaný. Ani pro velikost, ani pro rychlost ani pro nic jiného. Jen bude "chodit" a o to nám tu jde.
Až kompiler dokončíte, můžete (měli by jste pokud chcete jazyk používat ve svých komerčních programech) popřemýšlet jak kód optimalizovat. To si vyžadá jistě vložení dalšího modulu,
nejlépe za tento modu :) My se tady optimalizací bavit nebudeme, není to důležité pro o aby skriptovací jazyk fungoval. Jak se dá v assembleru napsat příkaz if-else jsme
se podívali vlastně už v minulé lekci. Samotný if se moc neliší a jistě ho zvládnete vymyslet/odvodit z if-else nebo opsat sami :) Proto se podíváme hned na cykly.
Co třeba cyklus for:
for (i = 0; i < 5; i++)
{
a *= i;
}
Kód který pro tento cyklus vygeneruje kompiler:
Toto je inicializace cyklu i = 1, provede se pred provadenim cyklu
ldc_int 0//Načti na vrchol zásobníku 0
store 0//Ulož 0 do proměnné i (i má index 0)
Tady zacina test a vyhodnoceni podminky
start_0:
load 0//Nacti na vrchol zasobniku promennou i
ldc_int 5//Nacti na vrchol zasobniku konstantu 5
if_cmplt true_2//Porovnej jestli je i < 5, pokud ano skoci se na navesti true_2
ldc_int 0//i je vetsi nez 5, dosad na zasobnik nulu jako priznak toho ze podminka neplati
goto stop_3//podminka neplati a skoc na stop_3, kde se rozhoduje jestli ma cyklus pokracovat
true_2:
ldc_int 1//dosad na zasobnik jednicku jako priznak toho ze podminka plati
stop_3:
ifeq stop_1//pokud je na vrcholu zasobniku 0, skoc na stop_1 (konec cyklu), jinak nikam neskakej a pokracuj v tele cyklu
Tady zacina telo cyklu
ldc_int 0//nacti na zasobnik nulu
store 1//Uloz nulu do proměnne a (tento radek spolecne s predchozim tvori deklaraci a inicializaci proměnne a)
load 1//nacti na zasobnik a
load 0//nacti na zasobnik i
mul//vynasob i s a (a *= i -> a = a * i)
dup//okopiruj vysledek na zasobnik
store 1//uloz vysledek nasobeni do a
pop//sniz ukazatel vrcholu zasobniku o 1
Tady zacina cast updates, neboli i++
load 0//nacti na zasobnik proměnnou i
dup//okopiruj ji zasobnik
inc//zvys i o 1
store 0//uloz inkrementovane i
pop//sniz ukazatel vrcholu zasobniku o 1
goto start_0//jdi na zacatek cyklu, k overeni podminky
stop_1:
V této ukázce vidíme hned několik věcí. Víme, že inicializace cyklu se provede jen jednou a proto je první. Pak si můžeme všimnout
jak se vypořádat s podmínkou. Poté následuje přímo tělo cyklu a poslední je část s kódem který se má provést po každém průchodu cyklu.
Možná vám připadá že je v kódu několik zbytečných instrukcí. To máte pravdu. Většinu instrukcí dup a pop bychom mohli vynechat. Ale než si
začnete programovat modul optimalizací kódu,počkejte než si vysvětlíme proč tam jsou. Čili v šabloně pro cyklus for budeme kód sestavovat následujícím způsobem. Za prvé vygenerujeme kód pro inicializaci cyklu. Za druhé vložíme
návěští, které označuje začátek cyklu. Za třetí vygenerujeme kód pro podmínku. Následuje kód těla cyklu a skok na začátek cyklu. Poslední je návěští
označující konec cyklu. V kompileru to bude vypadat následovně:
case forT:
//nejdriv vygeneruj kod pro inicializaci skriptu
processFORINIT(statement->val.forS.inits);
//vloz navesti oznacujici zacatek cyklu
instruct_label("start",statement->val.forS.startlabel);
//vygenruj kod pro podminku
processEXPRESSION(statement->val.forS.condition);
//vloz skok na konec cyklu pokud podminka neplati
instruct_ifeq(statement->val.forS.stoplabel);
//vygeneruj kod pro telo cyklu
processSTATEMENT(statement->val.forS.body);
//vygeneruj kod pro aktualizaci cyklu
processEXPRESSION(statement->val.forS.updates);
//podminka souvisi s pravidlem ze kazda operace musi zasobnik zanechat ve stavu v jakem byl pred
//spustenim operace. Tz. ze pokud operace neco uklada na zasobnik, musi to pred skoncenim vsechno vyjmout, aby
//by ukazatel zasobniku byl stejny jako pred operaci
if (statement->val.forS.updates->kind == callT)
if (statement->val.forS.updates->val.callE.symbol->val.functionS->returns_value == false)
instruct_nop();
else
instruct_pop();
else
instruct_pop();
//vloz skok na zactek cyklu
instruct_lgoto(statement->val.forS.startlabel);
//vloz navesti oznacujici konec cyklu
instruct_label("stop",statement->val.forS.stoplabel);
break;
Tuto šablonu najdete ve funkci processSTATEMENT. Podívejme se ještě do funkce processEXPRESSION na šablonu pro operátor '<':
case lessT:
//vygeneruj kod pro levou stranu podminky
processEXPRESSION(expression->val.lessE.left);
//vygeneruj kod pro pravou stranu podminky
processEXPRESSION(expression->val.lessE.right);
//vloz podmineny skok ktery skoci pokud leva starna je mensi nez prava
instruct_if_cmplt(expression->val.lessE.truelabel);
//podmineny skok neskocil, vloz na zasobnik nulu jako indikaci toho ze podminka nebyly splnena
instruct_ldc_int(0);
//vloz skok na misto kde si dalsi kod overi vysledek
instruct_lgoto(expression->val.lessE.stoplabel);
//vloz navesti, sem se skoci pokud je podminka splnena
instruct_label("true",expression->val.lessE.truelabel);
//vloz na zasobnik 1, indikace splenene podminky
instruct_ldc_int(1);
//navesti oznacujici misto kde bude vlozen kod ktery rozhodne co delat podle
//vysledku porovnani
instruct_label("stop",expression->val.lessE.stoplabel);
break;
Tím bych nechal být cykly a podmínky if. Podmínku if známe z minulé lekce. Czklus while je jednodušší než for. Na začátku bude mít návěští
označující jeho začátek. Následovat bude kód zpracovávající podmínku. Pokud bude podmínka platit, nebude se nikam skákat a bude se provádět kód
následující za podmínkou, tj. tělo cyklu. Na konci těla cyklu bude skok na začátek cyklu a poslední bude návěští označující konec cyklu, na které
se skočí při nesplnění podmínky. Šablony pro další porovnávací operátory vycházejí ze stejné filosofie jako šablona pro '<'. Ukážeme si
například šablonu pro sčítání:
case plusT:
//vygeneruj kod pro levou stranu
processEXPRESSION(expression->val.plusE.left);
//vygeneruj kod pro pravou stranu
processEXPRESSION(expression->val.plusE.right);
//proved soucet
instruct_add();
break;
Jednoduché, nebo ne? Teď se pokusím vám na příkladu vysvětlit proč jsou do kódu vkládány instrukce dup a pop, které v celkovém kontextu mohou
být zbytečné jako v ukázkovém kódu pro cyklus if. Následující výraz je v Universal Scriptu platný:
5 + 8;
Pro vygenerování kódu se použije výše uvedená šablona. Výsledek sčítání bude uložen na zásobník, ale jak je vidět, výsledek se nikam neukládá.
Povím vám o jednompravidle které platí pro náš virtuální stroj založený na zásobníku. Po provedení kterékoliv akce musí být ukazatel zásobníku ve stejném stavu
jako před provedením akce. Byl-li tedy ukazatel zásobníku před tím než se přešlo na vykonání tohoto součtu například 5, musí být po vykonání součtu také 5.
To ale za použití této šablony nebude splněno, protože součet se uloží na zásobník, ale není odtud nikam přesunut. Do žádné proměnné ho neukládáme. Vrchol zásobníku by
tedy byl 6. To může ovlivnit další chod programu, pokud třeba kód následující po tomto součtu, měl pracovat s nějakou hodnotou, kterou na zásobník uložil kód
předcházející součtu, že? Proto je nutno snížit zásobník zpět na 5 vložením instrukce pop a bude to vpořádku. Proto po každém příkazu typu výraz (pokud nejde o volání funkce,
která nevrací hodnotu) je vkládána instrukce pop:
case expT:
//zpracuj vyraz
processEXPRESSION(statement->val.expression);
//podminka souvisi s pravidlem ze kazda operace musi zasobnik zanechat ve stavu v jakem byl pred
//spustenim operace. Tz. ze pokud operace neco uklada na zasobnik, musi to pred skoncenim vsechno vyjmout, aby
//by ukazatel zasobniku byl stejny jako pred operaci
if (statement->val.expression->kind == callT)
if (statement->val.expression->val.callE.symbol->val.functionS->returns_value == false)
instruct_nop();
else
instruct_pop();
else
instruct_pop();
break;
A tomu jsou přizpůsobeny i šablony pro ostatní výrazy, například pro přiřazení výrazu do proměnné:
case assignmentT:
//zpracuj výraz na pravé straně
processEXPRESSION(expression->val.assignmentE.right);
//vysledek okopiruj do zasobniku
instruct_dup();
//uloz to do promenne
instruct_store_lvalue(expression->val.assignmentE.left);
break;
Tady lze vidět že je vložena instrukce dup, která výsledek výrazu okopíruje na zásobník ještě jednou. A to právě kvůli vkládání instrukce pop.
Normálně by stačilo tuto instrukci vynechat. Výsledek výarz na pravé straně přiřazení by tak byl instrukcí store uložen do proměnné a ukazatel vrcholu zásobníku by byl
vpořádku. Ale příkaz a = 4; není volání funkce která nevrací hodnotu, bude za něj vložena instrukce pop která snižuje vrchol zásobníku o 1.
Při použití stejných hodnot ukaztele zásobníku, by tedy bez použití funkce instrukce dup byl ukazatel zásobníku snížen na hodnotu 4, což už je také špatně (pokud původní ukazatel byl 5).
Myslím že na osvětlení toho jak je genrován kód funkcí by to stačilo. Zbylé šablony si prohlédněte ve zdrojových kódech kompileru. Předposlední funkcí kterou si ukážeme
je funkce pro přidání instrukce do spojového seznamu instrukcí dané funkce:
//****************************************************************************************************************
//Funkce prida instrukci do spojoveho seznamu instrukci
//****************************************************************************************************************
void CCode::AddInstruction(CInstruction* instruction)
{
if (!m_CurrCodeStart) //pokud ukazatekl na zacetk kodu je neplatny
{ //znamena to ze do seznamu nebyla jest pridana ani prvni instrukce
m_CurrCodeStart = m_CurrCode = instruction; //nastavime proto zacatek seznamu instrukci na nove pridavanou instrukci
}
else
{
m_CurrCode->next = instruction; //ukazatel na dalsi instrukci u soucane instrukce nastavime na nove pridavanou instrukci
m_CurrCode = m_CurrCode->next; //ukazatel na soucasnou instrukci nastavime na nove pridanou instrukci
}
}
Proměnná m_CurrCodeStart je pomocná proměnná ukazující na začátek kódu/spojového seznamu instrukcí zpracovávané funkce. Pokud je tento ukazatel
NULL, znamená to že do kódu dané funkce nebyla dosud přidána jediná instrukce. Proto přidáme první instrukci na začátek kódu. Ukazatel m_CurrCode ukazuje
na poslední instrukci (pokud je přidána první instrukce, je zárověň první i poslední v seznamu), za kterou mohou být přidávány další instrukce.
Pokud je ukazatel m_CurrCodeStart, znamená to že kód funkce obsahuje minimálně 1 instrukci, proto další instrukci přidáme za poslední instrukci (nastavením jejího
ukazele next) a ukazatel na poslední instrukci přenastavíme, aby ukazoval na poslední přidanou instrukci. Ve funkci processFUNCTION jen uložíme ukazatel ukazující na začátek
vygenerovaného kódu:
//****************************************************************************************************************
//Pruchod funkcemi
//****************************************************************************************************************
void CCode::processFUNCTION(FUNCTION* function)
{
if (function->kind == localT) //sestavovat kod ma smysl jen pro lokalni funkci, u externi nezname telo
{
m_CurrCodeStart = NULL; //seznam instrukci je prazdny
function->labels = new LABEL[function->labelCount]; //vytvor pole pro navesti
m_CurrLabels = function->labels; //ukazatel na aktualni pole popisku nastav na nove vytvorene pole
if (function->statements != NULL)
processSTATEMENT(function->statements); //zpracuj telo funkce
//uloz ukazatel na seznam instrukci
function->opcodes = m_CurrCodeStart;
}
}
Poslední je funkce pro vytvoření instrukce, instance třídy CInstruction, abychom měli do seznamu instrukcí/kódu zpracovávané funkce co přidávat :)
Například funkce instruct_mul, pro vytvoření instrukce násobení:
//****************************************************************************************************************
//Prida do seznamu instrukci mul
//****************************************************************************************************************
void CCode::instruct_mul()
{
CInstruction* pInstruction = new CInstruction;
pInstruction->mul(NULL);
AddInstruction(pInstruction);
}
Je vytvořena nová instance třídy CInstruction a pak zavolána její metoda mul(), která je nastaví členskou proměnnou kind třídy na
konstantu mulCK, která značí že jde o instrukci násobení. Poslední příkaz zavolá funkci AddInstruction (výše.) která instrukci přidá do kódu zpracovávané funkce.
To je pro tuto kapitolu vše. Jak už jsem psal výše, zbytek programového kódu si prohlédněte ve zdrojovém projektu. Věm, že vám nebude dělat větší problémy.
Část 6
Část 8
|