6. Käsitsi parsimine
Meie eesmärk on nüüd käsitsi kirjutada parsereid. Grammatikast parseri saamine on väga lihtne, kui grammatika on õigel kujul. Seetõttu peab kõigepealt aru saama, kuidas grammatikaid nii disainida, et tulemus oleks ühene ja saadud parsepuu pealt oleks võimalik välja lugeda alloleva lause struktuur. Avaldiste parsimisel tahame lõpuks saada abstraktse süntaksipuu, kus operaatorite prioriteedid on õiged.
Esimene nädal
Üritame endale selgeks teha mõisted: mitmesus, derivatsioon ja süntaksipuu. Me alustame ka kihiliste avaldisgrammatikatega tutvumist, sest nende disainipõhimõte võiks olla meile kõigile suureks eeskujuks. Praegu on ka eriti relevantsed järgmised lisatööd:
- Kui veel ei ole, siis võid 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 lisatööna!
Järgmises kodutöös tuleb implementeerida AKT keele avaldiste parser! Selleks on kaks nädalat, et loengutes kõik vajalik eelnevalt kaetud saaks, kuid see nädal võiks AST klasside loomisega juba alustada!
Teine nädal
Meil on nüüd teoorias kõik selge ja oskame avaldisgrammatika ilusasti kirja panna nii, et operaatorid loetakse õigete prioriteetidega ja assotsiatiivsustega. 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 grammatikate teisendus, mis võimaldab meil ka vasakassotsiatiivseid avaldisgrammatikaid korrektselt parsida!
See peaks olema piisav ettevalmistus kodutöö lahendamiseks. Antud käsitlus on aga võrdlemisi pealiskaudne. Meil on ka parsimise ülesanded, mis nõuavad natuke rohkem teooriat, aga need on suuresti iseseisvaks uurimiseks.
Kuna need teemad muutuvad üsna tehnilisteks, tuleb meeles pidada, et eesmärk on siin arendada modulaarset mõtteviisi. Grammatika ja rekursioon — nendes peituvad kogu informaatika põhitõed, aga kõrgema taseme saavutamiseks on eriti kasulik üritada ise välja mõelda, kuidas vasakrekursiooni elimineerimise järel peab tagastama esialgse (vasakassotsiatiivse operaatorite puhul) parsepuu. Kui saad sellest teemast aru, siis võib Sind turvalise tarkvara arendamisega usaldada!