Pokrok :)

Hotový projekt

Vítejte v první kapitole která zapadá do back-end části kompileru. Když se dostaneme sem, víme že skript přežil předchozí moduly a že musí být vpořádku, bez chyb. Můžeme se začít věnovat tomu, jak z něj udělat nějakou formu programu. V této části vypočítáme indexy pro proměnné a návěští ve skriptu. Nejde o nic složitého. Čísla a návěští budeme číslovat od nuly až do nějakého čísla, takže vypočítání indexu proměnné se snižuje na pouhou inkrementaci nějaké pomocné proměnné. Jinými slovy, každá další proměnná bude mít index o jedna větší než proměnná předchozí a u návěští to bude stejně. Po dokončení výpočtu indexu pro všechny proměnné funkce nám v pomocné proměnné kterou jsme použili k inkrementaci zůstane celkový počet všech proměnných - index poslední proměnné. Tuto hodnotu si uložíme jako jakýsi lokální limit (Locals Limit) funkce. Tato hodnota je pak využivána ve virtuálním stroji. Jednak pro rozhodování zda může být volána další funkce aniž by došlo k přetečení zásobníku a pak také k nastavení BSP. Mělo by to dávat smysl pokud si vzpomenete co jsem psal v teorii o virtuálním stroji pro Universal Script. Pokud ne, určitě to pochopíte v poslední kapitole o virtuálním stroji. Podíváme se na deklaraci třídy pro tento modul:

    /*Jednoduchy modul ktery pocita offsety pro navesti ve skriptech a pocita pocet promennych v dane
    funkci pricemz kazde promenne priradi index. Tento index se pak pouzije jako index do zasobniku ve VM kde
    bude promenna lezet
    */


    class CResourceCalculations
    {
    private:
       int m_CurrOffset; //pomocna promenna pro vypocet indexu promennyc
       int m_CurrLabel; //pomocna promenna pro vypocet indexu navesti
       int m_CurrLocalsLimit; //promenna pro ulozeni poctu promennych ve funkci
       int m_CurrNumOfVariables; //promenna pro ulozeni poctu vsech promennych ve funkci
    private:
       inline int Offset();
       inline int Label();
    private:
       void processTOPLEVEL(TOPLEVEL* toplevel);
       void processFUNCTION(FUNCTION* function);
       void processFORINIT(FORINIT* forinit);
       void processDECLARATION(DECLARATION* declaration);
       void processEXPRESSION(EXPRESSION* expression);
       void processSTATEMENT(STATEMENT* statement);
    public:
       void Process(SCRIPT* theScript);

       CResourceCalculations();
    };

Výpočet indexu/ů proměnné/ých

Pokud jste již koukli do zdrojáků, všimli jste si že ve funkci Offset, která slouží k vrácení indexu další proměnné není jen prostá inkrementace proměnné, ale je tam toho víc. Další chták s pomocnou proměnnou m_CurrOffset pro výpočet indexu proměnné můžete najít ve funkci processSTATEMENT u možnosti scopeT, tedy u nové skupiny příkazů. Tam si můžete všimnout že hodnotu této proměnné si ukládáme do jiné pomocné proměnné a když skončíme s kontrolou uzlu scopeT a všech jeho poduzlů, tak obnovíme původní hodnotu proměnné m_CurrOffset. Možná by vás zajímalo proč to děláme. Je to jen taková menší optimalizace, abychom neplýtvali místem v zásobníku. Ukážeme si to na příkladu:

    a = 10;
    while (a < 20)
    {
       b = a++;
    }
    c = 2 * a;

Pro tento příklad můžeme vypočítat indexy proměnných dvojím způsobem. Začínáme na indexu 0, respektive -1 protože nejdřív inkrementujeme a pak uložíme index proměnné. Proměnná a tak dostane index 0, což znamená že v zásobníku ji najdeme na offsetu BSP + 0. Další proměnná je b. Ta dostane index 1. Poslední proměnná dostane c index 2. Tak máme pro všechny vypočítán offset/index/pozici v zásobníku, která je dána hodnotou ukazatele začátku zásobníku BSP a vypočítaným indexem. Když ale o tom tak přemýšlím, až se dostaneme na výraz c = 2 * a;, nebudeme už proměnnou b potřebovat, že? Ta platila jen v těle cyklu while, protože tam je definovaná. Proč tedy nedat proměnné c také index 1 a ušetřit tak jedno místo v zásobníku. Proměnné b určitě nebude vadit, když její místo po skončení cyklu zaujme proměnná c. To je důvod proč v metodě processSTATEMENT ukládáme index proměnné:

    .
    .
    case scopeT:
       //mame-li vnoreny prikaz, treba mame for a v {} je jeho telo. V tele for cyklu mohou byt deklarovany
       //promenne ktere plati jen tam, v tele for cyklu. Tim ze si ulozime offset a pote ho zase obnovime docilimke toho, ze
       //se nam spocita opravdu jen ten pocet promennych co ve fci je, a ze dalsi promenne nasledujici po for cyklu
       //mohou prepsat v zasobniku ty z for cyklu, protoze ty stejne uz nepotrebujeme

       baseoffset = m_CurrOffset;
       processSTATEMENT(statement->val.scopeS.statement);
       m_CurrOffset = baseoffset;
       break;
    .
    .

