Zkouška 19.01.2022 - Simplified Intermediate Code Interpreter

Základní kurs objektově orientovaného programování v C++. Třídy a objekty, zapouzdření, metody, plymorfismus. Abstraktní datové typy, přetěžování. Kontejnery, iterátory, algoritmy. Šablony, generické programování, kompilační polymorfismus. Výjimky. Bezpečné a přenositelné programování, vazby na OS.
neznamymatfyzak
Matfyz(ák|ačka) level I
Příspěvky: 4
Registrován: 28. 6. 2021 20:50
Typ studia: Informatika Bc.

Zkouška 19.01.2022 - Simplified Intermediate Code Interpreter

Příspěvek od neznamymatfyzak »

Při zkoušce se mohl libovolně používat internet, s výjimkou komunikace s lidmi (nebylo povolené klást vlastní otázky na stackoverflow).
Také se samozřejmě nemohlo hledat samotné řešení problému.

Zadání úlohy z recodexu:

Úkolem je vytvořit interpreter zjednodušeného mezikódu, který je inspirovaný CILem z .NETu a bytecodem v Javě.
Vstup
Argumenty programu

Při spuštění je programu předán seznam souborů, které má jeden po druhém spustit, např.: program kod1.txt kod2.txt kod3.txt Můžete předpokládat, že soubory existují a jsou čitelné.

Vstupní soubor

Každý vstupní soubor musí být vyhodnocen odděleně od ostatních - tedy případný rozpracovaný stav po předchozím souboru je vždy potřeba před vyhodnocením dalšího uklidit. Syntaxe vstupního souboru je následující:
  • Pokud se kdekoliv na řádce objeví znak #, značí to začátek komentáře. Tento znak a všechny znaky po něm následující až do konce řádku musejí být ignorovány.
  • Program je rozdělený na funkce, každá funkce začíná řádkem .function F N, kde F je název funkce (neobsahující bílé znaky) a N je počet jejích argumentů (rozsah: 0-10).
  • Každý řádek v rámci funkce obsahuje nanejvýše jednu instrukci, ta se může skládat z jednoho a více slov oddělených mezerami nebo tabulátory (i více než jedním takovým znakem za sebou). Funkce je ukončená instrukcí ret.
  • Před každou instrukcí se může nacházet nanejvýše jedno návěští. Jedná se o slovo (neobsahující bílé znaky) končící na znak :. Jméno návěští je unikátní v celém programu.
Funkce

Každý vstupní soubor musí obsahovat funkci Main, která přijímá 0 argumentů a v níž výpočet začíná. Prvních 5 testů obsahuje pouze tuto funkci a žádnou jinou, pro jejich splnění (a zisk 35 bodů) stačí tedy pouze ignorovat první řádek a instrukcí ret ukončit výpočet. Pokud chcete získat dalších 15 bodů za pokročilou funkcionalitu, je potřeba všechny funkce ze vstupu správně naparsovat a korektně naimplementovat instrukce call a ret.

Instrukce

Veškeré výpočty v interpreteru probíhají na 32-bitových celých číslech se znaménkem. Interpreter má 10 lokálních proměnných indexovaných od 0, které musejí být před interpretací každé funkce inicializované na hodnotu 0 (až na předané argumenty, vizte instrukci call). Kromě toho používá vyhodnocovací zásobník, jehož velikost není omezená. Jednotlivé instrukce s tímto zásobníkem pracují různým způsobem:

Základní (35 bodů)
  • ldconst C
    Uloží na vrchol zásobníku celočíselnou konstantu C.
  • stloc I
    Odebere z vrcholu zásobníku aktuální hodnotu a uloží ji do proměnné I.
  • ldloc I
    Uloží na vrchol zásobníku aktuální hodnotu proměnné I.
  • pop
    Odebere hodnotu z vrcholu zásobníku.
  • out
    Vypíše aktuální hodnotu na vrcholu zásobníku a mezeru.
  • add
    Odebere dvě hodnoty z vrcholu zásobníku a uloží na něj jejich součet.
  • mul
    Odebere dvě hodnoty z vrcholu zásobníku a uloží na něj jejich součin.
  • sub
    Odebere dvě hodnoty z vrcholu zásobníku a uloží na něj jejich rozdíl (číslo první odebrané ze zásobníku je pravý operand).
  • div
    Odebere dvě hodnoty z vrcholu zásobníku a uloží na něj jejich podíl (číslo první odebrané ze zásobníku je pravý operand).
  • lt
    Odebere dvě hodnoty z vrcholu zásobníku a uloží na něj číslo 1, pokud je druhé odebrané číslo menší než první odebrané, jinak 0.
  • gt
    Odebere dvě hodnoty z vrcholu zásobníku a uloží na něj číslo 1, pokud je druhé odebrané číslo větší než první odebrané, jinak 0.
  • goto L
    Nepodmíněný skok na instrukci s návěštím L.
  • brt L
    Skok na instrukci s návěštím L, pokud je na vrcholu zásobníku číslo různé od 0.
  • brf L
    Skok na instrukci s návěštím L, pokud je na vrcholu zásobníku 0.
