Automaadid, keeled ja translaatorid 2018/19 kevad

Rohkem puu struktuuri harjutusi

Puu läbimine on meie jaoks oluline teema. Kõiksugused struktuursed andmed (näiteks XML) on sisuliselt sellised puud. Siin on mõned puu ülesanded iseseisvaks lahendamiseks. Need on kõik demos paketi all.

Transformer.java

Eksami ülesandes tulevad uued puu klassid, mida peate läbima selliselt, et te neid ise muuta ei saa. Kui kasutad visitor klasse, siis saab IDE kaudu lihtsalt teha override methods. Toome siin näitena mõned ülesanded aritmeetiliste avaldiste peal:

• Defineeri meetod valueList, mis tagastab listi avaldises esinevatest arvudest vasakult paremale.
  Näiteks avaldise 5 + -(3 + -(2 + -6) + 2)) tulemus on [5, 3, 2, -6, 2].
• Defineeri nüüd meetod replaceDiv, mis asendab avaldises kõik jagamised nende väärtustega,
  näiteks 3+24/(4+8)+-(8/2+1) tulemuseks on 3+2+-(4+1).
• Oleme elimineerinud kõik jagamised, seega eeldame järgmise ülesande jaoks, et avaldises on ainult liitmised ja unaarsed miinused. Defineeri meetod signedValueList, mis paneb kõik avaldises esinevad arvud ühte listi, aga valib märgi (positiivne/negatiivne) selliselt, et listi elementide summa ja esialgse avaldise summa oleks sama.
  Näiteks avaldise 5 + -(3 + -(2 + -6) + 2)) tulemus on nüüd [5, -3, 2, -6, -2].

Toome ka näitena ühe natuke raskema ülesande. Eksamil läheb natuke liiga kiireks, et järgnevat ülesannet lisaks kõigele muule jõuaks lahendada, aga kui kodus saad selle lahendatud, siis oled eksamiks valmis! Siin võib vaja minna abifunktsiooni või mõnda lisaparameetrit. Defineeri meetod elimNeg, mis tagastab uue avaldise, mis esialgsest erineb ainult selle poolest, et unaarne miinus on alla lükatud tippudesse. Näiteks 7 + -(3/6 + -(9/3)) tuleks teisendada avaldiseks 7 + -3/6 + 9/3.

Puude teisendamine on peamine asi, mida võiks proovieksamiks iseseisvalt uurida. See võib esialgu müstiline tunduda, sest neid puid ei saa ju muuta, aga siin peab lihtsalt tagastama uue puu! (Mõtle võrdluseks, kuidas Java sõnes tähti muuta: https://stackoverflow.com/questions/6952363/replace-a-character-at-a-specific-index-in-a-string).

FirstLetter.java

Siin peab arvutama regulaaravaldise põhjal kõik tähed, millega regulaaravaldisele vastav keel võib alata. Näiteks "(a|b)*cd" puhul on esimesed tähed 'a', 'b' ja 'c'. Selleks on väga abiks funktsioon matchesEmptyWord(), mida praktikumis lahendasime, sest konkatenatsiooni puhul peab jälgima, kas esimene osa võib olla tühi või mitte. Hea oleks need funktsioonid korraga arvutada, sest selline konstruktsioon, et meil on mitme väärtusega tulemustüüp, võib meil varem või hiljem ikkagi ette tulla...

PrettyPrinter.java

Selle ülesande juures tuleks välja trükkida regulaaravaldised niimoodi, et paneme võimalikult vähe üleliigseid sulge. Seal on kõigepealt väike näide, kuidas seda teha ExprNode klassi puhul. Sa võid otse proovida RegexNode jaoks midagi välja mõelda ja siis uurida, kuidas see on aritmeetiliste avaldiste jaoks tehtud. Regulaaravaldiste puhul tuleks arvestada järgmiste reeglitega:

• Prioriteedid on tärn, konkateneerimine ja valik.
• Meie binaarsed operaatorid on assotsiatiivsed, s.t. a|b|c ei vaja üldse sulge.
• Kordamisoperaatorit ei saa endale rakendada, s.t. a** ei ole lubatud!

Natuke selgitame nüüd aritmeetiliste avaldiste ilutrükki. Kõige olulisem moment on siin see, et kuidas me tuleme selle peale, et meil on sellist abifunktsiooni vaja. See on kriitiline, sest meie peamine eesmärk on muidugi see, et oskaksite lihtsalt asju ise lahendada, aga veel parem oleks, kui te lahendaks asju lihtsalt! See tähendab, et ei hajuta oma ideid igal pool koodis laiali. Inglise keeles öeldakse selle kohta: Don't Repeat Yourself (DRY). Selle kohta võib pikemalt lugeda, aga peamine on siin see, et tahame lahenduse iga mõtte oma koodis ainult ühes kohas selgelt väljendada. Meil on siin hea näidisülesanne: tahame sulud paigutada, aga mõnikord võib neid ära jätta...

Seega, alustame sellega, et mõtleme paljude näidetega läbi: "kuidas peaksin otsustama, kas mul läheb sulge vaja või mitte?" Me tahame näidete põhjal üldistada ja mõelda välja, mis on minimaalne info, millega me saame seda teha. Edasi peab mõtlema, kus/millal seda otsust teha! Vaatame üldisemalt aritmeetilise avaldise puhul:

• 5 - (78)
• 5 - (5 * 5)
• 5 - (5 + 5)

Millise nendest sulgudest võime ära jätta? Ilmselt kaks esimest, sest viimases tähendus muutuks sulgude eemaldamisel. Me võisime seal sulud ära jätta, kus alamavaldise operaatori prioriteet on miinusega võrreldes... milline? Ühesõnaga, kuidas nad omavahel suhestuvad? Kui teed need näited läbi ja küsid, mis infot oli sul vaja selle otsuse tegemiseks, siis midagi võiks nagu selguda...

Ja nüüd peamine otsus on see, et kes ja kus peaks seda otsust koodis tegema. Kas väline avaldis (miinus) võiks otsustada iga alamavaldise kohta? See tundub nagu palju tööd... võib-olla oleks kõige lihtsam, kui avaldis ise otsustab, kas tema ümber on sulge vaja või mitte. See oleks ideaalne, aga selleks, et üleval näites peaks pluss või korrutamine ise otsustama, siis neil on vaja midagi ikkagi teada saada selle välise miinuse kohta! Kuidas saaks seda neile kõrva sosistada? (Meil on vaja abifunktsiooni, mille parameeter sisaldab konteksti prioriteeti! Siis saame otsuse teha!)