Automaadid, keeled ja translaatorid 2017/18 kevad

11. praktikum: semantiline analüüs

Taust

Parser üldjuhul ei suuda anda kogu huvipakkuvat informatsiooni programmi kohta. Seetõttu tuleb süntaksipuud enamasti veel analüüsida ja töödelda. Seda faasi nimetatakse semantiliseks analüüsiks. Üks tavaline semantilise analüüsi ülesanne on muutujate deklaratsioonide ja nende kasutamiste seostamine.

Näited huvipakkuvatest olukordadest

Sama nimega erinevad muutujad

var x = inputInt();

if x % 2 == 0 then {
    printInt(x)
} else {
    var x = 1;
    printInt(x)
};

printInt(x)

Defineerimata muutuja kasutamine

var x = inputInt();

if x % 2 == 0 then {
    var y = 0;
    printInt(x)
} else {
    var y = 1;
    printInt(y)
};

printInt(y)

Samas skoobis muutuja mitmekordne deklareerimine

var x = inputInt();
var x = 34;
printInt(x)

Mõisted

Muutuja (variable)

Sõna 'muutuja' kasutatakse kahes tähenduses:

1. programmi tekstist rääkides mõeldakse selle all tavaliselt ühte süntaktilist konstruktsiooni, mis koosneb mingist nimest ja on harilikult avaldise alamliik, nt. x. Kui tahetakse seda tähendust rõhutada, siis öeldakse muutuja viide või viide muutujale;
2. programmi jooksutamisest rääkides mõeldakse selle all tavaliselt mingit nimega väärtust või mälukohta.

Need tähendused on seotud: muutuja esimes tähenduses (e. muutuja viide) tähistab mingit muutujat teises tähenduses (e. nimega väärtust või mälukohta).

NB! Muutuja ei pea olema tingimata muudetav (SML, Haskell, matemaatika), tähtis on see, et muutuja kasutamisel me (harilikult) ei tea, millise konkreetse väärtusega see programmi käivitamisel seotud on.

Vabad vs. seotud muutujad (free vs. bound variables)

Termineid vaba vs. seotud muutuja kasutatakse harilikult koodilõikude kohta. Muutuja on vaba, kui näidatud koodis ei ole muutuja definitsiooni või olemuse kohta mingit infot, vastasel juhul on muutuja seotud. Näiteks avaldises print(x + 1) on muutuja x vaba, aga programmilõigus var x = 10; print(x + 1) on seotud.

Sama terminoloogiat kasutatakse ka matemaatikas. Vaatame järgmist predikaatarvutuse valemit:

 ∀x.∀y.x&y∨z

Siin on muutujad x ja y seotud, aga muutuja z on vaba.

Veel üks näide (http://en.wikipedia.org/wiki/Free_variables_and_bound_variables):

Siin on muutuja n vaba ja muutuja k on seotud.

Nimede sidumine (name binding)

Muutujate kasutamise teeb keerulisemaks see, et enamik programmeerimiskeeli lubab kasutada sama nime erinevate muutujate tähistamiseks. Protsessi, mis paneb nimede esinemised vastavusse õigete muutujatega, nimetatakse nimede sidumiseks. Erinevates keeltes on selle jaoks erinevad reeglid. Iga programmeerija peab pidevalt seda protsessi enda peas käivitama, et programmist õigesti aru saada.

Skoop (scope)

Ka sõna 'skoop' kasutatakse mitmes pisut erinevas tähenduses

1. skoop võib tähendada mingit koodi piirkonda; näiteks globaalseks skoobiks nimetatakse harilikult tervet programmi (või moodulit), funktsiooni keha nimetatakse lokaalseks skoobiks, siit on ka näha, et mingi osa programmist võib korraga kuuluda mitmesse skoopi;
2. muutuja skoop on see osa programmi koodist, kus konkreetne muutuja (kui nimega väärtus või mälukoht) on nähtav/viidatav;
3. kui muutuja on mingis programmi kohas nähtav, siis öeldakse, et see muutuja on antud kohas skoobis.

Näide

x = 123

def blah(y):
    x = 10
    print(y*x)

z = "tere"
print(z)

Proovime selle näite põhjal kasutada sõna 'skoop' kolmel viisil:

1. globaalne skoop on read 1-8, funktsiooni blah lokaalne skoop on read 4-5;
2. globaalse muutuja x skoop on read 2,3,6,7,8, globaalse z skoop on rida 8, lokaalse x skoop on rida 5 ja lokaalse muutuja y skoop on read 4 ja 5;
3. real 5 on lokaalne muutuja y skoobis, aga real 8 ei ole.

Nimeruum (namespace)

Kui skoop on programmi koodi kohta käiv termin, siis nimeruum on programmi käivitamise kohta käiv termin.

Nimeruum on kujutus, mis seab mingile nimele vastavusse mingi muutuja, seega Javas mingi keele interpretaatorit kirjutades võiks nimeruumi esitada objektiga, mille tüüp on Map<String, Muutuja> või Map<String, Väärtus>.

Klassikaliselt luuakse programmi käivitamisel kõigepealt globaalne nimeruum, milles hoitakse globaalseid muutujaid ja mis eksisteerib programmi sulgemiseni. Iga funktsiooni väljakutsel luuakse ajutine lokaalne nimeruum, mis hoiab lokaalseid muutujaid ja mis kaob funktsiooni töö lõppemisel.

Mõnedes keeltes (nagu näiteks C, Java või AKTK) moodustatakse eraldi nimeruum ka iga ploki jaoks:

void blah() {
     if (...) {
          int x = 1;
          ...
     } else {
          int x = 2;
          ...
     }

}

Konkreetse programmeerimiskeele reeglid määravad, millisest nimeruumi(de)st tuleb väärtust otsida, kui interpretaator peab väärtustama mingi muutujaviite. Enamasti korraldatakse asi nii, et iga programmipunkti jaoks on teada järjestatud nimeruumide ahel (nt. sisemise ploki, välise ploki, funktsiooni ja lõpuks globaalne nimeruum), kust muutuja väärtust otsitakse.

Skoop vs. nimeruum

Mõisted 'nimeruum' ja 'skoop' on omavahel seotud -- skoop on koodi piirkond, mille jaoks programmi käivitamisel tekitatakse oma nimeruum.