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
      • JFLAP
      • Programmeerimine*
      • NFA ehitusklotsid
      • Püsipunktid*
      • Kodutöö
    • 4. Avaldise struktuur
    • 5. Grammatikad ja lekser
    • 6. Käsitsi parsimine
    • 7. ANTLRiga töötamine
    • 8. Interpretaator
    • 9. Kompilaator
    • 10. Edasi!
  • Süvendus
  • Bitbucket
  • Moodle
  • Zulip
  • Zoom

3. Automaadid

Nüüd on saabunud kõige olulisem hetk Wettlaufweltmeisteri seiklustel. Leksilise ja süntaktilise analüüsi jaoks on olemas suurepärane tööriist nimega ANTLR. Kas peaks otse liikuma ANTLRi kasutamise juurde või kõigepealt uurida, kuidas ise leksilist analüüsi realiseerida? Wettlaufweltmeister mõtleb pikalt järele, mis tegelane ta olla tahab: pealiskaudne tarbija või sügav asjatundja. Tema on oma otsuse teinud, aga kas Sina tahad kaasa tulla selles kõrvalpõiges või liiguksid pigem otse kasutamise juurde?

  • Kui soovid Wettlaufweltmeisteriga koos uurida leksilist analüüsi, siis loe siin lehel edasi.
  • Kui soovid otse minna ANTLRi kasutamise juurde, siis vajuta siia: otsetee ANTLRini.

Wettlaufweltmeister on väga õnnelik, et otsustasid temaga kaasa tulla! Selle kahenädalase "nädala" lõpuks peaks ta juba oskama

  • automaate kirjelduse põhjal joonistada ja neid simuleerida töövahendiga JFLAP;
  • lihtsama automaadi olekute tähendust kirjeldada;
  • koostada automaadi täiendit, võtta automaatide ühendit ja ühisosa;
  • nimetada kolm põhilist andmestruktuuri Java standardteegis (Map, List ja Set);
  • alustada probleemide lahendmist küsimusega "mis on tähtsamad andmed selles probleemis ja kuidas peaksin ma neid Java andmestruktuuridega esitama?"

Esimene nädal: olekupõhine mõtlemine

Kõigepealt harjutame automaatide joonistamist JFLAP abil. Neid automaate kasutame eelkõige regulaarsete keelte äratundmiseks, aga lisateemana saad uurida, kuidas olekumasina vaade võimaldab programme paremini üles ehitada.

Meie JFLAP harjutused arendavad Sinu võimet paremini ja selgemini programmi olekut väljendada! See eeldab muidugi, et teed need harjutused mõttega ja mitte liiga testipõhiselt. Küsi: mille eest vastutab iga olek ehk mis see tähendab, kui automaat on selles seisundis? (Näiteks: see seisund tähendab seda, et automaat on siiamaani näinud paaritu arv a-sid.) Samamoodi peaksid üritama ka päris programmides süsteemi olekut selgelt väljendama, mitte hajutada erinevate muutujate vahel.

Teine nädal: programmidisaini esimene samm

Keskendume kodutööle, kus implementeerime automaatide käivitajat. Järgmise kodutööga teisendame regulaaravaldisi automaatideks ja siis saame tekstis regulaaravaldiste abil otsida. Meie põhieesmärk nende kodutöödega on aru saada, kuidas lekser töötab. See ülesanne on aga lisaks suurepärane võimalus harjutada andmestruktuuride kasutamist! Sul on Map ja Set tuttavad andmestruktuurid ja nende abil võiks proovida ise järgmist kodutööd lahendada! Kui Sul kipub aga väga keeruliseks minema (lahendus on üle 100 rida), siis vaata ikka natuke abimaterjale.

  1. NFA esitamise ehitusklotsid. See on nüüd selleks, et natuke harjutada neid andmestruktuure, mida võiks NFA esitamiseks vaja minna. Praktikumis lahendame neid ja selle käigus valmib deterministlik automaat, mille eest saab kodutöös vähemalt ühe punkti.
  2. Püsipunkt ja sulund. See on ainult vajalik, kui tahta seda väga ilusasti lahendada. Vesal ilmselt räägib sellest ka loengus, sest talle need püsipunktid nii õudsalt meeldivad.

Selle kodutööga peatume programmidisaini esimesel ja kõige olulisemal sammul: andmete esitamamine arvutiprogrammis! Programmeerides peab päris maailma probleemi formaalselt kirjeldama ja see algab andmestruktuuride valimisest. Kodutöö jaoks on kaks nädalat aega! Esimene nädal on praktikumis JFLAP harjutused, aga järgmises praktikumis näitame juba lahenduse algust ja seega suunatakse teid mingisuguse konkreetse andmeesituseni. See on aga siin kõige olulisem ja loomingulisem samm selles kodutöös!

Seega on äärmiselt oluline, et oled ise enne üritanud midagi iseseisvalt lahendada. Kui ainsad loomingulised asjad lased enda eest ära teha, siis võib ju Sind samahästi robotiga asendada...

Süstemaatilise programmidisaini sammud raamatust How to Design Programs:

  • 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