Attribuudid

Süntaksianalüüsi tulemusena saadud puu põhjal arvutama (interpretaatoris) või väljundkoodi genereerima hakates osutub, et puus peab tippude vahel liikuma informatsioon. Vaatleme näitena probleeme, mis tekivad Pütaghorase teoreemi põhjal täisnurkse kolmnurga kaatetite a,b põhjal hüpotenuusi c pikkuse arvutamisel.

Avaldise sqrt(a*a + b*b) puud vaadeldes on selge, et kogu avaldise väärtust on lihtne arvutada kasutades magasini ja läbides puu lõppjärjestuses (endorder): tippudes, kus on väärtused (arvud) panna need magasini ja kui tuleb operatsioon, on operatsiooni argumendid (argument) alati magasini tipus, s.t kui arvutamise algul oli magasinis vaid nn põhjasümbol $, siis magasini sisu muutub puu läbimisel (lõppjärjestuses) selliselt (sulgudesse võetud avaldised tähistavad selle avaldise väärtust, s.t. ühte arvu!):

$
$ a
$ a a
$ a a * $ (a²)
$ (a²) b
$ (a²) b b
$ (a²) b b * $ (a²) (b²)
$ (a²) (b²) + $ ((a²) + (b²)) $ ((a²) + (b²)) sqrt $ (sqrt((a²) + (b²)))

Aritmeetilise avaldise puud on loomulik salvestada abstraktse süntaksi produktsioonidena, näiteks eelneva puu kirjeldavad produktsioonid

avaldis ARV | IDENT
avaldis avaldis '*' avaldis
avaldis avaldis '+' avaldis
avaldis 'sqrt' avaldis

Et nende produktsioonide abil kirjeldada ka arvutuste toimimist, võtame kasutusele mitteterminalidega seotud muutujad - attribuudid. Nende väärtus puus oleva mitteterminali jaoks arvutatakse puu läbimise ajal ja see sõltub nende all või nende kohal olevate tippude, s.t. neid tippe tähistavate mitteterminalide attribuutidest.

Ülalesitatud arvutusskeemis liikus informatsioon puus alt-üles: kõige madalama taseme tippude (a,b - need on lekseemid ARV või IDENT) väärtus on juba varem teada ja iga järgmise taseme tipus saadakse selle tipu väärtus selle all olevate tippude väärtustest. Olgu val (value - väärtus) vastav mitteterminali avaldis attribuut, s.t. muutuja, milles on salvestatud avaldise puus igas mitteterminaliga avaldis tähistatud tipus selle tipu all oleva alampuu väärtus.

Ülalesitatud produktsionides saadakse vasakul pool oleva mitteterminali avaldis attribuudi val väärtus produktsiooni paremal pool olevate mitteterminalide avaldis attribuutide val väärtustest.

Kuna attribuudid on seotud mitteterminalidega, on loomulik anda nende arvutuseeskirjad koos vastava mitteterminali produktsioonidega; neid arvutuseeskirju nimetatakse semantilisteks tegevusteks või semantilisteks reegliteks.

Avaldises olevate identifikaatorite ja arvkonstantide väärtus saadakse juba leksilise analüüsi käigus, see on üks lekseemile vastava kirje väli spetsifikatsioon. Muudel juhtudel saadakse produktsiooni vasakul pool oleva mitteterminali väärtus paremal pool olevate mitteterminalide väärtustest. Selle sünteesitud attribuudi väärtuse saamist kirjeldavad semantikareeglid:

avaldis avaldis + avaldis
{ avaldis.val = avaldis1.val + avaldis2.val}
| avaldis - avaldis
{ avaldis.val = avaldis1.val - avaldis2.val}
| avaldis * avaldis
{ avaldis.val = avaldis1.val * avaldis2.val}
| avaldis / avaldis
{ avaldis.val = avaldis1.val / avaldis2.val}
| IDENT
{ avaldis.val = IDENT.val}
| CONST
{ avaldis.val = CONST.val}

