Automaadid, keeled ja translaatorid - Kursused

Mitmesed ja ühesed grammatikad

Teemat tutvustav video: Avaldisgrammatikad (slaidid).

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 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üntaksipuu.

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:

E → E + E

E → E * E

E → ( E )

E → x

(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*x kuulub keelde, aga derivatsiooni põhjal pidime ka kätte saama avaldise struktuuri. Võta 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üntakspuu seisukohalt olulisem?
- Me saame valida millist reeglit rakendada, kuna näiteks E jaoks on mitut reeglit, siis saab meie derivatsioonide alguses E asendada nii liitmise kui ka korrutamise avaldistega.
- Me saame valida, millist mitte-terminali asendada, näiteks E+E sees saab asendada esimest või teist mitte-terminali.
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*x kõiki derivatsioone, 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?.

Prioriteedid

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 taset: avaldised E ja liidetavad L.

E → E+E | L

L → L*L | (E) | x

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 kompaktse aatomi, mistõttu sulgavaldist võib tegurina kasutada küll.

Assotsiatiivsused

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 parempoolses avaldises. 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:

E → E+L | L

L → L*T | T

T → (E) | x

Jällegi on oluline, et sulud on viimasel tasemel ja pakivad suvalise avaldise teguriks kokku, mida võib sisuliselt igal pool kasutada.

Harjutused

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+x parsitakse kui (-x)+x.
Lisage faktoriaali operatsioon ja tehke kindlaks, et -x! saaks ainult parsida kui -(x!).
Lisage astendamise operatsioon, mis oleks paremassotsiatiivne (x^x^x peaks parsima kui x^(x^x)) ning kõrgema prioriteediga kui unaarne miinus, aga madalama prioriteediga kui faktoriaal (-x^x! peaks parsima kui -(x^(x!))).

Hea disaini tavad

Avaldisgrammatika idee on väärt meelde jätta. Kui seda naiivselt disainida, on oht, et tehakse sulgude käsitlemiseks väga palju sigadusi. Grammatika disain on väga hea koht harjutada hea disaini tavasid. Kui oskame ühe lihtsa grammatika juures häid disaini tavasid rakendada, siis on lootust, et disainime süsteeme ka nende heade disaini tavade järgi!

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