7. Käsitsi parsimine
Meie eesmärk on nüüd käsitsi kirjutada parserid. Grammatikast parseri saamine on väga lihtne, kui grammatika on õigel kujul. Seetõttu peab kõigepealt aru saama, kuidas grammatikad disainida, et tulemus oleks ühene ja saadud parsepuu pealt oleks võimalik välja lugeda alloleva lause struktuur. Avaldisete parsimisel tahame lõpuks saada abstraktne süntakspuu, kus operaatorite prioriteedid on õiged.
Esimene nädal
Üritame mõisted nagu mitmesus, derivatsioon ja süntakspuu endale selgeks tegema. Me alustame ka kihiliste avaldisgrammatikatega tutvumist, sest nende disainipõhimõtte võiks olla meile kõigile suureks eeskujuks. Praegu on ka eriti relevantsed järgmised lisatööd:
- Võite vaadata Pythoni näitel, mida kujutab endast programmi süntaksipuu. (Kuna selles aines on põhifookus Javal, siis piisab, kui tollelt lehelt lugeda vaid esimene osa kuni pealkirjani "Pythoni AST tekitamine".)
- Edasi võib ka vaadata, kuidas Java Spetsifikatsioonis on kõik keele avaldised kiht-haaval välja toodud. Soovitame uurida Java süntaksipuid ja sealolev lisatöö ära teha!
- Lausearvutuse valem. Suurepärane harjutus avaldisgrammatika koostamiseks on meie neljas lisatöö!
Esimesel nädalal tuleb lõpetada lekseri kodutöö. Kes on juba valmis, võib piiluda järgmist kodutööd, kus tuleb siis implementeerida AKT keele avaldiste parser! See on tegelikult üsna lihtne, aga me räägime sellest rohkem teisel nädal. Kui lekser on juba tehtud, siis võiks vähemalt AST klassidega alustada!
Teine nädal
Meil on nüüd teoorias kõik selge ja oskame avaldisgrammatika ilusasti kirja panna, et loetakse operaatorid õigete prioriteetidega ja assotsiatiivsusega. Nüüd teisendame lihtsalt grammatika parseriks!
- Java implementatsioon. Teisendame grammatika Java koodiks, mis teostab süntaksanalüüsi ja loob sõnele vastava parsepuu (või otse abstraktse süntaksipuu). Kahjuks tekib meil seal probleeme oma avaldisgrammatikatega...
- Vasakrekursiooni elimineerimine. See on lihtne teisendus grammatikate peal, mis võimaldab meil ka vasakassotsiatiivsed avaldisgrammatikad korrektselt parsida!
See peaks olema piisav ettevalmistus kodutöö lahendamiseks. Antud käsitlus on aga võrdlemisi pealiskaudne. Eksami lõviosas on meil ka parsimise ülesanne, mis nõuab natuke rohkem teooriat, aga suuresti jätame seda iseseisvaks uurimiseks, sest ta ei ole nii fundamentaalse tähtsusega kui need põhitõdesid, mis praktikumi põhikavasse kuuluvad.
Kuna need teemad muutuvad üsna tehnilisteks, tuleb meeles pidada, et eesmärk on siin arendada modulaarset mõtteviisi. Grammatika ja rekursioon, nendes juba peituvad kogu informaatika põhitõdesid, aga eriti kasulik on siin üritada ise välja mõelda, kuidas vasakrekusiooni elimineerimise järel peab tagastama esialgse (vasakassotsiatiivse operaatorite puhul) parsepuu. Kui saad sellest teemast aru, siis võib Sind turvalise koodi kirjutamisega usaldada! Pea meeles, et enamus turvanõrkuste taga on lihtsad koodivead. Parim küberkaitse on kompetentsed programmeerijad!