Automaadid, keeled ja translaatorid - Kursused

5. Grammatika mõiste ja käsitsi leksimine

Alustame juba grammatika teemaga, et oleks aega seda seedida. Sellel nädalal võiks endale selgeks teha selle põhilise olemuse ehk mis ta on ja kuidas ta keele defineerib. Samal ajal alustame kodutöödes käsitsi lekseri ja parseri kirjutamist. Pärast me loome need ANTLRi abil, kuid nende kodutööde eesmärk on pigem aru saada, mida ANTLR üldse teeb.

Grammatikate koostamine. Alustame sellega, et üritame mõned lihtsad grammatikad ise koostada. Proovime ka implementeerida süstemaatilise meetodi regulaaravaldiste grammatikaks teisendamiseks.
Grammatikale vastavad automaadid. Seda maksab siis vaadata, kui on natuke teoreetilisem huvi asja vastu. Nagu regulaaravaldisele vastab automaat, vastab kontekstivabale grammatikale magasinmäluga automaat.
KalaLekser. Kodutöö ettevalmistuseks kirjutame ühe pisikese lekseri.
Kodutöö. Kodutöös tuleb käsitsi kirjutada lekser AKTK keele jaoks.

Sellel nädalal toome sisse grammatika mõiste. Kontekstivaba grammatika on ise üks elegantne keel (DSL), mis võimaldab hulkasid induktiivselt defineerida. Just sellele tasub tähelepanu pöörata, sest ühelt poolt on see kooskõlas eesmärgiga arendada teil modulaarset ja selget mõtlemist (grammatika on parim viis harjutada selge ja modulaarse disaini põhimõtteid!), aga teiselt poolt on induktiivsed definitsioonid koodi korrektsuse tõestamiseks väga olulised. Kui tahad rohkem teada induktiivsete definitsioonide kohta, siis vajuta

Mis on induktiivne definitsioon? See on täpselt see, kui defineerime hulga selliselt, et anname eeskirja tema elementide koostamiseks. Kõigepealt ütleme, et hulka kuuluvad teatud fikseeritud baaselemendid (aatomid):

Iga üksik täht on regulaaravaldis.
Epsilon on regulaaravaldis.

Edasi anname eeskirjad, kuidas väiksematest elementidest moodustada suuremaid:

Kui R ja Q on regulaaravaldised, siis on ka (RQ) regulaaravaldis.
Kui R ja Q on regulaaravaldised, siis on ka (R|Q) regulaaravaldis.
Kui R on regulaaravaldis, siis on ka (R)* regulaaravaldis.

Ehk kontekstivaba grammatikana:

R → a | b | ...
R → ε
R → (R R)
R → (R | R)
R → (R)*

Ok, mis siis? Miks peaks kedagi olema induktiivsetest definitsioonidest nii vaimustuses? Sellepärast, et selliselt defineeritud hulga puhul teame täpselt, millest on tehtud hulga elemendid. Kui väike tüdruk kuulub hulka R, siis on ta kas baaselement (antud juhul üksik täht või epsilon) või siis koosneb ta veelgi väiksematest osadest, mida on kokku liimitud konkatenatsiooni, alternatsiooni või korduse abil. See teadmine, et iga hulga element on selliselt üles ehitatud saame ära kasutada kahel viisil:

Rekursioon! Funktsioonid sellel hulgal saame defineerida kasutades rekursiooni. Kuna meil on eeskirjad, kuidas iga hulga element on moodustatud, siis võime funktsioonid defineerida nende struktuuri järgi. Me peame ainult defineerima, mida funktsioon teeb baasjuhtumitel ja kui element on üles ehitatud väiksematest osadest, siis me peame ainult oskama alamosade tulemusi kombineerida.
Induktsioon! See on nüüd pärlite pärl: me saame selle hulga elementide kohta asju tõestada! Kui me tahame veenduda, et programm töötab õigesti, siis me ei taha lihtsalt testida üks element siin ja üks element seal. Tahaks midagi öelda kõikide sisendite kohta ja induktiivselt defineeritud hulkade korral saame seda teha!!

Üks triviaalne induktsiooni näide. Oletame, et tahame veenduda, et regulaaravaldised ilma tärnita defineerivad lõplikke keeli. See peaks olema suhteliselt ilmne, aga ka see intuitiivne viis, kuidas ennast selles veenda on sisuliselt üks induktiivne argument. Kõigepealt veendume, et baaselemendid defineerivad lõpliku keele: nad defineerivad kõik ühesõnalisi keeli. (Ka epsiloni keel koosneb ühest sõnast!) Edasi pead lihtsalt veenduma, et alternatsioon ja konkatenatsioon mõlemad säilitavad keelte lõplikkust. Selline mõttekäik ja induktiivsed andmestruktuurid mängivad olulist rolli programmide verifitseerimises.