Automaadid, keeled ja translaatorid 2018/19 kevad

Alusosa näited

Mõned näited alusosa ülesannetest asuvad paketis week5.alusosa. Need on võetud eelmistest aastatest, aga pisut mugandatud, et oleks kooskõlas sellega, mis me nüüd tahame teilt näha. Seega, nende harjutamine on parim viis ette valmistada eksami alusosaks. Seal on järgmised paketid, kus igaühes on üks Analyzer.java klass, mille puuduolevaid meetodeid tuleb implementeerida:

1. randex: mündi viskamisega avaldised.
2. bexp: tõeväärtusavaldied.

RndAnalyzer.java

Selles ülesandes tuleb töödelda etteantud RndExp tüüpi avaldise puu. Puu on moodustatud tema alamklasside isenditest, mille definitsioonid on paketis randAst. Selles on meile tuttavatale aritmeetilistele operatsioonidele (RndAdd, RndNeg ja RndNum) veel lisaks ka RndFlip tüüpi vahetipp. Selle tipu juures tuleb juhuslikult valida (õiglase mündiviske põhjal) vasakpoolset või parempoolset alampuud.

1. Meetod findRandomLeafs peab tagastama kõikide lehtede väärtusi, mis jäävad mõne juhusliku valiku alampuude sisse.
2. Meetod eval peab väärtustama avaldist etteantud mündi coin abil. See peab toimuma nii, et kui coin.getAsBoolean() tagastab true, siis valitakse vasakpoolset alampuud, vastasel korral valitakse parempoolset alampuud. Oluline on puu läbida ülalt-alla ja vasakult paremale, et mündi visked toimuks õigel ajal. (See on see loomulik viis, kuidas meie eval meetodid on siiamaani ka toiminud.
3. Meetod prop peab tagastama tõenäosuse, et avaldise tulemus on võrdne etteantud väärtusega. Siin eeldame, et valikud on kõik võrdse tõenäosusega (0.5 vasakule ja 0.5 paremale) ning kõik mündivisked on teineteisest sõltumatud.

Viimane alamülesanne on tehniliselt natuke keerulisem kui see, mida alusosa eksamil tahaks viimase alamülesandena panna, aga oluline on siin see, et meil (vähemalt minul) oli vaja teise tagastustüübiga visitori kui lihtsalt Visitor<Double>.

BExpAnalyzer.java

Siin tuleb töödelda etteantud BExp tüüpi avaldise puu. Puu on moodustatud paketis bexpAst oleva BExp klassi alamklasside isenditest. Puuga saab esitada loogilisi avaldisi, kus on muutujad (Var), disjunktsioon (Or), implikatsioon (Imp) ja eitus (Not).

1. Meetod analyze uurib etteantud süntaksipuud ja tagastab Stats klassi isendi, mis vastab küsimustele containsImp (tõene, kui avaldises sisaldus Imp tüüpi tipp) ja getVariables (kõik avaldises esinenud muutujate nimed). Ise ei saa Stats klassi muuta, vaid analyze meetodis tuleb selle sisu luua ja puud läbides kutsuda addVar ning foundImp meetodid, et õigete väärtustega Stats isend saaks tagastatud.
2. Meetod eval on klassikaline väärtustamise meetod. Loogikatehete tähendus peaks olema teada (vähemasti koos Internetiga), aga muutujate kohta saab eval meetod parameetrina ette tõeste muutujate hulga. Seega on muutuja väärtus tõene siis ja ainult siis, kui ta kuulub sinna hulka.
3. Meetod transform teisendab puu loogiliselt samaväärseks avaldiseks, mis ei sisalda implikatsiooni.
4. Meetod createDiagram tekitab avaldisest otsustusdiagrammi. See on selline puu, kus vahetippudeks on ainult muutujad ning vastavalt nende tõeväärtusele valitakse vastav alampuu. Tasub vaadata selle klassi eval meetodit. Selle loomiseks tuleb kasutada DecisionDiagram klassi staatilist meetodit choice ja lehtede jaoks konstante TRUE ning FALSE, näiteks on choice('x', choice('y', TRUE, FALSE), FALSE) samaväärne valemiga "x või y". Diagrammide ühendamiseks on defineeritud meetod compose, millest tuleb aru saada, sest selle abil on kõige lihtsam ülesannet lahendada.