Automata, Languages and Compilers 2018/19 spring

Eksami näidisülesanded

Iga osa kohta olid meil ka eraldi harjutused (Alusosa • Põhiosa • Lõviosa), aga siin on mõned ülesanded, millega saab korrata kõik osad korraga. Eksamil tuleb ühe ja sama keele kohta kõik osad teha. See teeb nende elu oluliselt lihtsamaks, kes tahavad rohkem osad järgi teha. Samas peaks olema võimalik iga osa eraldi lahendada, aga see tähendab, et võib kasulik olla teiste osade kirjeldusi ka sirvida!

Choice: mittedeterministlikud avaldised

Lõviosas oli tehniline viga. Siin on uuendatud versioon sellest ülesandest. Selleks, et teil konflikte ei tekiks jätame vana versioon repos. Kui alustad nüüd selle lahendsamist, siis kasuta ChoiceLoviosaV2.java.

Vaatame siin uuesti mitte deterministlike avaldisi. Selle ülesanne grammatika on natuke lihtsam, et jõuaks rokhem aega kulutada lõviosale. Keel on seega väga lihtne meil on ainult liitmisega aritmeetilisi avaldisi, kus on ainult lubatud täisarvud. Lisatud on siis ainult operaator |, mis valib juhuslikult kahe avaldise vahel.

Alusosa. AST klassid on siis ChoiceNode alamklassid ning asuvad paketis choiceAst. Nendeks on ChoiceAdd (liitmine), ChoiceDecision (mittedeterministlik valik) ja ChoiceValue (täisarv). Vaja on lahendada ülesanded klassis ChoiceAlusosa, mis peaksid olema üsna tuttavad meetodid. Kommenteerimist väärib tegelikult ainult viimane ülesanne addConst, kus on vaja tagastada uue puu, mille kõikidele tipudele on lisatud etteantud arv. Näiteks addConst(choice(val(5),val(11)), val(2)) tulemuseks peaks olema choice(val(7),val(13)).

Põhiosa. Selle keele süntaks on äärmiselt lihtne, kuna tegemist on sisuliselt tavaliste aritmeetiliste avaldistega, kus on kaks operaatorit ja sulud lubatud. Tähtis on see, et operaator | on vasakassotsiatiivne ja madalama prioriteediga kui liitmine. Näiteks avaldis (1|2) + 3 | 5 tuleks välja lugeda kui choice(add(choice(val(1),val(2)),val(3)),val(5)).

Lõviosa. Selles osas on vaja lahendada kahte ülesannet. Üks koodigenereerimise näide ja teine on siis koodi optimeerimiseks. Koodi genereerimise meetod codeGen peab tagastama CMa programmi. Mida valikutes tehakse on aga ette antud esialgse magasini seisundina. Seega on esimene valik pesas S[1], teine valik pesas S[2], jne. Neid on seal magasini peal nii palju kui on vaja, et otsust ära teha.

• CMa puhul on meil aga tõeväärtused ühe ja nullina kodeeritud, seega vastab nullile valiku parempoolne argument ja ühele vasakpoolne!
• Avaldist tuleb väärtustada vasakult paremale ning valikute nummerdamine on dünaamiline, näiteks avaldise (1|2) | (3|4) väärtustamiseks tuleb esimene valik valida pesast S[1] ning olenemata valitud harust tuleb lugeda teine valik pesast S[2]. Selles suhtes peaks ta langema kokku alusosa eval meetodi loogikaga.
• See tähendab, et mõnede avaldiste puhul ei ole võimalik staatiliselt kindlaks tegema, kust peab lugema: avaldise (1|(3|4)) + (10|20) korral ei ole kohe selge, mis pesast loetakse valik 10 ja 20 vahel. Kui kõige esimene valik oli lihtsalt 1, siis asub viimane valik pesas S[2], aga kui liitmise vasakpoolse avaldise jaoks oli ka vaja valida 3 ja 4 vahel, siis asub viimane valik pesas S[3]. Seetõttu tuleb pesas S[0] jälgida, kust on vaja valikut lugeda.

Natuke raskem ülesanne on meetod optimize, mis peaks liitmist avaldises täielikult elimineerida niimoodi, et koodi tähendus ei muutuks. Alusosas oleme tegelikult juba lahendanud lihtsama variandi, kus on teine argument lihtsalt arv: (4|1)+6 teisendame avaldiseks 10|7. Kuidas aga teha üldisemalt, et näiteks (1|3)+(10|20) tulemuseks oleks (11|21) | (13|23)? Kui optimize on õigesti lahendatud, siis võib koodi genereerida niimoodi, et valikute lugemised on koodi sisse kirjutatud. (See meetod on testfailis defineeritud.)

Funlist: eksami harjutamiseks lisaülesanne

See on lisaülesanne, mida võib moodle'is esitada, et ühe punkti teenida selle eest, et valmistad eksamiks! Keel on meil siin väga lihtne ja koosneb ainult eraldi ridadel kirjutatud funktsioonide definitsioonidest. Definitsioonid on kõik sellisel kujul:

 sum(x, y) = x + y
 inc(x) = x +1
 f() = 100

