Počet bodov:
Program:  20b

Ak máte akékoľvek otázky k tejto úlohe, napíšte Mišovi Štrbovi na .

Paulínka si otvorila zadanie tejto úlohy (ale až po zverejnení … naozaj!) a zvolala:

“Čo si tí KSPáci zase vymysleli? Bojím, bojím, vyzerá to na nejaký programovací jazyk. To od nás chcú, aby sme si naprogramovali vlastný jazyk? Ja si pamätám, na Zenite raz bola taká úloha… Animassembler, to bolo škaredééé.”

Áno, Paulínka, uhádla si to správne. V tejto úlohe si máte naprogramovať programovací jazyk. Ale nie vlastný, my sme vám už nejaký vymysleli.

“Och, to bude určite nejaký škaredý ezoterický jazyk, nejaké nenaprogramovateľné veci, bojím, bojím. No, určite to nebude normálny programovací jazyk, bude to niečo šialené.”

Tak, sklamem ťa Paulínka, nie je to žiaden ezoterický jazyk. Ale báť sa môžeš stále. Je to totiž úplne normálny programovací jazyk. Podobný, ako skoro všetky, v ktorých programujete KSP. Tak, poďme sa na tento programovací jazyk pozrieť.

VEĽKÉ UPOZORNENIE: Pre získanie čiastočných bodov stačí naprogramovať len veľmi malú časť tohto jazyka a aj to veľmi nekompletným spôsobom. Nikdy sa nevzdávajte.

Zoznámte sa

func main() {
    print 1;
}

Takto vyzerá Hello, World! v Teatrálnom Programovacom Jazyku (ďalej len TPJ). V skutočnosti je to skôr Hello, one!, keďže program vypisuje číslo 1. Tento jazyk totiž nepozná stringy (to je pre vás asi potešujúca správa). Predtým, než sa pozrieme na syntax TPJ detailnejšie, ukážme si ešte zopár príkladov.

Program, ktorý vypíše súčin \(7 \times 9\):

func main() {
    var a;
    var b;

    a = 7;
    b = 9;

    print a*b;
}

Program, ktorý vypíše čísla od jedna po desať:

func main() {
    var i;
    i = 1;
    while i <= 10 {
        print i;
        i = i + 1;
    }
}

Program s funkciou na počítanie faktoriálu:

func factorial(n) {
    if n <= 1 {
        return 1;
    }
    return n * factorial(n-1);
}

func main() {
    print factorial(7);
}

Základy

TPJ je kompilovaný jazyk. To znamená, že ak použijete nedeklarovanú premennú alebo zadáte zlý počet parametrov funkcie alebo niečo podobné, tak program sa neskompiluje. Napríklad tento program by sa neskompiloval, lebo premenná b nebola deklarovaná:

func main ( ) {
    var a;
    print b;
}

Nedodržanie pravidiel jazyka treba vždy vyhodnotiť ako COMPILATION ERROR.

Každý program v jazyku TPJ musí mať funkciu main(). Neskôr sa pozrieme aj na to, ako písať v TPJ vlastné funkcie. Funkcia main() vyzerá takto:

func main() {

}

Funkcia main() nesmie brať žiadne parametre. Program v jazyku TPJ sa začne spustením funkcie main(). Teraz sa pozrieme na všetky vymoženosti, ktoré môžeme písať dovnútra funkcie main().

Premenné

Všetky premenné v jazyku TPJ sú typu signed 32-bit integer, čiže normálny int v C. Sú to celé čísla vyjadrené pomocou 32 bitov v doplnkovom binárnom kóde. Nekontroluje sa pretečenie (overflow), takže tento program vypíše -2147483648:

func main() {print 2147483647 + 1;}

Premennú v jazyku TPJ deklarujeme pomocou kľúčového slova var, takto:

var meno_premennej;

Pred použitím je nutné premennú deklarovať. Priamo po deklarácii má premenná hodnotu 0.

