AKT teemade ülevaade
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 teostada.
Leksiline analüüs
Peame alustama keele sõnade äratundmisega. Programmeerimiskeelte sõnu kirjeldatakse regulaaravaldistega, aga need on ka niisama kasulikud ja 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. Mini AKTK. 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. Regex. Loengus defineeritakse regulaaravaldised teoreetilisest vaatenurgast. Kodutöös proovime neid Javas kasutada, aga alustame ka nende uurimist, et saaks ise regulaaravaldisi manipuleerida.
- 3. NFA realiseerimine. Meie grep töövahendi implementatsiooni idee on teisendada regulaaravaldis mittedeterministlikuks lõplikuks automaadiks. Siis saab iga sõna puhul kiiresti öelda, kas see sobitub regulaaravaldisega või mitte. Selleks on vaja, et saaksime mittedeterministlikke automaate käivitada!
- 4. Grep. Lõpuks teisendame eelmise kodutöö regulaaravaldised automaatideks, mis kokku moodustavad ühe natuke lihtsustatud grepi implementatsiooni.
Süntaksanalüüs
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.
- 5. Käsitsi lekser. 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.
- 6. Käsitsi parser. Parseri kirjutamine on oluliselt mõnusam ja tegelikult üks suurepärane harjutus rekursiooni kohta. Harjutame seetõttu ka mingite pisikeste grammatikate teisendamist parseriteks.
- 7. ANTLR. Kui oskame keele süntaksi grammatika abil spetsifitseerida, oleme lõpuks valmis kasutama seda maagilist tööriista ANTLR, et automaatselt parseri koodi genereerida. Grammatika defineerib keele süntaksi, aga võib-olla mitte kõige paremini selle keele sisulist struktuuri. Seetõttu annab ANTLRi parser meile automaatselt programmile vastava parsepuu, aga seda tuleks natuke teisendada, et jõuda sisulisema abstraktse süntaksipuuni.
Semantiline analüüs ja koodi genereerimine
Meil on lõpuks käes abstraktne süntaksipuu, mis väga mugavalt esitab programmi sisulist struktuuri. Soojendusena kirjutame interpretaatori, mis otse tõlgendab seda programmi, aga meie lõppsiht on genereerida päris Java virtuaalmasina baitkoodi.
- 8. Interpretaator. Seega kirjutame kõigepealt programmi, mis etteantud süntaksipuud väärtustab! Selle lahendamisega areneb meie ettekujutus programmi täitmise protsessist. Mida paremini oskad enda peas programmi „interpreteerida“, seda paremini oskad ka programmeerida.
- 9. Semantiline analüüs. Kui lõppsiht on programmi teisendamine baitkoodiks ehk kompileerimine, siis on mõttekas enne programmi täitmist seda uurida, näiteks võime kontrollida, et muutujate tüübid klappivad.
- 10. 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!
See on üsna ambitsioonikas programm! Soovime Sulle edu oma sisemise programmeerija avastamisel ja palume probleemide tekkimisel kohe Zulipis abi küsida!