Arvutiteaduse instituut
  1. Kursused
  2. 2019/20 kevad
  3. Automaadid, keeled ja translaatorid (LTAT.03.006)
EN
Logi sisse

Automaadid, keeled ja translaatorid 2019/20 kevad

  • Üldinfo
  • Eksami näidised
  • Kava
    • 1. Soojendus
    • 2. Regulaaravaldised
    • 3. Olekumasinad
      • 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
  • Bitbucket
  • Moodle
  • Fleep!

3. Olekumasinad

Me tahame siin lõplikest automaatidest aru saada. 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.

Selle ja järgneva kodutöö raames implementeerime oma päris grep töövahendi. See on eelkõige selleks, et aru saada, kuidas lekser töötab. See ülesanne on aga 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 mudeldama 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 robtiga 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.
Courses’i keskkonna kasutustingimused