Automaadid, keeled ja translaatorid

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. Puude teisendamine 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: stackoverflow). Uue puu tagastamine tähendab, et iga vahetipu juures peab seda uuesti looma.

ExprMaster

Vaatame nüüd meie esimesest visitori näitest kasutatud expr keele.

• 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 replaceDivs, 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].
• Defineeri meetod elimNeg, mis tagastab uue avaldise, mis esialgsest erineb ainult selle poolest, et unaarne miinus on alla lükatud puu tippudesse (jagamise korral lugejasse). Näiteks 7 + -(3/6 + -(9/3)) tuleks teisendada avaldiseks 7 + -3/6 + 9/3.
• Meetod pretty on näide allpool RegexPrettyPrinter ülesande jaoks.

Kui oled seda lahendanud, siis proovi ka tõestada Isabelle abiga, et see on kõik õige!

BoolMaster

Siin on mõned harjutused bool abstraktse süntaksi peal.

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 transform teisendab puu loogiliselt samaväärseks avaldiseks, mis ei sisalda implikatsiooni.
3. Meetod createDecisionTree tekitab avaldisest otsustuspuu. 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 DecisionTree klassi staatilist meetodit decision ja lehtede jaoks konstante TRUE ning FALSE, näiteks on decision('x', decision('y', TRUE, FALSE), FALSE) samaväärne valemiga "x ja y". Diagrammide ühendamiseks on defineeritud meetod compose, millest tuleb aru saada, sest selle abil on kõige lihtsam ülesannet lahendada.

RegexPrettyPrinter

Selle ülesande juures tuleks välja trükkida regulaaravaldised niimoodi, et paneme võimalikult vähe üleliigseid sulge. Klassis ExprMaster 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 kahanevas järjekorras: 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!)