4. kodutöö: Grep
Eesmärk on nüüd siis meie suurepärase grep töövahend tööle saada! Selles programmis on main meetod juba defineeritud ja seda me testidega ei kontrolli, aga kindlasti tasub proovida seda 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 meetod
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 juba käsurealt grepi käivitada! - Selline automaat ju tegelikult ei kõlba ja me kõik kibeleme alamhulga konstruktsiooni implementeerima. Seega järgmise sammuna tuleks implementeerida meetod
optimize, 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 ka implementeerida ja praktikumijuhendajale/Vesalile näidata, kui on soov mõni boonuspunkt veel juurde 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. Minu soovitus on siin kasutada õpiku või JFLAPi konstruktsioone, 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õtte! Sellepärast peabki mõtlema, sest esimene mõte ei pruugi olla kõige parem. Mõistlikum on ikka 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 minimaaalne informatsioon, millega saaks automaat 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 Java klasse lihtsate regulaaravaldiste parsimiseks; regulaaravaldiste struktuurseks esitamiseks ja taoliste struktuuride läbimiseks; determineeritud ja mittedetermineeritud automaatide koostamiseks ja käivitamiseks.
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(false);
Edasi saab siis sellele uuele seisundile newstate servasid lisada nagu tavaliselt.
Automaatide joonistamisest
Praktikumis vaatasime automaatide joonistamist. Kui createDotFile anda ette fail, mille laiend on png, siis genereerib ta sellest ise pildi. Kui see ei tööta, siis kasuta laiendiks dot ja teisenda ta ise pildiks veebilehel http://www.webgraphviz.com/. Alternatiivina võib kasutada süsteemi Graphviz ka enda arvutisse paigaldatuna. Ubuntu jaoks soovitame sudo apt-get install xdot.
NB! Tuletame meelde, et peab kasutama epsiloni jaoks servadeks "null". Kui kasutad epsilon, siis joonistatakse õige välimusega automaat, aga ta ei käitu ikkagi õigesti.
Tingimused
- Automaatse testimissüsteemi tõttu on oluline, et klassinimi ja implementeeritud meetodite signatuurid oleksid samad, nagu etteantud šabloonis.
- Kui esitatavad java failid sisaldavad täpitähti (või muid ASCII'sse mittekuuluvaid sümboleid), siis peavad need olema UTF-8 kodeeringus.
- Kui sa kasutad etteantud projektikausta, siis ei ole vaja kodeeringu pärast muretseda.
- Eclipse'is on soovitatav määrata failide kodeering korraga tervele projektile (paremklõps projektil -> Properties -> Resource : Text file encoding) või lausa tervele workspace-ile (Window -> Preferences -> General -> Workspace : Text file encoding).
- Oma koodi testides ei ole Eclipse'is vaja kodeeringu pärast muretseda. Käsureal kompileerides võib olla vajalik kodeering ette anda, nt:
javac -encoding UTF-8 MinuKlass.java. Juba kompileeritud *.class failide käivitamisel võib jälle kodeeringu teema unustada, sest *.class failid ei ole tekstifailid.