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
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:
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)
Attachments: