5. kodutöö: Grep
Eesmärk on nüüd siis meie suurepärase grep töövahendi 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 week5.Grep "(a|b)*" input2.txt abab aaaa ababab abba baba baab
Kodutöö koosneb kahest osast ja esimest osa oleks hea teha enne proovieksamit, kuigi tähtaeg on alles 27. märts. (Esitada siia!)
- 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. Selle eest saab 7.5 punkti 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.)
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.
week5.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. Erikujuliste tippudega puid tuleb uurida instanceof operaatoriga:
void teeMidagiRegulaaravaldisega(RegexNode node) {
if (node instanceof Alternation) {
// see tipp tähistab valikut
Alternation altNode = (Alternation)node;
teeMidagi(altNode.getLeft());
teeMidagi(altNode.getRight());
} else if (node instanceof Repetition) {
...
}
...
}
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. Sellega saab kirjutada automaadi loomisel 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 pilti. 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.
Tingimused
- Automaatse testimissüsteemi tõttu on oluline, et klassinimi ja implementeeritud meetodite signatuurid oleksid samad, nagu etteantud šabloonis.
- Kui soovid lahenduses kasutada mingeid kolmandate osapoolte teeke, siis anna sellest teada aadressil aivar.annamaa@ut.ee või aine foorumis.
- 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.