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ärjekorda. Meil on lõpuks programmi täitmiseks vaja kätte saada üheselt defineeritud süntakispuu.
Mitmene grammatika
Praegu keskendume sellele, et mitmesuse probleemist aru saada. Selleks peab aru saama, millal erinevad derivatsioonid tekitavad erinevad süntaksipuud. Alustame sellise mitmese grammatikaga:
(Kasutame lekseemiklassi id asemel lihtsalt ühte konkreetset muutujat "x".)
- Vaatame Varmo näidet
x+x*x. Teeme sellest sõnest kokku neli derivatsiooni: kaks vasak- ja kaks paremderivatsiooni! 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üntaksipuud! - Ürita aru saada, mis seos on derivatsiooni ja süntaksipuu vahel. Selleks on hea mõelda, millised valikud on meil derivatsiooni teostamisel. Meil on kahte tüüpi valikud. Milline nendest valikutest on süntaksipuu seisukohalt olulisem?
- Me saame valida millist reeglit rakendada, kuna näiteks E jaoks on mitut reeglit, siis saab meie derivatsioonide alguses
Easendada nii liitmise kui ka korrutamise avaldistega. - Me saame valida, millist mitte-terminali asendada, näiteks
E+Esees saab 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 alguses
- 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 derivatsioonistrateegiat. Need peaksid ka viima kahe erineva süntaksipuuni. - Veendu, et iga süntaksipuu 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 ühe ja sama derivatsiooni.
Kokkuvõtteks:
- Igale (suvalisele) derivatsioonile vastab üks süntaksipuu.
- Igale süntaksipuule vastab täpselt üks fikseeritud strateegiaga derivatsioon.
- Seega, kui maailmas oleks ainult lubatud vasak-derivatsioonid (või ainult parem-derivatsioonid), siis oleks süntaksipuu ja derivatsiooni mõiste sisuliselt eristamatud.
- Grammatika on mitmene kui ühele sõnale leidub mitu süntaksipuud (ehk mitu fikseeritud strateegiaga derivatsiooni).
Ühene grammatika
Proovime nüüd intuitiivselt välja mõelda, kuidas avaldisgrammatikast võiks mitmesust eemaldada. Sellest räägitakse loengus ja võib ka lugeda õpikust, 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 vasakassotsiatiivsed. Näita vastust!
Me peame nüüd kolmanda taseme sisse tooma, 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 kihtideks jaotada samade põhimõtete alusel. Pange ka tähele, et see ei ole kokkusattumus, et selle õpiku definitsiooni põhjal saab otse grammatika kirjutada! Iga grammatikat saab ka mõista kui vähimat hulka, mis rahuldab teatud tingimusi, näiteks:
| A → x | x ∈ A |
| A → aAb | kui w ∈ A, siis ka awb ∈ A |