Tere tulemast kompilaatori 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!
| Põhipunktid: 100 | Lisapunktid: 30 |
|---|---|
| Kodutööd (30 punkti) | Tähtajatud kodutööd (15 lisapunkti) |
| Kordamistestid (10 punkti) | Loengust osavõtt (10 lisapunkti) |
| Eksam (60 punkti) | Boonus (5 lisapunkti) |
Hindamisskaala on lõpuks selline, et >50 on E, >60 on D, ..., >90 on A. Kodutöö ülesannete eest peab koguma vähemalt 15 punkti! Aines on kokku 12 põhilist kodutööd, mille lahendamiseks on nädal aega. Nendele lisaks paneme ka paljude teemade juurde välja tähtajatud kodutööd. (Neid tuleb siiski esitada enne eksamit ja nendega arvestatakse ka lävendi ületamiseks.)
Kodutööd hinnatakse läbitud testide järgi ja nende tulemus jagatakse neljaga lõpphinne arvestuses. 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 Fleepiis. Teil on ka võimalus Fleepis küsida tagasiside ja oma tulemusi parandada, kui automaatkontroll oli sinu vastu liiga kuri. Me avalikustame selleks ajaks kodutöö lahendust, 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 kordamistestidega ja loengu küsimustega.
- Kodused kordamistestid annavad kokku 10 punkti. Iganädalased testid annavad 0.8 punkti. Kokku on 12 testi, aga viimane on natuke suurem (eksamiks kordamiseks) ja annab 1.2 punkti.
- Iga loengu test eest on võimalik saada kuni 1 punkt. Me teeme igal loengus neid teste, aga kokku saab koguda nende eest maksimaalselt 10 punkti.
Nädala kava
Töö korraldus sellel kursusel tiirleb kodutööde ümber. Kuna meil on erinevad praktikumi ajad, siis kodutööd tutvustatakse loengus ja seal seletatakse ka nende lahendamiseks vajalik teooria ja programmeerimise soovitused. Praktikumides eeldame, et olete loengus kohal käinud või loengu lindistust vaadanud.
- E10:15 Loeng. Räägime teooriast (60 minutit) ja tutvustame uut kodutööd (30 minutit).
- T-N Praktikumid. Lahendame kodutöödega sarnased ülesanded ja vastame küsimustele kodutööde kohta. Palume selleks ajaks loengu materjalidega, kodutööga ja quizi küsimustega tutvuda, et teooriaga oleksid piisavalt kursis, et seda saaks praktikas harjutada.
- 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.
- E10:00 Quizi tähtaeg. Ideaalne aeg quizi lahendamiseks on esmaspäeval peale loengut, aga seda võib teha nii palju kordi kui vaja, et nädala materjal saaks selgeks. Quizi kohta saab samuti küsimusi küsida Fleepis.
- T14:00 Kodutöö tähtaeg. Tegelikult võiks varem lahendada, et probleemide korral saaks õigeaegselt abi küsida. Me hoiame moodle lahti kuni teiseipäevani. Praktikumides arutatakse lahendusi, mistõttu teisipäeval 14:00 on range tähtaeg.
Kodutööde plaan
Kursuse lõpuks oled siis oma käega ühe lihtsa keele jaoks kompilaatori ehitanud, aga ma kohe ei alusta ANTLRiga keelte disainima enne kui oleme mõnedest keele spetsifitseerimise koostisosadest kõigepealt põhjalikumalt aru saanud ja enda käega implementeerinud.
- Grep. Me peame alustama keele sõnade ära tundmisega. Programmeerimiskeelte sõnu kirjeldatakse regulaaravaldistega, aga need on ka niisama kasulikud ja peatume natuke nende juures. Meie esimese projekti lõppsiht on implementeerida selline töövahend nimega grep, mis trükib välja failist kõik ridu, mis sobituvad etteantud regulaaravaldisega. Kõigepealt aga kordame natuke Javat ja kasutame regulaaravaldised Javas.
- 1. Brute Force. Enne kui hakkata mingeid asju siin õppida 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 siis regulaaravaldised teoreetilisest vaatenurgast. Kodutöös proovime neid Javas kasutada, aga alustame ka nende uurimist, et saaks ise regulaaravaldist manipuleerida.
- 3. Olekumasinad. Regulaaravaldis defineerib sõnade hulga. Kuidas otsustada, kas mõni etteantud sõna kuulub sinna hulka? Regulaaravaldisele vastava hulka kuuluvust saab kontrollida lõpliku automaadiga! Ta on sisuliselt olekumasin, mis on jällegi omaette huvitab nähtus!
- 4. NFA. Meie grep töövahendi implementatsiooni idee on siis teisendada regulaaravaldis mitte-deterministlikuks lõplikuks automaadiks. Siis saab iga sõna puhul kiiresti öelda, kas sobitub regulaaravaldisele või mitte. Selleks on vaja, et me saaks mittedeterministlike automaate käivitada!
- 5. Grep. Lõpuks teisendame regulaaravaldist eelmise kodutöö automaatideks, mis kokku moodustab siis ühe natuke lihtsustatud grepi implementatsiooni.
- Käsitsi. Järgmisena tuleks nüüd sõnadest moodustada laused. Keele süntaksit defineeritakse grammatikate abil. Tutvume selle mõistega ja siis proovime käsitsi kirjutada oma süntaksanalüsaatori. Pärast genereerime seda osa automaatselt, aga hea on 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 nende 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 kasutada maagilise tööriista ANTLR, et defineerida oma keele grammatika ja sealt edasi minna ka interpretaator ja päris kompilaatorini, mis genereerib Java virtuaalmasina baitkoodi.
- 8. ANTLR Grammatika. Kui oskame keele süntaks grammatika abil spetsifitseerida, siis võib sellest automaatselt parseri koodi genereerida. Selle
- 9. Abstraktne süntakspuu. Grammatika defineerib keele süntaksit, aga võib-olla mitte kõige paremini selle keele sisuline struktuur. ANTLRi parser annab meile automaatselt programmile vastav parsepuu, aga seda tuleks natuke teisendada, et jõuda sisulisema abstraktse süntakspuuni.
- 10. Nimede sidumine. Mõned analüüsid on vaja teostada programmi vaheesituse peal, et saada selle tähendusest aru. Minimaalselt peame jälgima muutujate skoopid ja seostada muutuja kasutus tema definitsiooniga.
- 11. Interpretaator. Me oleme nüüd valmis etteantud süntakspuu väärtustada! Selle lahendamisel peaks just mõtlema ka selle peale, mida me kirjutasime, sest tegelikult võiks meil olla selline ettekujutus programmi täitmisest. Mida paremini oskad enda peas programmi "interpreteerida", seda paremini oskad ka programmeerida.
- 12. Kompilaator. Lõpuks tõmbame otsad kokku ja genereerime Java virtuaalmasina baitkoodi ASM teegi abil. Lõpuks võime enneast pidada tõsiseltvõetavateks programmeerijateks, kes on enda käega kompilaatori ehitanud!
See on üsna ambitsioonikas programm! Me soovime edu Sulle edu oma sisemise programmeerija avastamisel ja palume probleemide tekkimisel kohe Fleepis abi küsida!