Prekladač (bez zotavenia)

Ciele
  1. Pochopiť princíp prekladu výrazov do strojového kódu s využitím zásobníka.
  2. Oboznámiť sa s kódom generátora a funkciami pre zápis kódu pre Computron VM do výstupného súboru.
  3. Naprogramovať funkcie realizujúce zápis jednotlivých konštrukcií jazyka aritmetických výrazov do výstupného súboru v jazyku inštrukcií Computron VM.
  4. Vhodne použiť vytvorené funkcie v kóde intrpretátora a zrealizovať tak rekurzívny prekladač do jazyka inštrukcií Computron VM.
Úvod
    Úlohou dnešného cvičenia bude vytvoriť prekladač do jazyka inštrukcií virtuálneho stroja Computron VM. To znamená, že namiesto okamžitej interpretácie analyzovaného programu sa bude generovať kód (postupnosť inštrukcií), ktorý zabezpečí vykonanie potrebných operácií v Computron VM.
Postup

  1. Pre výraz zadaný používateľom je potrebné vygenerovať postupnosť inštrukcií Computron VM, ktorá zabezpečí jeho vyhodnotenie.

    Úloha: Napíšte takúto postupnosť inštrukcií pre výraz " 1+2".

    Zásadným problémom pri preklade výrazov je však (1) určenie poradia, v akom sa operácie majú vykonávať, a tiež (2) ukladanie medzivýsledkov výpočtu.

    Úloha: Ako bude vyzerať preklad výrazu " 1*2+3*4"? Ako vytvoriť program, ktorý bude automaticky prekladať takéto alebo ešte zložitejšie výrazy?

    Riešením prvého problému je prevod výrazu do postfixnej formy, kde sa operácie vykonávajú v tom poradí v akom sa vyskytujú. Riešením druhého problému je použitie zásobníka. Princíp výpočtu výrazu v postfixnom tváre s použitím zásobníka je znázornený na obrázku.

    Obr.: : Výpočet výrazu s využitím zásobníka

    Pri preklade výrazu je teda dostatočné vygenerovať postupnosť operácií vloženia hodnoty do zásobníka a výpočtu s hodnotami na vrchole zásobníka.

    Úloha: Prepíšte do postfixného tvaru výraz " 5*x^2 + 10*y - 8".

  2. Úlohou dnešného cvičenia bude upraviť kód interpretátora z minulého cvičenia tak, aby výsledkom bol prekladač do jazyka inštrukcií virtuálneho stroja Computron VM.

    Úloha: Stiahnite si a preštudujte zdrojový kód generátora a pridajte ho do projektu interpretátora. Kód obsahuje množinu kódov všetkých inštrukcií stroja Computron vo forme enumeračného poľa enum OP_Code { .. };, pomocné funkcie pre využitie v prekladači a funkcie pre generovanie kódu.
    Poznámka: Uvedomte si fakt, že zoznam kódov inštrukcií stroja Computron v generátore je vlastne interná reprezentácia jazyka Computron VM v prekladači.

    Na zápis jednej inštrukcie alebo hodnoty do výstupného binárneho súboru je možné použiť funkciu void put_word(short value). Argumentom tejto funkcie môže byť kód inštrukcie z poľa OP_Code alebo číselná hodnota.

    Príklad zápisu inšrukcie 'STA 2': 

    
put_word(STA);
put_word(2);

    V kóde sa nachádza aj pomocná premenná void put_op_attr(short op, short value), ktorá uľahčuje zápis inštrukcií s atribútom.

    Inšrukciu 'STA 2' teda vieme zapísať aj ako: 

    
put_op_attr(STA, 2);

    Pre výpis alfanumerického znaku je potrebné použiť inštrukciu OUTC, pričom v akumulátore musí byť uložený ASCII kód daného znaku. Príklad: 

    
