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