Kvůli této optimalizaci je také nutné zvyšovat hodnotu proměnné m_CurrLocalsLimit, která počítá počet proměnných které budou uloženy v zásobníku (ne tedy počet všech proměnných ve funkci, ale kolik místa v zásobníku bude potřeba pro uložení proměnných) jen když je hodnota této proměnné menší než hodnota m_CurrOffset. Tzn. že když budeme procházet poduzly uzlu STATEMENT (kind=scopeT), nebude se hodnota této proměnná zvyšovat, aby nepočítala i proměnné jejichž místa v zásobníku mohou být použita i pro následující proměnné. Pro účely výpisu a statistiky používáme ještě proměnnou m_CurrNumOfVariables, která se inkrementuje při každém volání funkce Offset a počítá tak celkový počet proměnných. Funkce pro vypočítání indexu proměnné vypadá následovně:

    //****************************************************************************************************************
    //Fce pro ziskani cisla dalsi promenne
    //****************************************************************************************************************

    int CResourceCalculations::Offset()
    {
       m_CurrOffset++;
       if (m_CurrOffset > m_CurrLocalsLimit)
          m_CurrLocalsLimit = m_CurrOffset;
       m_CurrNumOfVariables++;

       return m_CurrOffset;
    }

Zbývá už jen funkci Offset zavolat. Index proměnné by bylo nejlepší uložit tam kde jsou uloženy i další informace o deklarovaných proměnných, tj. do uzlů se strukturou DECLARATION, která uchovává informace a deklarovaných proměnných. Naštěstí jsme při deklaraci struktury DECLARATION nezapoměli na členskou proměnnou offset, která je určena právě k uložení indexu proměnné :). Deklarace proměnných zpracuje funkce processDECLARATION:

    //****************************************************************************************************************
    //Pruchod deklaraci
    //****************************************************************************************************************

    void CResourceCalculations::processDECLARATION(DECLARATION* declaration)
    {
       switch (declaration->kind)
       {
       case formalT:
          declaration->val.formalD.offset = Offset();
          break;
       case variableT:
          declaration->val.variableD.offset = Offset();

          if (declaration->val.variableD.initialization != NULL)
             processEXPRESSION(declaration->val.variableD.initialization);
          break;
       case simplevarT:
          declaration->val.simplevarD.offset = Offset();

          if (declaration->val.simplevarD.initialization != NULL)
             processEXPRESSION(declaration->val.simplevarD.initialization);
          break;
       }

       if (declaration->next)
          processDECLARATION(declaration->next);
    }

Výpočet čísla návěští:

Funkce pro výpočet čísla/sel návěští je jednodušší. Jedná se jen o tu inkrementaci pomocné proměnné:

    //****************************************************************************************************************
    //Funkce pro ziskani cisla dalsiho navesti
    //****************************************************************************************************************

    int CResourceCalculations::Label()
    {
       return m_CurrLabel++;
    }

Jednoduché, že :) Ale radši si ještě povíme proč počítáme čísla návěští. Souvisí to s vyjádřením některých programových konstrukcí (cykly, podmínky) v assembleru skriptovacího jazyka. Pokud znáte klasický assembler pro procesory 86 a vyšší, znáte určitě instrukce jako goto. Podobné jako ty co jsou v tabulce instrukcí v teorii o virtuálním stroji. Jedná se o všechny instrukce které mají operand <adresa>. Tato adresa je offset v kódovém segmentu označující místo kam se má skočit, odkud má pokračovat vykonávání kódu. Třeba následující funkce:

    fce (a)
    {
       if (a)
          return -a;
       else
          return a;
    }

která vrací negativní hodnotu pokud zadaný parametr je nenulový, má následující reprezentaci v assembleru Universal Scriptu:

    .function fce(1)
    .locals_limit 1
    .stack_limit 1
    load 0
    ifeq else_0
    load 0
    neg
    vreturn
    goto stop_1
    else_0:
    load 0
    vreturn
    stop_1:
    .endf