put_op_attr(LDAM, '=');
put_word(OUTC);
    Poznámka: Všimnite si, že funkcia put_word inkrementuje premennú address, ktorá nám uchováva akutálnu adresu poľa, do ktorého zapisujeme inštrukcie a hodnoty.

  3. Okrem funkcií pre zápis do výstupného súboru modul generator.c obsahuje aj funkcie pre generovanie inštrukcií zodpovedajúcich jednotlivým operáciám výsledného programu. Ich význam je nasledovný:

    • write_begin(short num_vars) vygeneruje začiatok programu vrátane oblasti pre ukladanie premenných (ich počet je zadaný parametrom),
    • write_end() vygeneruje koniec programu, teda inštrukciu EXIT,
    • write_result() — kód pre výpis výsledku výpočtu,
    • write_number(short value) — kód pre vloženie čísla do zásobníka,
    • write_var(short index) — kód pre vloženie hodnoty premennej so zadaným indexom do zásobníka,
    • write_add() — kód pre sčítanie dvoch čísel uložených na vrchole zásobníka,
    • write_sub() — kód pre odčítanie dvoch čísel uložených na vrchole zásobníka,
    • write_mul() — kód pre vynásobenie dvoch čísel uložených na vrchole zásobníka,
    • write_div() — kód pre vydelenie dvoch čísel uložených na vrchole zásobníka,
    • write_ask_var(short index, char *name) — kód pre načítanie hodnoty premennej od používateľa.
    • write_string(const char *str) — kód pre vypísanie reťazca znakov na obrazovku.
    Úloha: Doplňte chýbajúci kód funkcií pre zápis inštrukcií stroja Computron do výstupného binárneho súboru.

  4. Vytvorené funkcie pre generovanie kódu je potrebné použiť v syntaktickom analyzátore namiesto priamej interpretácie výrazu.

    Úloha: Pridajte vytvorenie výstupného súboru a zápis inicializačnej časti kódu do hlavnej funkcie main: 
    
int main(int argc, char** argv) {

    ...

    FILE *output_file = fopen("program.bin", "wb");
    init_generator(output_file);

    program();

    generate_output();
    fclose(output_file);
    printf("Program vygenerovany v program.bin\n");

    getchar();
    return 0;
}
    Úloha: Do funkcie term() pridajte do vetvy VALUE príkazu switch zápis čísla do binárneho súboru pomocou funkcie write_number(int value). 
    
...
case VALUE:
    write_number(lex_attr);
    next_symbol();
    break;
...
    Úloha: Do funkcie expr vhodne doplňte použitie funkcií write_add() a write_sub() tak, aby do výstupného súboru generovali výpočet operácie sčítania alebo odčítania pomocou zásobníka. 
    
...
while (...) {
    operator = lex_symbol;

    ...
    case PLUS:
        write_add();
        break;
    ...
}
...
    Úloha: Pridajte volanie funkcie write_begin(int num_vars) ešte pred generovaním ostatných časti kódu. Ak nemáte implementovanú podporu premených, použite hodnotu 0 ako parameter.
  5. V tomto kroku otestujeme vytvorený prekladač. Vstupom prekladača je jazyk aritmetických výrazov a výstupom je binárny súbor v jazyku inštrukcií stroja Computron. Po spustení by mal prekladač teda vygenerovať súbor program.bin, ktorý je spustiteľný v Computron VM.
    Poznámka: Výsledok prekladu si môžete priebežne kontrolovať aj pomocou nástroja disassembler z cvičenia 2.
Doplňujúce úlohy
    Úloha: Implementujte prekladač zátvorkových aritmetických výrazov do jazyka stroja Computron do vášho zadania B.
    Úloha: Doplňte preklad operácie mocniny. Keďže Computron VM nemá špeciálnu inštrukciu pre výpočet mocniny, potrebujete ju realizovať cyklickým opakovaním násobenia. Ak budete používať inštrukcie pre vetvenie, nezabudnite, že kód obsauhje premennú address, pomocou ktorej si viete zistiť adresu pre skoky.
comments powered by Disqus