Názov premennej môže byť ľubovoľný reťazec zložený z veľkých a malých písmen anglickej abecedy, číslic a podtržítka (_). Nesmie však začínať číslicou. Nasledujúci program ukazuje deklarovanie premenných (vypíše tri nuly):

func main() {
    var a;
    var b;
    print a;
    print b;

    var uplne_zmysluplna_premenna_123;
    print uplne_zmysluplna_premenna_123;
}

Premenné môžu byť deklarované hocikde vo funkcii, avšak použité môžu byť až po deklarácii. Navyše, TPJ je úplne pokrokový jazyk a nemá globálne premenné. Každá premenná musí byť deklarovaná vo funkcii.

Nie je možné dvakrát deklarovať tú istú premennú. Tento program sa neskompiluje:

func main() {
    var a;
    print a;

    var a;
}

Do premennej je možné priradiť hodnotu pomocou príkazu =. Pozor, = nie je operátor, nie je možné ho použiť vo výrazoch.

func main() {
    var hello;
    hello = 42;
    hello = 47;
}

Výrazy

Číslo v jazyku TPJ je ľubovoľný reťazec číslic v desiatkovej sústave. Číslo teda môže začínať veľa nulami, ktoré nemajú žiaden význam. Ak sa číslo nezmestí do 32 bitov, zoberie sa jeho zvyšok po delení \(2^{32}\) a ten sa interpretuje v doplnkovom binárnom kóde. Znamienko - nie je súčasťou čísla. Namiesto toho je to unárny operátor. -123 je teda číslo 123, na ktoré je použitý operátor -.

Operátory

Jazyk TPJ podporuje nasledujúce operátory:

  • Matematické unárne:
    • + – nespraví nič, zachová hodnotu operandu
    • - – vráti hodnotu operandu vynásobenú -1
  • Matematické binárne:
    • + – sčítanie
    • - – odčítanie
    • * – násobenie
    • / – celočíselné delenie
    • % – zvyšok po delení, výsledok má znamienko ľavého operandu – ako v jazyku C (a nie ako v Pythone)
  • Porovnávacie:
    • == – vráti 1, ak sa operandy rovnajú, inak 0
    • != – vráti 1, ak sa operandy nerovnajú, inak 0
    • < – vráti 1, ak je ľavý operand menší ako pravý, inak 0
    • > – vráti 1, ak je ľavý operand väčší ako pravý, inak 0
    • <= – vráti 1, ak je ľavý operand menší alebo rovnaký ako pravý, inak 0
    • >= – vráti 1, ak je ľavý operand väčší alebo rovnaký ako pravý, inak 0
  • Logické unárne:
    • ! – pre nulu vráti 1, pre hocičo nenulové vráti 0
  • Logické binárne:
    • && – logické a, vráti 1, ak sú oba operandy nenulové, inak 0
    • || – logické alebo, vráti 1, ak je aspoň jeden z operandov nenulový, inak 0

Pri vyhodnocovaní operátorov && a || sa vždy vyhodnotia oba operandy.

Ak dôjde k deleniu (/) alebo modulovaniu (%) nulou, tak výsledok je vždy nula. Nasledujúci program vypíše 5:

func main() {
    print 5 + 5/(5 - 5);
}

Vyhodnocovanie výrazov

Operátory v jazyku TPJ nemajú žiadne prednosti, všetky operátory sú rovnocenné a výrazy sa vyhodnocujú sprava doľava. Napríklad tento výraz sa vyhodnotí na -280 a nie na 37:

8*4-3*2+11

Výrazy môžete aj zátvorkovať. Zátvorky sú jediný spôsob, ako explicitne určiť poradie vyhodnocovanie výrazu. Takto uzátvorkovaný výraz sa už vyhodnotí na 37:

((8*4) - (3*2)) + 11

V takomto výraze sa najprv vyhodnotí funkcia c(), potom b() a nakoniec a():

a() + b() + c()

Bloky