Vidíme že pokud je argument funkce nulový, skočí se na návěští else_0. Když bude operand nenulový, bude znegován a pokud by tento znegovaný parametr funkce nevracela jako výsledek, pokračovali bychom až na instrukci goto (nepodmíněný skok) a skočili na návěští stop_1. V tomto ukázkovém kódu je vidět, jak je možno v assembleru jazyka naprogramovat příkaz if-else. Při nesplnění první podmínky skočíme na nějaké návěští else_, kde se nachízí kód else části podmínky. Pokud podmínka splněna je, nikam se neskáče. Na konec těla if části dáme poté skok na konec podmínky stop_. Takovýchto podmínke může být ve funkci víc a proto musíme pro každé návěští vygenerovat/vypočítat jedinečné číslo. Nelze mít ve funkci u dvou podmínek návěští else_0. To bychom nevěděli na které skočit. Mohli bychom návěští označovat sice jen vygenerovanými čísly, jako například 1:, ale když vytvoříme návěští spojením textu a čísla, tak se to přeci jen o něco líp čte. V textu můžeme přeci jenom do jisté míry uložit informaci o tom k čemu se návěští váže, s čím souvisí. Účel výpočtu návěští je doufám objasněn. Funkci která počítá číslo návěští už jsme si ukázali. Nyní se podíváme na místa kde je funkce volána. Proč je volána právě v těch místech kde je volána pochopíte v další lekci, kde budeme generovat assembly kód pro funkce a povíme si jak v assembleru jazyka vyjádřit i ostatní programové konstrukce, což by jste ale měli vědět už teď. Když jste se pustili do psaní kompileru, očekávám že budete mít i nějakou zkušenost s assemblerem :) Funkci Label, která vrací číslo návěští voláme ve funkci processSTATEMENT:

    .
    .
    case ifT:
       statement->val.ifS.stoplabel = Label();
       processEXPRESSION(statement->val.ifS.condition);
       processSTATEMENT(statement->val.ifS.body);
       break;
    case ifelseT:
       statement->val.ifelseS.elselabel = Label();
       statement->val.ifelseS.stoplabel = Label();
       processEXPRESSION(statement->val.ifelseS.condition);
       processSTATEMENT(statement->val.ifelseS.ifbody);
       processSTATEMENT(statement->val.ifelseS.elsebody);
       break;
    case forT:
       statement->val.forS.startlabel = Label();
       statement->val.forS.stoplabel = Label();
       processFORINIT(statement->val.forS.inits);
       processEXPRESSION(statement->val.forS.condition);
       processEXPRESSION(statement->val.forS.updates);
       processSTATEMENT(statement->val.forS.body);
       break;
    case whileT:
       statement->val.whileS.startlabel = Label();
       statement->val.whileS.stoplabel = Label();
       processEXPRESSION(statement->val.whileS.condition);
       processSTATEMENT(statement->val.whileS.body);
       break;
    .
    .

Pak také ve funkci processEXPRESSION:

    .
    .
    case notT:
       expression->val.notE.truelabel = Label();
       expression->val.notE.stoplabel = Label();
       processEXPRESSION(expression->val.notE.expression);
       break;
    .
    .
    case equalsT:
       expression->val.equalsE.truelabel = Label();
       expression->val.equalsE.stoplabel = Label();
       processEXPRESSION(expression->val.equalsE.left);
       processEXPRESSION(expression->val.equalsE.right);
       break;
    case nequalsT:
       expression->val.nequalsE.truelabel = Label();
       expression->val.nequalsE.stoplabel = Label();
       processEXPRESSION(expression->val.nequalsE.left);
       processEXPRESSION(expression->val.nequalsE.right);
       break;
    case lessT:
       expression->val.lessE.truelabel = Label();
       expression->val.lessE.stoplabel = Label();
       processEXPRESSION(expression->val.lessE.left);
       processEXPRESSION(expression->val.lessE.right);
       break;
    case greaterT:
       expression->val.greaterE.truelabel = Label();
       expression->val.greaterE.stoplabel = Label();
       processEXPRESSION(expression->val.equalsE.left);
       processEXPRESSION(expression->val.equalsE.right);
       break;
    case lequalsT:
       expression->val.lequalsE.truelabel = Label();
       expression->val.lequalsE.stoplabel = Label();
       processEXPRESSION(expression->val.lequalsE.left);
       processEXPRESSION(expression->val.lequalsE.right);
       break;
    case gequalsT:
       expression->val.gequalsE.truelabel = Label();
       expression->val.gequalsE.stoplabel = Label();
       processEXPRESSION(expression->val.gequalsE.left);
       processEXPRESSION(expression->val.gequalsE.right);
       break;
    .
    .
    case andT:
       expression->val.andE.falselabel = Label();
       processEXPRESSION(expression->val.andE.left);
       processEXPRESSION(expression->val.andE.right);
       break;
    case orT:
       expression->val.orE.truelabel = Label();
       processEXPRESSION(expression->val.orE.left);
       processEXPRESSION(expression->val.orE.right);
       break;
    .
    .

A máme za sebou šestou lekci. Na zbytek kódu funkcí se podívejte do zdrojového projektu k této lekci, ale jako vždy, to nejdůležitější jsme si ukázali tady.

Část 5
Část 7