Eksami lõviosa
Eksami lõviosa ei ole enam lastemäng. Kui me ikkagi sooviks, et kõik AKT lõpetajad oskaksid alusosa eest saada vähemalt 10 punkti, siis lõviosa on ikkagi ainult tõelistele lõvidele. Need on need viimased 10 punkti, mida me niisama kandiku peal välja ei jaga, vaid peab higi ja vaevaga ära teenima. Põhiteemaks on analüüs ja/või koodigenereeri, mis on üsna lai teema ning järgmised ülesanded on head harjutused selleks, aga ei saa eeldada, et eksamil tuleb ainult nende moodi asju. Kõik on võimalik...
Järgmised ülesanded jätkavad meie põhiosa grammatikatega. Siin kordame ainult nende ASTide kirjelduse. Kui on vaja meelde tuletada, milline keel välja nägi, siis võid vaadata, aga nende lahendamiseks on ainult vaja ASTiga töötada.
Loogika (eesti keeles)
AST moodustatakse LoogikaNode alamklassidest. Iga grammatikas kirjeldatud avaldise tüübi jaoks on oma AST klass. Loogilise tehte jaoks on kolm eraldi klassi: JaNode, VoiNode, VordusNode. Meil on siin vaja siin lahendada kahte ülesannet.
1. Interpretaator
Soojenduseks tuleks lahendada vana hea eval meetod. See peab peab väärtustama (tulemuseks true/false) etteantud ASTi, kasutades etteantud tõeväärtusmuutujate map. Tingimusavaldise korral, kui avaldises ei esine MUIDU osa ning KUI avaldis on väär, tuleks tagastada true.
2. Kompilaator
Järgmisena tuleks implementeerida meetod compile. See peab aga tagastama CMa programmi esindava isendi. Selleks saab kasutada CMaProgramWriter klassi. Selle kohta on näide Vam lehel. CMa jaoks tuleb siis tähistada tõeväärtustüüpe täisarvudega 1 (true) ja 0 (false). Klassis CMaUtils on lihtsad abimeetodid nende teisendamiseks. Meil on muutujate jaoks fikseeritud aadresskeskkond ρ = {x→0, y→1, z→2, a→3, b→4, c→5}. Selle saab kätte MUUTUJAD.indexOf(x) kaudu.
Hulk programmid
AST moodustatakse HulkNode alamklassidest. Iga AST algab HulkProgramm tipuga, mis sisaldab listi HulkLause tippudega. HulkLause esindab omistamist, koosneb hulgamuutuja nimest (millele omistatakse), avaldisest (mida omistatakse) ning tingimusest (kas omistatakse). HulkAvaldiseks võivad olla HulkMuutuja, HulkLiteraal (elementide list) ja HulkTehe (ühend, ühisosa, vahe). HulkTingimus koosneb alamavaldisest ja ülemavaldisest.
Siin on kokku neli ülesannet, mis kõik töötlevad ASTi, et saaks eksamiks rohkem harjutada. Tegelikult on eksami lõviosas siiski ainult kahest ülesandest, aga kõik järgmised on võimalikud variatsioonid ASTi analüüsi ja teisendamise kohta.
1. Semantiline analüüs
Meetod isValidHulkNode peab kontrollima, kas kõik muutujad, mida avaldistes ning tingimustes kasutatakse, on eelnevalt defineeritud. Kui leidub mõni mitte-defineeritud muutuja kasutus, tuleb tagastada false, vastasel juhul tagastada true. Kui muutuja on omistatud avaldisega, mis sisaldab tingimust, ei loe me muutujat defineerituks (olenemata tingimuse tõeväärtusest – siin me nende väärtusi ei arvesta). Ükski muutuja pole enne programmi analüüsi defineeritud.
- Järgneva näite korral peab meetod tagastama false, sest muutuja A pole enne selle kasutamist defineeritud:
A := A | {a} subset {b, c} - Järgneva näite korral peab meetod tagastama false, sest muutuja B omistamisel kasutatakse muutujat A, mida loeme mitte-defineerituks tingimusega omistamise tõttu:
A := {b} | {a} subset {a, b, c} B := (A-{a}) - Järgneva näite korral peab meetod tagastama true, sest muutuja A on enne selle kasutamist eelnevalt defineeritud:
A := {a, b, c} B := (A+{a})
2. Optimeerimine
Meetod processEmptyLiterals tagastab uue puu, kus on eemaldatud kõik tühjad literaalid, mis esinevad tehetes. Lisaks on vaja omistuslausest eemaldada ka tingimus, kui tingimuses kasutatav alamhulk on tühi literaal. Uus puu peab olema esialgsega samaväärne ning tehetest tühjade literaalide eemaldamisel kasutatakse järgmisi reegleid:
- Kui ühisosa (
&) vasak või parem pool on tühi literaal, tuleb tehe asendada tühja literaaliga.A := {} & B => A := {} - Kui ühendi (
+) vasak või parem pool on tühi literaal, tuleb tehe asendada poolega, mis polnud tühi literaal.A := {a, b, c} + {} => A := {a, b, c} - Kui vahe (
-) vasak pool on tühi literaal, tuleb tehe asendada tühja literaaliga.A := {} - B => A := {} - Kui vahe (
-) parem pool on tühi literaal, tuleb tehe asendada vasaku poolega.A := {a, b} - {} => A := {a, b}
3. Interpretaator
Edasi on vaja teha meetod run, mis on natuke keerulisem kui meie tavalised eval meetodid: see võtab lisaks ASTi argumendiks keskkonna (Map<Character, Set<Character>>, mis näitab missugused elemendid kuuluvad hulkadesse) ning peab muutma etteantud keskkonna sisu nii, et see vastaks ASTile vastava programmi jooksutamisele.
- Iga lause täidetakse ainult siis, kui vastav tingimus on tõene või tingimus puudub üldse.
- Tingimus on tõene siis, kui iga alamavaldise element on ka ülemavaldise element.
- Hulgamuutujaid saab avaldises kasutada ainult siis, kui neile on eelnevalt omistatud midagi või nad on etteantud keskkonnas juba defineeritud. Muidu tuleks visata erind.
Vihje: pead tegema, kas erinevate visitoritega või kusutad Set<Character>, mis on avaldiste tulemus, ja lausete puhul tagastad "null". Tingimuste tulemus saab ka hulgana kodeerida. Muidu saab alati tagastada Object ja igal pool tüüpe teisendada.
4. Kompilaator
Lõpuks on jäänud meetod compile, kus tuleb hulkprogramme CMa peal käivitada. Hulkmuutujate keskkond on fikseeritud ja nende mälupesad saab kätte SET_VARIABLES.indexOf kaudu. Kuna CMa arvutab ainult täisarvudega, siis on hulga sisu ka fikseeritud ja meetod set2int, teisendab hulka bitvektoriks. See muidugi tähendab, et pead ise nuputama, kuidas hulga operatsioone bitoperatsioonidena teostada. Ühe vihje anname siiski, sest NOT ei tööta CMa-s bithaaval: selle asemel võib teha miinus ühega XOR.
Let-avaldised
AST moodustatakse LetAvaldis alamklassidest. Avaldiseks võib olla: täisarv (LetArv); muutuja (LetMuutuja); kahe avaldise vahe (LetVahe); muutuja sidumisega avaldis (LetSidumine, koosneb seotava muutuja nimest, muutujale omistatavast avaldisest ning avaldise kehast); summeeriv avaldis (LetSumma, koosneb muutuja nimest, muutuja algväärtusavaldisest, muutuja lõppvääärtusavaldisest ning avaldise kehast).
1. Semantiline analüüs
Let-avaldise puu võib sisaldada erinevaid muutujad. Defineeri meetod onVaja, mis etteantud muutuja ja puu kohta kontrollib, kas selle muutuja väärtust on avaldise väärtustamisel vaja eelnevalt teada või mitte. Kõigepealt tasub vaadata meie teste ning nende põhjal järjest implementeerida. Literaalide puhul peaks olema selge, näiteks avaldise x-kala väärtustamisel on muutuja kala kasutusel, aga avaldise x-y puhul mitte.
Oluline on aga see, et tuleb eristada lokaalselt defineeritud muutujad nendest muutujatest, mis peavad olema väärtustamise keskkonnas defineeritud. Kui mõni muutuja on kohalikult defineeritud (let x=5 in x), siis ei sõltu selle väärtus keskkonnast ja tuleb tagastada, et muutujat x ei ole vaja. Järgneva kahe avaldise väärtustamiseks aga on vaja, et keskkonnas oleks muutuja x defineeritud:
let y = x-1 in y (let x=5 in x) – x
Siin võib tekkida küsimus, kas avaldises let y=x in 5 on muutuja x väärtus vaja või mitte. Avaldise tavapärasel väärtustamisel tekiks viga, kui muutuja on defineerimata, aga tulemus samas ei sõltu muutuja väärtusest. Sellistel avaldistel on meil käitumine spetsifitseerimata ehk me otseselt ei testi seda ja võid tagastada misiganes aitab Sul järgmist optimeerijat mugavamalt implementeerida.
2. Optimeerimine
Eesmärk on nüüd eemaldada sellised let-sidumised, mida väärtustamisel vaja ei lähe. Jällegi tasub vaadata testis olevaid näited ning nende põhjal üldistada. Siin on mõned neist välja kirjutatud:
| Esialgne avaldis | Ebavajalike let-sidumisteta |
|---|---|
let x=5 in y let x=5 in x let x=5 in let y=10 in let z=x in z let x=10 in let y=x in z |
y let x=5 in x let x=5 in let z=x in z z |
NB! Me ei soovi siin saada avaldise lihtsutajat, vaid ainult üleliigsete let-sidumiste eemaldajat. Seega, teise näide korral ei ole tulemuseks lihtsalt 5, vaid terve esialgne let-avaldis. Tuleb aga nii palju let-avaldisi eemaldada kui võimalik. Näiteks ei ole viimases näites muutuja x väärtus vaja, sest selle põhjal arvutatakse muutuja y väärtus, mida lõpuks ei kasutata. Me jätsime üleval onVaja käitumist sellistel juhtudel lõpuni spetsifitseerimata, sest tema vajalik käitumine sõltub sellest, kuidas seda meetodit siin rakendada.
3. Interpretaator
Lahenda soojenduseks eval meetod, mis tagastab etteantud ASTi täisarvulise väärtuse. Sidumisega avaldises esmalt arvutatakse välja muutuja väärtus ning seejärel kasutatakse saadud tulemust avaldise kehas. Summeerimises leitakse muutuja väärtuse vahemik (kõik täisarvud, mis on vähemalt lo ning mitte rohkem kui hi), leitakse avaldise keha väärtus iga muutuja väärtuse jaoks ning summeeritakse need. Kui kasutatakse muutujat, mis pole eelnevalt sidumise või summeerimise poolt defineeritud, tuleks visata erind.
4. Kompilaator
Nüüd võib implementeerida compile meetod, et transleerida let-avaldisi CMa programmideks. Meil on defineeritud vabad muutujad (x, y, z), mis asuvad kohe magasini põhjas (pesades 0, 1, 2 vastavalt). Õige indeksi saab kätte VARS.indexof abil. Teeme siin aga olulise lihtsustuse, et let ja sum ei esine teiste avaldiste alamavaldistena, vaid meil on ainult järjest let-sidumiste jada, nagu näiteks:
let a = 5 in let b = x - a in let c = sum 3 to y in 10 - b in let d = a - c in d - (z - 1)
See garanteerib, et magasini tegelikult ainult kasvab ja iga let-seotud muutuja asukoht on kompileerimise ajal lihtne paika panna. Testides on näha, mis avaldistega peab hakkama saama.