Tere tulemast AKT kursusele!
—Hal Abelson, raamatu EOP eessõnast.
Meie soov on see, et peale kursuse läbimist oleks Sul sügavam arusaamine arvutiprogrammide tähendusest ja seetõttu oskad paremini programmeerida. Me üritame seda saavutada ühelt poolt programmeerimise harjutustega ja teiselt poolt interpretaatori ja kompilaatori ehitamisega. Kui oleme aru saanud, kuidas programmeerimiskeele käsud täidetakse ja transleeritakse, siis oleme sunnitud sellest keelest päriselt aru saama ja oskame paremini ka oma lauseid moodustada.
Selles dokumendis kirjeldame õppekorraldust ja üritame anda suurema pildi, kuidas kursuse kodutööd on omavahel seotud.
Tegevused ja hindamine
Sellel kursusel on üsna mahukad kodutööd, aga kontrolltööd ja eksam sisuliselt samade ülesannete peal, mida olete juba kodus lahendanud!
- Kodutööd (30 punkti)
- Kordamistestid (10 punkti)
- Eksam (60 punkti)
- Loengu ActiveQuiz (10 lisapunkti)
Hindamisskaala on lõpuks selline, et >50 on E, >60 on D, ..., >90 on A. Eksami eest peab koguma vähemalt 30 punkti! Aines on kokku 12 põhilist kodutööd, mille lahendamiseks on nädal aega. Nendele lisaks on ka paljude teemade juures semestri lõpu tähtajaga kodutööd.
Hindamine käib eelkõige automaattestide alusel ehk korrektsus on peamine kriteerium. Juhendajad panevad siiski kodutööle lõpliku hinde ja sealjuures võib ta küsida selgitusi sinu töö kohta meie kursuse Fleepis. Teil on ka võimalus Fleepis küsida tagasisidet ja oma tulemusi parandada, kui automaatkontroll oli sinu vastu liiga kuri. Me avalikustame selleks ajaks kodutöö lahenduse, mistõttu pead eelkõige näitama, kuidas oma enda lahenduse pealt saaks edasi minna õige lahenduseni.
Praktikumijuhendajatel on suur vabadus punktide panemisel otsustada, kui palju parandusi vastu võtta ja mis kujul neid saada (diff, kogu töö, selgitused, intervjuu, misiganes), aga keegi meist ei pane lihtsalt punkte juurde, kui lahendus on "peaaegu õige". Lahendused on kas õiged või mitte; peaaegu õigeid lahendusi ja alternatiivseid fakte me siin aines ei tunnista.
Teooria hindame Moodle'i kordamistestidega ja loenguküsimustega.
- Kodused kordamistestid annavad kokku 10 punkti.
- Iga loengutesti eest on võimalik saada kuni 1 punkt. Me teeme neid teste igas loengus, aga arvesse lähevad ainult 10 parimat sooritust.
Nädala kava
Töö korraldus sellel kursusel tiirleb kodutööde ümber. Kuna meil on erinevad praktikumide ajad, siis kodutöid tutvustatakse loengus ning seal seletatakse ka nende lahendamiseks vajalikku teooriat ja programmeerimise soovitusi. Praktikumides eeldame, et olete loengus kohal käinud või loengu salvestust vaadanud.
- E 10:15 Loeng. Räägime teooriast ja tutvustame uut kodutööd. Enne loengut peab olema läbi loetud vastav õpiku peatükk. Selle kohta lahendame loengus ActiveQuiz küsimusi.
- T-N Praktikumid. Lahendame kodutöödega sarnaseid ülesandeid ja vastame küsimustele kodutööde kohta. Palume selleks ajaks loengu materjalidega, kodutööga ja kordamistesti küsimustega tutvuda, et oleksid teooriaga piisavalt kursis, et seda saaks praktikas rakendada.
- T-R Fleep! Kodutööde lahendamisel me eeldame, et tekkivad probleeme ja mõnedel kodutöödel on vähe selgitusi, kuidas peaks lahendama. See ei tähenda, et ei või küsida täpsustusi ja selgitusi juurde! Selleks on Fleepi abikeskus.
- E 10:00 Kordamistesti tähtaeg. Tasub varakult sellega tutvust teha. Seda võib teha nii palju kordi kui vaja, et nädala materjal saaks selgeks. Kordamistesti kohta saab samuti küsimusi küsida Fleepis.
- T 14:00 Kodutöö tähtaeg. Tegelikult võiks varem lahendada, et probleemide korral saaks õigeaegselt abi küsida. Me hoiame Moodle'i lahti kuni teisipäevani. Praktikumides arutatakse lahendusi, mistõttu teisipäeval 14:00 on range tähtaeg.
Kodutööde plaan
Kursuse lõpuks oled oma käega ühe lihtsa keele jaoks kompilaatori ehitanud, aga enne kui ANTLRiga keelte disainimise juurde läheme, tuleb mõndadest keele spetsifitseerimise koostisosadest põhjalikumalt aru saada ja neid enda käega implementeerida.
- Grep. Me peame alustama keele sõnade äratundmisega. Programmeerimiskeelte sõnu kirjeldatakse regulaaravaldistega, aga need on ka niisama kasulikud ja me peatume nende juures natuke. Meie esimese projekti lõppsiht on implementeerida töövahend nimega grep, mis trükib välja failist kõik sellised read, mis sobituvad etteantud regulaaravaldisega. Kõigepealt aga kordame natuke Javat ja kasutame regulaaravaldisi Javas.
- 1. Brute Force. Enne kui hakata siin mingeid uusi asju õppima, võiks ju proovida oma praeguste oskustega sarnast ülesannet lahendada. Esimene kodutöö ei vaja ühtegi uut mõistet, aga natuke peab muidugi mõtlema, kuidas OOPis õpitu kokku kombineerida.
- 2. Regulaaravaldised Javas. Loengus defineeritakse regulaaravaldised teoreetilisest vaatenurgast. Kodutöös proovime neid Javas kasutada, aga alustame ka nende uurimist, et saaks ise regulaaravaldisi manipuleerida.
- 3. Olekumasinad. Regulaaravaldis defineerib sõnade hulga. Kuidas otsustada, kas mõni etteantud sõna kuulub sinna hulka? Regulaaravaldisele vastavat hulka kuuluvust saab kontrollida lõpliku automaadiga! See on sisuliselt olekumasin, mis on jällegi omaette huvitav nähtus!
- 4. NFA. Meie grep töövahendi implementatsiooni idee on teisendada regulaaravaldis mittedeterministlikuks lõplikuks automaadiks. Siis saab iga sõna puhul kiiresti öelda, kas see sobitub regulaaravaldisele või mitte. Selleks on vaja, et me saaks mittedeterministlikke automaate käivitada!
- 5. Grep. Lõpuks teisendame eelmise kodutöö regulaaravaldised automaatideks, mis kokku moodustavad ühe natuke lihtsustatud grepi implementatsiooni.
- Käsitsi. Järgmisena tuleks sõnadest moodustada laused. Keele süntaks defineeritakse grammatikate abil. Tutvume selle mõistega ja siis proovime käsitsi kirjutada oma süntaksianalüsaatori. Hiljem genereerime seda osa automaatselt, aga alguses on hea teada selle tööriista põhimõtteid.
- 6. Lexer. Käsitsi lekseri kirjutamine on üks suhteliselt tüütu tegevus, aga üks kord elus võiks selle ikkagi proovida läbi teha. Sel ajal võiks ka selle tööpõhimõtte, maximal munch, selgeks saada.
- 7. Parser. Parseri kirjutamine on oluliselt mõnusam ja tegelikult üks suurepärane harjutus rekursiooni kohta. Me harjutame seetõttu ka mingite pisikeste grammatikate teisendamist parseriteks.
- Kompilaator Nüüd oleme lõpuks valmis kasutama seda maagilist tööriista ANTLR, et defineerida oma keele grammatika ja sealt edasi minna ka interpretaatori ning päris kompilaatorini, mis genereerib Java virtuaalmasina baitkoodi.
- 8. ANTLR Grammatika. Kui oskame keele süntaksi grammatika abil spetsifitseerida, siis võib sellest automaatselt parseri koodi genereerida.
- 9. Abstraktne süntakspuu. Grammatika defineerib keele süntaksi, aga võib-olla mitte kõige paremini selle keele sisulist struktuuri. ANTLRi parser annab meile automaatselt programmile vastava parsepuu, aga seda tuleks natuke teisendada, et jõuda sisulisema abstraktse süntaksipuuni.
- 10. Interpretaator. Me oleme nüüd valmis etteantud süntaksipuud väärtustama! Selle lahendamisel peame mõtlema ka selle peale, mida me täpselt kirjutame, sest tegelikult võiks meil olla ettekujutus programmi täitmise protsessist. Mida paremini oskad enda peas programmi "interpreteerida", seda paremini oskad ka programmeerida.
- 11. Semantiline analüüs. Mõned analüüsid on vaja teostada programmi vaheesituse peal, et saada selle tähendusest aru. Minimaalselt peame jälgima muutujate skoope ja seostama muutuja kasutust tema definitsiooniga.
- 12. Kompilaator. Lõpuks tõmbame otsad kokku ja genereerime Java virtuaalmasina baitkoodi ASM teegi abil. Nüüd võime ennast pidada tõsiseltvõetavaks programmeerijaks, kes on enda käega kompilaatori ehitanud! Lõpuks tõmbame otsad kokku ja genereerime Java virtuaalmasina baitkoodi abil.
See on üsna ambitsioonikas programm! Me soovime Sulle edu oma sisemise programmeerija avastamisel ja palume probleemide tekkimisel kohe Fleepis abi küsida!