Automaadid, keeled ja translaatorid 2017/18 kevad

Rohkem puu struktuuri harjutused

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 paketti all.

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 tuleb väga abiks funktsioon isEmpty(), 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...

ExpressionEksam.java

Eksami ülesandes tulevad uued puu klassid, mida peate läbima selliselt, et te neid ise muuta ei saa. Me anname ette nende klasside jaoks instanceof malli, et saaksite rohkem keskenduda sisule. Kui kasutad visitor klassid, siis saab IDE kaudu lihtsalt teha override methods. Toome siin näitena mõned ülesanded aritmeetiliste avaldiste peal:

• Defineeri meetod valueList, mis tagastab list 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 ülesanne jaoks, et avaldises on ainult liitmised ja unaarset miinust. 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äidena üks natuke raskem ülesanne. Eksamil läheb natuke liiga kiireks, et järgnev ülesanne lisaks kõigele muule jõuaks lahendada, aga kui kodus saad seda lahendatud, siis oled eksamiks valmis! Siin võib vaja minna abifunktsioon või mõni lisaparameeter. Defineeri meetod elimNeg, mis tagastab uue avaldise, mis esialgsest erineb ainult selle poolest, et unaarset miinust on alla lükatud tipudesse. 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).

PrettyPrinter.java

Selle ülesanne juures tuleks välja trükkida regulaaravaldised niimoodi, et paneme võimalikult vähe üleliigsed sulud. 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 on aritmeetiliste avaldiste jaoks seda 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 selline abifunktsioon 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 sulud vaja või mitte?" Me tahame näidete põhjal üldistada ja mõelda välja, mis on minimaalne info, millega me saime seda teha. Edasi peab mõtlema, kus/millal seda otsust teha! Vaatame üldisemalt aritmeetilise avaldise puhul:

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

Milline 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... kuidas? Ühesõnaga, kuidas nad omavahel suhestuvad? Kui natuke teed need näited läbi ja küsid, mis info 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 sulud 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 abifunktsioon, mille parameeter sisaldab konteksti prioriteet! Siis saame otsust teha!)