Pokročilé (15 bodů)
  • call F
    Odebere z vrcholu zásobníku n hodnot, kde n je počet argumentů funkce F. Následně si uloží stávající stav interpretace funkce (hodnoty lokálních proměnných, stav zásobníku a "ukazatel" na instrukci, která má být vykonána po návratu z funkce) a rekurzivně (není nutné implementovat rekurzí, lze i např. zásobníkem) zavolá interpretaci funkce F (tj. první instrukci následující po její definici). V rámci této interpretace je prvních n lokálních proměnných nahrazeno dříve odebranými argumenty (argument s nejvyšším indexem je argument první odebraný ze zásobníku, obdobně jako u instrukcí sub či div).
  • ret
    Odebere hodnotu z vrcholu zásobníku hodnotu. Pokud se jednalo o funkci nejvyšší úrovně (tj. funkci, která pomocí instrukce call nevolala žádnou jinou), hodnota se ignoruje a program se ukončí. V opačném případě se pouze ukončí vyhodnocování aktuální funkce a návratová hodnota je umístěna na vrchol vyhodnocovacího zásobníku volající funkce (tj. funkce, odkud byla tato funkce zavolaná pomocí instrukce call). Výpočet následně pokračuje v kontextu volající funkce instrukcí následující za instrukcí call.
Výstup

Pro každý vstupní soubor vypíše program na samostatný řádek jeho název následovaný dvojtečkou, následně provede vyhodnocení programu, které v sobě může zahrnovat i výstupy příkazu out.

Pokud dojde k nějaké chybě v programu, vypíše řádek syntax error (např. neexistující příkaz), resp. runtime error (např. při chybějících argumentech na zásobníku) a ukončí vykonávaní programu. Pokus o skok na neexistující návěští či zavolání neexistující funkce (vč. Main na začátku programu) skončí runtime error.

Testovací vstupy

Ke stažení zde:
vstupy.zip
(2.78 KiB) Staženo 108 x
Jednotlivé testy v ReCodExu odpovídají následujícím vstupům:

Syntaktická chyba: synerr1.txt, synerr2.txt, synerr3.txt
Běhová chyba: runerr1.txt, runerr2.txt
Krajní případy správné syntaxe: synok.txt
Funkce sgn: sgn1.txt, sgn2.txt, sgn3.txt
Výpis faktoriálu čísel od 1 do 6: fact5.txt
Pokročilé: Volání funkce sgn: fn_sgn.txt
Pokročilé: Fibonacciho čísla: fn_fibo.txt
Pokročilé: Umocňování: fn_pow.txt

Očekávaný výstup při zavolání programu s argumenty synerr1.txt synerr2.txt synerr3.txt runerr1.txt runerr2.txt synok.txt sgn1.txt sgn2.txt sgn3.txt fact5.txt fn_sgn.txt fn_fibo.txt fn_pow.txt:

Kód: Vybrat vše

synerr1.txt:
syntax error

synerr2.txt:
syntax error

synerr3.txt:
syntax error

runerr1.txt:
runtime error

runerr2.txt:
runtime error

synok.txt:
4

sgn1.txt:
1

sgn2.txt:
-1

sgn3.txt:
0

fact5.txt:
1 2 6 24 120 720

fn_sgn.txt:
1 -1 0

fn_fibo.txt:
0 1 1 2 3 5 8 13 21

fn_pow.txt:
1 25 3 125 81
Hodnocení

Na základě splnění funkcionality (základní + pokročilé instrukce) je možné z ReCodExu získat až 50 bodů, pokud však řešení nezíská ani 30 bodů, není přidělen bod žádný (požadavek na funkčnost se chápe jako nesplněný). U funkčních řešení bude dále přiděleno +- 10 bodů (tj. při horší kvalitě řešení se mohou body i snížit) na základě kvality kódu.

Příklady důvodů pro získání bodů:

vhodné rozdělení funkcionality
OOP
popisné názvy proměnných, funkcí a tříd
efektivní kód (např. vyvarování se opakovaného parsování)
vhodné používání const

Příklady důvodů pro ztrátu bodů:

warningy
nepřehledný kód (např. příliš mnoho operací na jedné řádce)
obskurity (např. goto)
Odpovědět

Zpět na „NPRG041 Programování v C++“