Všetko, čo sa nachádza medzi kučeravými zátvorkami { a } je blok. Do programu v jazyku TPJ môžete bloky vkladať do seba podľa ľubovôle. Napríklad toto je úplne platný program:

func main() {
    {
        {
            {}{{}}{{{}}}
        }
        {
            {{{}}}{{}}{}
        }
    }
    {
        { { } }
    }
    {
        {
        }
        {
        }
        {
        }
    }
}

V každom bloku môžete deklarovať premenné. Po ukončení bloku však platnosť všetkých premenných, ktoré v ňom boli deklarované zanikne. Napríklad tento program sa kvôli tomu neskompiluje, pretože premenná a zanikla po ukončení bloku, v ktorom bola deklarovaná.

func main() {
    {
        var a;
        a = 10;
        print a;
    }

    print a;
}

Nasledujúci program sa taktiež neskompiluje, ale z iného dôvodu a síce preto, že je zakázané jednu premennú znova deklarovať, ak jej platnosť ešte nezanikla:

func main() {
    var a;

    {
        var a;
        a = 10;
        print a;
    }

    print a;
}

Blok samozrejme nežije len sám pre seba. Obsahuje príkazy, ďalšie bloky a podobne. Do bloku je možné umiestňovať nasledujúce veci (po veciach, ktoré majú v zozname nižšie na konci napísanú bodkočiarku, tá bodkočiarka musí byť):

  • iný blok – { }
  • deklarácia premennej – var meno_premennej;
  • priradenie hodnoty do premennej – premenna = 2 * x + 13 - factorial(10);
  • vetvenie if (vysvetlené nižšie) – if x == 3 { ... }
  • cyklus while (vysvetlený nižšie) – while x < 10 { ... }
  • príkaz return (vysvetlený nižšie) – return vysledok;
  • príkaz print (vysvetlený nižšie) – print cislo;
  • výraz ukončený bodkočiarkou – 3 + 3 + funkcia(10);
  • prázdny príkaz – ;

Vetvenie if

Jazyk TPJ podporuje klasické if, ktorý poznáte z iných jazykov. Vyzerá takto (<blokN> a <podmienkaN> sú placeholdery pre skutočné výrazy a bloky príkazov):

if <podmienka1> {
    <blok1>
} else if <podmienka2> {
    <blok2>
} else if <podmienka3> {
    <blok3>
} else {
    <blok4>
}

Vetvy else if a else sú samozrejme nepovinné. V jazyku TPJ nemusia byť okolo podmienky v príkaze if zátvorky, avšak blok príkazov, ktoré sa majú vykonať ak podmienka platí, musí byť uzavretý v kučeravých zátvorkách. Nasledujúce vetvenia if nie sú skompilovateľné:

if x == 3 {
    print x;
    else{
        print 10;
    }
}

if ( x == 3 )print x;

Prvý príklad nie je skompilovateľný preto, že vetva else nemá nad sebou if a druhý preto, že okolo príkazu print x nie sú kučeravé zátvorky.

Cyklus while

Cyklus while je jediný cyklus podporovaný jazykom TPJ. Vyzerá veľmi jednoducho:

while <podmienka> {
    <blok>
}

To je všetko, príkazy medzi kučeravými zátvorkami sa budú vykonávať pokým bude platiť podmienka. Jazyk TPJ nepodporuje príkazy break ani continue známe z iných jazykov. Tešte sa.

Podobne ako vo vetvení if, ani v cykle while nie je nutné dávať podmienku do zátvoriek, ale je nutné dávať blok príkazov, ktoré sa majú vykonávať do kučeravých zátvoriek.

Príkaz print

Jazyk TPJ nevie načítavať žiaden vstup. Každý program teda pri každom spustení vypľuje ten istý výstup. Na výstup je možné vypisovať pomocou príkazu print. Tento príkaz vypíše jedno číslo ukončené znakom nového riadku. Vyzerá takto:

print <výraz>;

Funkcie

