Lausekekielioppien yksiselitteistäminen

(Alun perin kurssin TIEA241 Automaatit ja kieliopit syksy 2017 materiaaleista.)

Aritmeettisten lausekkeiden ja muiden samankaltaisten kielten luontainen kontekstiton kielioppi tekee jokaisesta operaattorista oman produktionsa. Näiden lisäksi produktiot tulevat vakiolle ja muille vastaaville konstruktioille sekä sulkeille:

E → c
E → - E
E → E + E
E → E - E
E → E * E
E → E / E
E → ( E )

Samantyyppinen kielioppi voidaan kirjoittaa myös säännöllisille lausekkeille:

R → ∅
R → ( )
R → c
R → R *
R → R R
R → R | R
R → ( R )

Kummankin kieliopin ongelma on moniselitteisyys. Esimerkiksi lausekkeelle c + c * c on mahdollista tehdä kaksi johtoa E:stä, joissa aina valitaan vasemmanpuoleisin välikesymboli (ns. vasen johto):

E ⇒ E + E ⇒ c + E ⇒ c + E * E ⇒ c + c * e ⇒ c + c * c

E ⇒ E * E ⇒ E + E * E ⇒ c + E * E ⇒ c + c * E ⇒ c + c * c

Nämä kaksi johtoa eroavat siinä, pidetäänkö yhteenlaskua vai kertolaskua lausekkeen pääoperaattorina eli operaattorina, joka lasketaan viimeiseksi. Jatkossa tulemme käyttämään kontekstitonta kielioppia ohjaamaan syötteen jäsennystä (ja jäsennys puolestaan voi ohjata esimerkisi ohjelman käännösprosessia tai laskimessa laskennan etenemistä), joten olisi toivottavaa, että kielioppi olisi yksiselitteinen. Onneksi tällaisille kieliopeille on varsin yksinkertainen menetelmä yksiselitteistämiseen.

Ensiksi tulee luokitella produktiot:

• produktio on primäärilauseke, jos se ei ala eikä pääty lausekkeen välikesymbolilla, esim. R → c ja R → (R)
• produktio on prefiksilauseke, jos se päättyy mutta ei ala lausekkeen välikesymbolilla, esim. E → - E
• produktio on postfiksilauseke, jos se alkaa mutta ei pääty lausekkeen välikesymbolilla, esim. R → R *
• produktio on infiksilauseke, jos se sekä alkaa että päättyy lausekkeen välikesymbolilla, esim. R → R | R

Näissä produktioissa operaattori on produktiossa esiintyvien päätemerkkien jono (esim. ( ), *, |). Joskus usealla eri produktiolla voi olla sama päätemerkkien jono (esim. negaatio ja vähennyslasku), mutta joka produktio määrittelee tästä huolimatta eri operaattorin.

Seuraavaksi kaikille operaattoreille (pois lukien primäärilausekkeet) määritellään presedenssijärjestys ja assosiatiivisuus. Niitä käytetään moniselittelisyyden ratkaisemiseen silloin, kun operaattoreita on peräkkäin; esim. tarkoittaako c|c* samaa kuin (c|c) vai samaa kuin c|(c)? Se operaattori, jolla on korkeampi presedenssi, lasketaan ensin. Jos operaattoreilla on sama presedenssi, määräytyy laskujärjestys assosiatiivisuuden nojalla:

• jos kaikki tarkasteltavat operaattorit assosioivat vasemmalle (eng. associate to the left), laskujärjestys on vasemmalta oikealle
• jos kaikki tarkasteltavat operaattorit assosioivat oikealle (engl. associate to the right), laskujärjestys on oikealta vasemmalle
• jos operaattoreilla on eri assosiatiivisuus tai ne eivät assosioi (engl. nonassociative), lauseke on hylättävä virheellisenä

Käytännössä prefiksioperaattorit eivät voi assosioida vasemmalle eivätkö postfiksioperaattorit oikealle.

Tavallisesti presedenssi ja assosiatiivisuus esitetään seuraavankaltaisena taulukkona (korkeampi presedenssi on taulukossa ensin):

R → R *	assisoioi vasemamalle
R → R R	assisoioi vasemamalle
R → R | R	assisoioi vasemamalle

Samalla rivillä (eli presedenssitasolla) voi olla useita produktioita, mutta tällä kertaa niin ei käynyt.

Seuraavaksi kullekin presedenssitasolle luodaan oma välikesymbolinsa. Tässä tapauksessa tarvitaan kolme: K (Kleene), C (concatenate) ja  A (alternate). Jos jollakin presedenssitasolla on useita assosiatiivisuuksia, kullekin niistä luodaan lisäksi oma välikesymbolinsa. Lisäksi tarvitaan oma välikesymboli primäärilausekkeille (usein P).

Kukin alkuperäisen kieliopin produktio muokataan seuraavasti:

1. nuolen vasemmalle puolelle tulee operaattorin presedenssin ja assosiatiivisuuden mukaan valittu uusi välikesymboli (primäärilausekkeiden tapauksessa primäärilausekkeiden välikesymboli)
2. produktion seuraavat reunimmaiset välikesymbolit muutetaan seuraavaksi korkeamman presedenssitason (tai jos sitä ei ole, primäärilausekkeiden) välikesymboliksi
   1. vasemmalle assosioivan operaattorin tapauksessa vain oikeanpuoleisin
   2. oikealle assosioivan operaattorin tapauksessa vain vasemmanpuoleisin
   3. ei assosioivan operaattorin tapauksessa sekä vasemmanpuoleisin että oikeanpuoleisin
3. produktion muut reunimmaiset lausekekieliopin välikesymbolit korvatan produktion vasemmalla puolella olevalla välikesymbolilla

Lisäksi luodaan seuraavat uudet produktiot:

1. joka presedenssitasolle ja sen assosiatiivisuudelle luodaan lisäksi uusi produktio A → B, missä A on kyseisen presedenssi- ja assosiatiivisuusluokan välikesymboli ja B on seuraavaksi korkeamman presedenssitason (tai jos sitä ei ole, primäärilausekkeiden) välikesymboli
2. jos presedenssitasolla, jonka välikesymboli on A, on useita assosiatiivisuusluokkia, kunkin assosiatiivisuusluokan välikesymbolille B luodaan produktio A → B
3. alkuperäisen kieliopin välikesymbolin A kaikki produktiot korvataan yhdellä produktiolla A → B, missä B on matalimman presedenssitason välikesymboli

Säännöllisten lausekkeiden tapauksessa saadaan tällainen uusi kielioppi (oikeassa reunassa viitataan yllä numeroituihin kohtiin, eka lista sellaisenaan ja toka lista Unumero)

R → A	U3
A → C	U1
A → A | C	2.1
C → K	U1
C → C K	2.1
K → P	U1
K → K *	2.1
P → ∅	1
P → c	1
P → ( )	1
P → ( R )	1