Arvutiteaduse instituut
  1. Esileht
  2. Automaadid, keeled ja translaatorid
EN
Logi sisse

Automaadid, keeled ja translaatorid

  • Üldinfo
  • Ajakava
  • Eksami näidised
  • Teemad
    • 1. Soojendus
    • 2. Regulaaravaldised
    • 3. Automaadid
    • 4. Avaldise struktuur
      • Avaldispuu läbimine
      • Eksami alusosa!
      • Regulaaravaldiste analüüs
      • Kodutöö
        • Minimeerimine*
    • 5. Grammatikad ja lekser
    • 6. Käsitsi parsimine
    • 7. ANTLRiga töötamine
    • 8. Interpretaator
    • 9. Kompilaator
    • 10. Edasi!
  • Süvendus
  • Bitbucket
  • Moodle
  • Zulip
  • Zoom

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:

  1. 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!
  2. 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!

  1. Proovi paberi peal konstruktsioon läbi teha.
  2. Küsi enda käest "Mis on minimaalne informatsioon, millega saaks automaadi kokku panna?"
  3. 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 determinize meetodiga 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!).

  • Arvutiteaduse instituut
  • Loodus- ja täppisteaduste valdkond
  • Tartu Ülikool
Tehniliste probleemide või küsimuste korral kirjuta:

Kursuse sisu ja korralduslike küsimustega pöörduge kursuse korraldajate poole.
Õppematerjalide varalised autoriõigused kuuluvad Tartu Ülikoolile. Õppematerjalide kasutamine on lubatud autoriõiguse seaduses ettenähtud teose vaba kasutamise eesmärkidel ja tingimustel. Õppematerjalide kasutamisel on kasutaja kohustatud viitama õppematerjalide autorile.
Õppematerjalide kasutamine muudel eesmärkidel on lubatud ainult Tartu Ülikooli eelneval kirjalikul nõusolekul.
Tartu Ülikooli arvutiteaduse instituudi kursuste läbiviimist toetavad järgmised programmid:
euroopa sotsiaalfondi logo