Doteraz sme prebrali všetko, čo je možné písať dovnútra funkcie. Jazyk TPJ však podporuje aj vytváranie vlastných funkcii. Každá funkcia má svoje meno a parametre. Definujeme ju takto:

func <názov_funkcie>(<parameter1>, <parameter2>, <parameter3>, ...) {
    ...
}

Pre názov funkcie aj názvy parametrov platia rovnaké obmedzenia ako pre názvy premenných. Funkcia môže brať ľubovoľný počet parametrov. Po spustení funkcie sa parametre správajú rovnako ako lokálne premenné, ktorých počiatočné hodnoty sú zadané pri volaní.

Nie je možné definovať dve funkcie s rovnakým meno.

Všetky funkcie v jazyku TPJ vracajú 32-bitový signed integer a všetky premenné sú tohto typu.

Každý príkaz sa musí nachádzať vo funkcii. Navyše je zakázané definovať funkciu vo funkcii. Tieto dva kódy by sa neskompilovali:

Tu je príkaz mimo funkcie:

func main() {
    print 1;
}

print 2;

A tu je funkcia vo funkcii:

func main() {
    func vnorena() {
        return 4;
    }

    print vnorena();
}

Príkaz return

Logicky, keďže funkcia má vracať nejakú hodnotu, potrebujeme na to prostriedky. Tie nám poskytuje príkaz return. Vyzerá takto:

return <výraz>;

Po vykonaní príkazu return funkcia skončí a riadenie sa odovzdá volacej funkcii, pričom funkcia sa vyhodnotí na vrátenú hodnotu.

Napríklad táto funkcia berie ako parametre dve čísla a vracia menšie z nich:

func min(a, b) {
    if a < b {
        return a;
    }
    return b;
}

Alebo táto funkcia vypočíta faktoriál čísla n:

func factorial(n) {
    var result;
    result = 1;

    var i;
    i = 2;
    while i <= n {
        result = result*i;
        i = i+1;
    }

    return result;
}

V prípade, že funkcia skončí bez toho, aby nastal príkaz return, tak funkcia automaticky vráti hodnotu 0.

Volanie funkcii

Funkcie sa volajú rovnako ako vo väčšine programovacích jazykov. Volanie funkcie je výraz, ktorý sa vyhodnotí na návratovú hodnotu funkcie. Napríklad nasledujúci výraz sa vyhodnotí na 1 (používame funkcie definované vyššie):

factorial(4) == min(24,47)

Volanie funkcie má syntax <názov_funkcie>(<výraz1>, <výraz2>, ..). Volaná funkcia musí existovať a musí byť volaná so správnym počtom parametrov. Avšak nemusí byť definovaná pred použitím. Takýto kód je úplne v poriadku:

func main() {
    print add(2, 3);
}

func add(a, b) {
    return a+b;
}

Rekurzia

Jazyk TPJ podporuje rekurziu. Funkcia teda môže volať sama seba a funguje to, ako keby volala inú funkciu (teda po skončení rekurzívneho volania ostanú lokálne premenné funkcie nedotknuté).

Uveďme si dva príklady.

Prvý je funkcia na vypisovanie Fibonacciho čísel. Nasledujúci program vypíše prvých 20 čísel tejto postupnosti:

func fibonacci (a, b, n) {
    if n > 0 {
        print a;
        fibonacci(b, a + b, n-1);
    }
}

func main() {
    fibonacci(0,1,20);
}

Nasledujúci program vypíše postupne čísla 10 10 9 9 8 8 ... 1 1 (samozrejme, na osobitných riadkoch). Nepoužíva priamo rekurziu, ale robí akýsi “ping-pong” medzi dvomi funkciami:

func a(n) {
    if n > 0 {
        print n;
        b(n);
    }
}

func b(n) {
    print n;
    a(n - 1);
}

func main() {
    a(10);
}

Úloha

