Mitmesed ja ühesed grammatikad
Loodetavasti on juba täiesti selge, kuidas grammatika spetsifitseerib sõnade hulga. Meid ei huvita aga ainult lõplik sõnade hulk, vaid tihti ka lause tähendus. Kui grammatika abil spetsifitseerime programmeerimiskeele avaldised, siis selliste matemaatiliste avaldiste puhul on lause struktuur väga oluline, kuna see mõjutab operaatorite rakendamise järjekord. Meil on lõpuks programmi täitmiseks vaja kätte saada üheselt defineeritud süntakspuu.
Mitmene gramatika
Praegu keskendume sellele, et mitmesuse probleemist aru saada. Selleks peab aru saama, millal erinevad derivatsioonid tekitavad erinevad süntakspuud. Alustame sellise mitmese grammatikaga:
(Kasutame lekseemi klassi id asemel lihtsalt üks konkreetne muutuja "x".)
- Vaatame Varmo näide
x+x*x. Teeme sellest sõnest kokku neli derivatsiooni: kaks vasak ja kaks paremderivatsioon! Sõnade hulga seisukohalt ei ole derivatsiooni strateegia oluline. Iga derivatsioon on tõend, et antud sõne kuulub meie keelde. - See on nüüd selge, et
x+x*xkuulub keelde, aga derivatsiooni põhjal pidime ka kätte saama avaldise struktuuri. Võtta kõik neli derivatsiooni ja joonista nendele vastavad süntakspuud! - Ürita aru saada, mis seos on derivatsiooni ja süntakspuu vahel. Selleks on hea mõelda, millised valikud on meil derivatsiooni teostamisel. Meil on kahte tüüpi valikud. Milline nendest valikutest on süntakspuu seisukohalt olulisem?
- Me saame valida millist reeglit rakendada, kuna näiteks E jaoks on mitut reeglit, siis saab meie derivatsioonide algul
Easendada nii liitmise kui ka korrutamise avaldistega. - Me saame valida, millist mitte-terminali asendada, näiteks
E+Esaab asendada esimest või teist mitte-terminali.
- Me saame valida millist reeglit rakendada, kuna näiteks E jaoks on mitut reeglit, siis saab meie derivatsioonide algul
- Fikseeritud derivatsiooni strateegia võtab meilt teist laadi valikuid ära. Fikseeri endale oma lemmikstrateegia: vasak või parem... jah, oleme siin ekstremistid. Vaata nüüd sõne
x+x*xkõik derivatsioonid, mis kasutavad sinu valitud derivatsioonistrateegia. Need peaksid ka viima kahe erineva süntakspuudeni. - Veendu, et iga süntakspuu pealt saab süstemaatiliselt (näiteks) vasakderivatsioon välja lugeda. (See tähendab, et sa pead südamest tunnetama, et sul ei ole mingit valikut: puu määrab millist reeglit valida ja strateegia fikseerib millist mitte-terminali asendada). Kui strateegia on fikseeritud, siis saadki puu käest alati üks ja sama derivatsioon.
Kokkuvõtteks:
- Igale (suvalisele) derivatsioonile vastab üks süntakspuu.
- Igale süntakspuule vastab täpselt üks fikseeritud strateegiaga derivatsioon.
- Seega, kui maailmas oleks ainult lubatud vasak-derivatsioone (või ainult parem-derivatsioone), siis oleks süntakspuu ja derivatsiooni mõiste sisuliselt eristamatud.
- Grammatika on mitmene kui ühele sõnale leidub mitut süntakspuud (ehk mitut fikseeritud strateegiaga derivatsiooni).
Ühene grammatika
Prooime nüüd intuitiivselt välja mõelda, kuidas avaldisgrammatikast võiks mitmesust eemaldada. Selle kohta räägitakse loengus ja võib ka lugeda õpikus, aga parem oleks üritada ise mõelda: kuidas saan grammatikas valikuid piirata?.
Alustame ainult operaatorite prioriteediga. Võtame konkreetselt x+x*x. Mida peame tegema, et vältida (x+x)*x moodi tõlgendust? Kuidagi peaks defineerima alamkeeled, näiteks liidetavad, tegurid, vms, et saaks väljendada seda, et tegur ei või sisaldada liitmist (kui ta just sulgudes ei ole). Praktikumijuhendajaga võib siin arutada ka sulgude rolli või üritad ise mõelda, kuidas nendesse suhtuda, aga see on kindlasti üks võtmekoht. Näita vastust!
Järgmine grammatika on veel mitmene, aga tahtsimegi siin ainult prioriteete paika panna. Meil on kaks tase: avaldised E ja liidetavad L.
Avaldis on plussiga eraldatud liidetavad, aga liidetav ei sisalda ise liitmist! Me oleme sellega keelanud täpselt seda olukorda, et x+x saaks tõlgendada tegurina. Sulud aga töötavad selliste pakenditena, mis teevad keerulisest avaldisest kompaktset aatomit, mistõttu sulgavaldist võib tegurina kasutada küll.
Järgmisena vaatame, kas saame samamoodi kontrollida operatsioonide assotsiatiivsust? Kuna liitmise ja korrutamise juures ei ole väga vahet, siis mõtleme pigem lahutamise kohta, et tahame nüüd piirata seda, et 5-3-1 tõlgendataks alati kui (5-3)-1. Kuidas nüüd siin mõelda? Mingi analoogia võiks olla tasemetega, sest me jällegi tahaks keelata, et lahutamine (ilma sulgudeta) toimuks parempoolsel avaldisel. Kirjuta grammatika ümber, et liitmine ja korrutamine oleksid paremassotsiatiivsed. Näita vastust!
Me peame nüüd kolmanda taseme sisse tuua, et saaksime korrutamise juures keelata korrutisavaldiste esinemist operaatorist paremal:
Jällegi on oluline, et sulud on viimasel tasemel ja pakkivad suvalist avaldist kokku teguriks, mida võib sisuliselt igal pool kasutada.
Lõpuks võiks lisada mõned operatsioonid veel, et rohkem intuitsiooni arendada.
- Lisame unaarse operatsiooni, näiteks miinus, mis on (siiamaani) kõige kõrgema prioriteediga:
-x+xparsitakse kui(-x)+x. - Lisage faktoriaali operatsioon ja tehke kindlaks, et
-x!saaks ainult parsida kui-(x!).
Lausearvutuse valem
Selle implementeerimine on meil lisatööna, aga väga hea harjutus oleks lihtsalt enda jaoks grammatika kirja panna. Kõigepealt proovige mitmest grammatikat teha otse definitsiooni põhjal ja siis kihideks jaotada loengu põhimõttete alusel. Pange ka tähele, et see ei ole kokkusattumus, et selle õpiku definitsiooni põhjal saab otse grammatika kirjutada! Iga grammatika saab ka mõista kui vähim hulk, mis rahuldab teatud tingimusi, näiteks:
| A → x | x ∈ A |
| A → aAb | kui w ∈ A, siis ka awb ∈ A |