Alusosa. AST klassid on kõik FunlistNode alamklassid ning asuvad paketis week11.eksamdemo.funlist.ast. Funktsioonide kehad on liitmisavaldised, mida esitatakse klassidega FunlistLit (täisarvliteraal), FunlistVar (muutuja) ja FunlistAdd (liitmine). Funktsiooni definitsioon esitatakse klassiga FunlistFun ja kogu program on siis FunlistProg. Avaldise AST klassid peaksid olema tuttavad, aga tasub korraks vaadata, nende kahe viimase definitsioonide sisse. Programm on lihtsalt list funktsioonidest ja igal funktsioonil on nimi, parameetrite nimed ja funktsiooni keha.

• Kõigepealt üks triviaalne puu läbimise ülesanne allLiterals. Korjata tuleb kõik programmis esinevad täisarvliteraale. Meie FunlistAstVisitor käitub siin rohkem nagu ANTLR'i BaseVisitor ehk selle ülesanne lahendamiseks piisab tegelikult literaalide külastamisest.
• Nüüd selline päris puu läbimise ülesanne constFuns, mis peab tagastama hulgana programmi kõikide konstantsete funktsioonide nimed. Me peame funktsiooni konstantseks, kui selle tulemus ei sõltu tema parameetritest. Kuna siin ei ole keerulisemad avaldised, siis piisab kontrollida, kas funktsiooni argumendid esinevad tema kehas. (Näiteks f(x) = x - x ei sõltu tegelikult x-ist, aga meil on siin ainult liitmine, mistõttu meil on ikka väga lihtne elu. Ja siis räägitakse veel, et AKT peaks olema raske...) Funktsioonis võib aga esineda vabad (globaalsed) muutujad, seega funktsioon f(x) = y peame ikkagi konstantseks funktsiooniks (aga f(x) = x ei ole).
• Programmide väärtustamiseks vaatame kõigepealt natuke lihtsam variant eval(expr, env). Selle ülesanne jaoks võib eeldada, et AST koosneb ainult ühest funktsoonist ja tema parameetrite väärtused on globaalse keskkonnana ette antud. See tähendab, et kui kasutada FunlistAstVisitor, siis peab ainult liitmist, literaale ja muutujad käsitleda.
• Lõpuks tuleks defineerida päris väärtustaja eval(prog, glob, f, args), mis võtab argumendiks programmi ja keskkonda, aga lisaks ka funktsiooni nimi f ja konkreetsed väärtused, mida tuleks funktsiooni argumendina kasutada. Siin kehtib meie tavapärased skoopimise reeglid: funktsiooni f(x) = x + y korral tuleb x-i väärtus argumendina ja y-i väärtus tuleb globaalsest keskkonnast lugeda.

Põhiosa. Keel on suhteliselt primitiivne ja peaks ülaloleva näidete ja testi põhjal olema üsna selge. Iga rea peal on funktsiooni definitsioon, mis koosneb järgmistest osadest:

• Funktsiooni nimi, mis koosneb ühest või enamast väiketähest. (Me testime siin ainult ladina tähtedega 'a'-'z'.)
• Sulgudes parameetrite nimed, aga need tohivad olla ainult ühetähelised. Parameetrid on komaga eraldatud.
• Võrdusmärk.
• Liitmisavaldis. Avaldises võib siis lihtsalt esineda muutujad (ühetähelised), täisarvud ja kahe avaldise liitmist.

Grammatika aluseks tuleb võtta Funlist.g4, mis asub kataloogis week11.eksamdemo.funlist.

Lõviosa. Siin tuleb kõigepealt genereerid koodi iga funktsiooni jaoks eraldi: codeGen võtab argumendiks programm ja tagastab Map<String, CMaProgram>. Avaldised on väga lihtsad ja raskem moment on siin parameetrite paika saamine. Me eeldame, et globaalseid muutujad ei ole kasutusel, s.t. funktsiooni kehas võib muutujatena ainult esineda funktsiooni parameetrid. Me käivitame CMa sellise magasiniga, kus argumendid on samas järjekorras nagu parameetrite listis. Funktsiooni f(x,a,z) = ... korral tuleks siis koodi genereerida eeldades, et funktsiooni argumendid asuvad järjest pesades {x→0, a→1, z→2}, seega samas järjekorras nagu parameetrid funktsiooni definitsioonis esinevad.

Lõpuks on kõige toredam ülesanne üldse... tõelistele lõvidele. Tuleb defineerida meetod toJavaFun, mis teisendab selle keele funktsioone Java funktsioonideks. Täpsemalt siis järgmise klassi alamklasside isenditeks:

    public interface IntVarargOperator {
        int apply(int... args);
    }

Kui see tundub natuke imelik liides, siis vaata faili lõpus on main meetodis mõned näited. Java võimaldab selliste liideste alamklasse kohe lambda-notatsiooniga kirja panna! IntelliJ oskab minu kirjutatud siseklassi samaväärseks lambda-avaldiseks teisendada. Kui Sinu IDE seda ei tee, siis võid vaadata tulemust siin:

   IntVarargOperator f = a -> a[0] + a[1] + a[2];
   System.out.println(f.apply(1, 2, 3));

Kui mõned testidest lähevad juba läbi, siis võib esitada moodle'is. Selle eest saab kuni üks lisapunkt!