6. Käsitsi leksimine ja grammatika mõiste
Kodutöös jätkame veel leksimise teemaga. Me peame ka paari nädala pärast ANTLR tööriista abil lekserit spetsifitseerima, aga alustame kõigepealt grammatikaga. Sellel nädalal võiks endale selgeks teha selle põhilise olemuse ehk mis ta on ja mida ta defineerib.
- 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 vaadata, kui on natuke teoreetilisem huvi asja vastu. Nagu ka regulaaravaldisele vastab automaat, siis kontekstivabale grammatikale vastab magasinmäluga automaat.
- Lekser. Kodutöö ette valmistamiseks teeme ühe pisikese lekseri siin ka.
Mis on induktiivne definitsioon? See on täpselt see, kui defineerime hulka 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 eeskirju, kuidas väiksematest elementidest moodustada suuremad:
- 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 konkatenatsioon, alternatsioon või korduseoperaatori abil. See teadmine, et iga hulga element on selliselt üles ehitatud saame ära kasutada kahel viisil:
- Rekursioon! Saame funktsioonid defineerida sellel hulgal 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ärlide 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 konkatenatsiooni mõlemad säilitavad keelte lõplikkust. Selline mõttekäik ja induktiivsed andmestruktuurid mängivad olulist rolli programmide verifitseerimises.