4. kodutöö: Grep
Eesmärk on nüüd meie suurepärane grep töövahend tööle saada! Selles programmis on main meetod juba defineeritud ja seda me testidega ei kontrolli, aga kui huvitab, siis tasub proovida seda ka käivitada. Tulemus võiks olla järgmine, kui käsureal gradle'i abil ehitada ja käivitada:
gradlew assemble java -cp build/classes/java/main week4.Grep "(a|b)*" inputs/regex.txt abab aaaa ababab abba baba baab
Kodutöö koosneb kahest osast:
- Kõigepealt peab implementeerima etteantud Java klassi Grep meetodi
regexToFiniteAutomaton, mis peab koostama etteantud regulaaravaldisele vastava lõpliku automaadi. Teie elu lihtsamaks tegemiseks on lisatud abiklassid ning meetodid regulaaravaldise parsimiseks regulaaravaldise puuks. Selline automaat peaks juba töötama ja võib käsurealt grepi käivitada! - Aga selline automaat ju tegelikult ei kõlba kuhugi ja me kõik kibeleme alamhulga konstruktsiooni implementeerima. Seega järgmise sammuna tuleks implementeerida meetod
determinize, mis peaks teisendama etteantud NFA vastavaks DFA-ks. (Päris grep'i moodi töövahendid, millele antakse regulaaravaldis ja sisend korraga ette, teostavad alamhulga konstruktsiooni jooksvalt. Luuakse ainult see osa DFA-st, mis on sisendi jaoks vajalik. Sellist lähenemist võib proovida ka implementeerida ja Vesalile näidata, kui on soov mõni boonuspunkt veel teenida.)
Selle kodutöö juures tuleb läbida regulaaravaldise puu visitoriga, mis on hea harjutus eksamiks. Antud kodutöö on aga raskem, sest pead ise välja mõtlema, kuidas käib andmete edastamine erinevate arvutuste vahel. Soovitus on siin kasutada õpiku või JFLAPi konstruktsiooni, kus andmed liiguvad puu tipudest alt üles. See on rohkem nagu meie väärtustamise meetodid, aga mis on tulemustüüp?
Esimene mõtte võib olla see, et tagastame lihtsalt automaate. See ei ole hea mõte! Sellepärast peabki mõtlema, sest esimene mõte ei pruugi olla kõige parem. Mõistlikum on automaat isendiväljana hoida ja seda täiendada puud läbides. Tagastada tuleks selle asemel ainult vajalik informatsioon, et saaks automaadi erinevad osad ühendada!
- Proovi paberi peal konstruktsioon läbi teha.
- Küsi enda käest "Mis on minimaalne informatsioon, millega saaks automaadi kokku panna?"
- Loo sellele tulemustüübile vastav klass!
Igal juhul peaksid kulutama 90% oma ajast oma lahenduse disainile. Kui on selge, mis informatsioon on vaja tagastada, siis lahenduse implementeerimine (Visitori lünkade täitmine) on väga väike töö. Kui hakkad kohe koodi kirjutama, võib asi palju hullem olla!
Abiklasside kirjeldus
Lisasime projektile ka klassid lihtsate regulaaravaldiste parsimiseks; regulaaravaldiste struktuurseks esitamiseks ja taoliste struktuuride läbimiseks.
week4.regex
RegexParser'i kasutamise kohta on näide klassi Grep main-meetodis ja tegelikult seda sul mujal vaja ei lähegi. Vaja on teada, kuidas käia läbi puuna esitatud parsitud regulaaravaldist, st. käsitseda klassi RegexNode ja selle alamklasse. Seda saab teha sobiva RegexVisitor-i implementatsiooni abil.
Seisundite lisamine
FiniteAutomaton ülemklassis on defineeritud seisundi lisamise meetod, kus arvutame ise välja järgmise seisundi indeksi. Selline meetod võib väga kasulik olla, kui tahad genereerida regulaaravaldisest NFA. Seda saab kasutada järgnevalt:
int newstate = automaton.addState();
Edasi saab siis sellele uuele seisundile newstate servasid lisada nagu tavaliselt.
Automaatide joonistamine
FiniteAutomaton ülemklassis on defineeritud renderPngFile meetod, millega saab automaadist pildifaili genereerida, et visuaalselt selle sisu näha. Selleks peavad aga kõik getter meetodid õigesti töötama, sest nende kaudu käib automaadi joonistamine.
NB! Tuletame meelde, et epsiloni jaoks peab kasutama automaadi servadel sümbolit null. Kui kasutad epsilon sümbolit ennast, siis joonistatakse õige välimusega automaat, aga ta ei käitu ikkagi õigesti.
Tingimused
- Moodle'isse tuleb esitada ka oma eelmise kodutöö NFA-võimekusega FiniteAutomaton lahendus.
- Kui sellega oli probleeme, siis võid kasutada ja esitada meie näidislahenduse
sols/kaustast. - Me võimaldame siin oma FiniteAutomaton-i esitada, sest sinna võib nüüd lisada veel mingeid abimeetodeid, millega selle kodutöö lahendamist enda jaoks lihtsustada. Aga see pole vajalik ja saab hakkama ka olemasolevatega.
- Kui sellega oli probleeme, siis võid kasutada ja esitada meie näidislahenduse
- Kui
determinizemeetodiga ei saa hakkama või see ei tööta, siis esita vaikimisi implementatsioon, mis tagastab optimeerimata automaadi. Ära kustuta seda meetodit, sest muidu ei saa ka esimest osa testida.
Video juhuks, kui jääd alustamisega hätta: RegexAnalyzer ja Grep-i algus (spoiler!).