Hurá, konečne sme si popísali celý náš krásny jazyk TPJ. Tak čo je vlastne úloha? Váš program dostane na vstupe nejaký kód v jazyku TPJ. Ak je tento kód chybný (nespĺňa niektorú z podmienok uvedených v popise jazyka), tak váš program má vypísať COMPILATION ERROR.

V opačnom prípade má spustiť program, ktorý dostal na vstupe a vypísať jeho výstup. Je zaručené, že žiaden zo vstupných programov na testovači sa nezacyklí a ani nebude bežať príliš dlho.

Všimnite si krásu jazyka TPJ. Ak sa už raz skompiluje, nie je možné aby sa počas behu zrúbal.

Formát vstupu

Na vstupe máte zdrojový kód nejakého programu v jazyku TPJ. Kód je ukončený znakom konca súboru.

Formát výstupu

V prípade, že program na vstupe nie je korektný, vypíšte reťazec COMPILATION ERROR. V opačnom prípade vypíšte \(n\) riadkov, kde \(n\) je počet vykonaných príkazov print vo vstupnom programe. Na každom z týchto riadkov nech sa nachádza číslo, ktoré daný príkaz print vypísal.

Sady

Aj keď to vyzerá ťažko, získať čiastočné body naozaj nie je ťažké. Takýto bude obsah testovacích sád:

  1. Obyčajné príkazy print s jednoduchými výrazmi bez zátvoriek. Všetko je pekne naformátované, odsadené, jeden príkaz na jednom riadku. Všetky operátory a čísla sú oddeľované medzerami.

Input:

func main() {
    print 2;
    print 3;
    print 5 + 2 % 7;
}

Output:

2
3
7
  1. Teraz už vo výrazoch pribudli aj zátvorky. Operátory a čísla už nemusia byť oddelené medzerami.

Input:

func main() {
    print (2 + 2) - (3 + 3);
    print (12 % 3) + 5 / 3 * ((9 + 9) - 2);
}

Output:

-2
0
  1. Deklarácie premenných. Priraďovanie hodnôt a výrazov do premenných. Žiadne chyby kompilácie.

Input:

func main() {
    var a;
    a = 3;

    var b;
    b = 7;

    print (a + b)%47;
}

Output:

10
  1. Použitie blokov. Treba zachytiť chybu pri kompilácii kvôli použitiu nedeklarovanej premennej alebo použitiu premennej mimo svojej scope.

Input:

func main() {
    var a;

    {
        var a;
        var b;
        b = 5;
        print b;
    }

    print a;
    print b;
}

Output:

COMPILATION ERROR
  1. Pribudli štruktúry if a while. Treba zachytiť nekorektné výrazy v podmienkach.

Input:

func main() {
    var i;

    while i <= 10 {
        if (i % 2) == 0 {
            print 1000;
        }
        print i;
        i = i+1;
    }
}

Output:

1000
0
1
1000
2
3
1000
4
5
1000
6
7
1000
8
9
1000
10
  1. Funkcie bez return. Zatiaľ volané len z main. Treba kontrolovať počet parametrov a správny názov funkcie pri volaní.

Input:

func add(x, y) {
    print x + y;
}

func main() {
    add(7, 7);
}

Output:

14
  1. Pribúda príkaz return. Treba vedieť vracať hodnotu, pracovať s návratovou hodnotou a tiež korektne ukončiť funkciu pri použití return.

Input:

func add(x, y) {
    return x + y;
}

func main() {
    print add(7, 7) % 47;
}

Output:

14
  1. Teraz sa už funkcie môžu volať navzájom a dokonca aj rekurzívne.

Input:

func fibonacci(a, b, n) {
    if n > 0 {
        print a;
        fibonacci(b, a + b, n - 1);
    }
}

func main() {
    fibonacci(0, 1, 10);
}

Output:

0
1
1
2
3
5
8
13
21
34
  1. Táto sada testuje schopnosti vášho parsera vysporiadať sa s nedostatkom bielych znakov.

  2. Všelijaké syntaktické a iné chyby v rôznych programoch.

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.