Ülalesitatud semantilistes reeglites (produktsioonile järgnev figuursulgude {...} vahel olev osa) eristatakse mitteterminalide esinemisi reeglis sellele mitteterminalile lisatud indeksitega; esimest esinemist (reegli vasakul pool olevat esinemisest) tähistab see mittetereminal ilma indeksiteta. Reegli paremal pool olevate mitteterminalide esinemisi tähistatakse nende järjekorranumbriga (vasakult paremale lugedes) reegli paremal pool olevast terminalidest ja mitteterminalidest koostatud avaldises, seega produktsiooni avaldis avaldis + avaldis semantilistes tegevustes {avaldis.val = avaldis1.val + avaldis3.val} tähistab avaldis.val produktsiooni vasakul pool oleva mitteterminali avaldis attribuuti val ja avaldis1.val, avaldis3.val vastavalt produktsiooni paremal pool mitteterminali avaldis esimese ja teise esinemise attribuute val; terminali (lekseemi) '+' indeks on 2 .

Attribuudi val väärtus kulgeb avaldise puus alt-üles - alumisel tasemel saadud attribuudi val väärtusi kasutatakse järgmisel tasemel uute val väärtuste arvutamiseks. Selliseid "alt-üles" informatsiooni liigutavaid attribuute nimetatakse sünteesitud (synthesized) attribuutideks. Kuid mõnikord on tarvis, et informatsioon liiguks ka vastupidises suunas, ülalt alla. Vaatleme näiteks, mis peab toimuma if-then-lause transleerimisel:

Tingimusele vastavas koodiosas tuleb moodustada kaks GO TO - lauset - esimene juhuks, kui tingimus on tõene ja teine - kui tingimus on väär. See teine GO TO lause peab suunama kogu if-then lausete transleerimise järel saadud lausetele järgnevale reale. Kuid selle rea järjekorranumber ln selgub alles pärast kõigi then-osa lausete töötlemist ja selle informatsiooni (attribuudi ln väärtuse) saab tingimuse-osa GO TO - lausesse saata (kirjutada) vaid kogu if-then struktuuri kõige ülemine tipp IF, seega muutuja ln väärtus (asendatuna GOTO-ritta märgendiga n+1) peab liikuma sellest tipust allapoole. Ülalt-alla liikuvaid attribuute nimetatakse päritud attribuutideks.

Nii sünteesitud kui ka päritud attribuutide arvutamise reeglid on loomulik esitada grammatika produktsioonide juures semantiliste tegevustena. Vaatame näiteks, kuidas skanner saab juba täisarvu lugemise ajal arvutada ka loetud arvu väärtuse. Programmeerimiskeeles Ada esitatakse baasiga b (2 ≤ b ≤ 16) täisarv kujul [Märk]Baas#Numbrid#, seega korrektelt kirjutatud täisarvud oleks näiteks 3, -16#8# . Baas kirjutatakse alati kümnendsüsteemis, kuid baasi numbrite kirjutamisel võib kasutatada ka allkriipsu (see ei mõjuta arvu väärtust).

Sellise baasiga arvu lugemise ajal väärtuse arvutamiseks võib kasutada järgmisi muutujaid (mitteterminalide attribuute):

- arvu baasi b (täisarv);
- numbrite juba loetud osa ja iga numbri väärtust val (täisarv);
- loogilist muutujat neg, mis on tõene, kui arvu ees on märk - (märk võib ka puududa).

Järgnevas eeldatakse, et numbrite väärtuse (attribuudi Number.val) saab skanner C protseduuriga atoi(yytext) numbri teksti lugemisel.

Arv Märk Baas # List #
{Arv.b = Baas.b
if Märk.neg
then Arv.val = - List.val
else Arv.val = List.val} Märk + {Märk.neg = false}
| - {Märk.neg = true}
| {Märk.neg = false} Baas Number {Baas.b = Number.val}
| _ { /* ei tee midagi */}
| Baas Number {Baas.b = 10 * Baas.b + Number.val; if (Baas.b > 16) then error;} List Number {List.val = Number.val}
| List Number {List.val = List1.val * List.b + Number.val}
| List _ {List.val = List1.val} Number 0..9 {Number.val = atoi(yytext)

Attribuut b tuleb luua ja algväärtustada arvu esimese numbri lugemise järel. Kuna arv võib olla esitatud ka ilma baasita (tavaline kümnendsüsteemis kirjutatud arv), siis peab teada olema, kas esimese (kui b ≥ 10, siis esimese ja teise) numbri järel tuleb #, seega skanneril peab olema võimalik "ette vaadata" (look ahead) kaks sümbolit.

Küsimused, probleemid: ©2004 Jaak Henno