6. 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. Avaldiste parsimisel tahame lõpuks saada abstraktse süntakspuu, kus operaatorite prioriteedid on õiged.
Esimene nädal
Üritame mõisted nagu mitmesus, derivatsioon ja süntakspuu endale selgeks teha. 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 on meil lisatööna võimalik lahendada!
Järgmises kodutöös tuleb implementeerida AKT keele avaldiste parser! Selle tähtaeg on ülejärgmine nädal, sest järgmises loengus alles räägitakse (ühestest) avaldisgrammatikatest, aga see nädal 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 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 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. Meil on ka parsimise ülesandeid, mis nõuavad natuke rohkem teooriat, aga jätame need 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 juba 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!