Automaadid, keeled ja translaatorid

9. kodutöö: AKTK semantiline analüüs

See kodutöö keskendub AKTK programmide (täpsemalt AST-i) semantilisele analüüsile ja koosneb kahest võrdse kaaluga osast:

1. Nimede sidumine
2. Tüübikontroll

Nimede sidumine

Selleks on tehtud täiendused AST klassidesse, et salvestada muutujate ja funktsioonide kohta lisainfot.

Implementeeri meetod bind klassis AktkBinding:

package week9;

import week7.ast.*;

public class AktkBinding {
    /**
     * Määra iga antud programmis olevale muutujaviitele (week7.ast.Variable)
     * teda siduv element (week7.ast.VariableBinding,
     * st week7.ast.VariableDeclaration või week7.ast.FunctionParameter)
     * Kasuta selleks meetodit week7.ast.Variable#setBinding.
     *
     * Kui muutuja kasutusele ei vasta ühtegi deklaratsiooni ega parameetrit,
     * siis jäta binding määramata.
     */
    public static void bind(AstNode node) {
        throw new UnsupportedOperationException();
    }
}

Vihjed

• Skoobis olevate muutujate jälgimiseks sobib sarnane andmestruktuur nagu interpretaatoris nimeruumide jaoks, aga konkreetsete väärtuste asemel tuleb salvestada midagi muud.
• Kui AST-i läbimisel pole vaja midagi tagastada, siis AstVisitor<Void> vms asemel on mugavam implementeerida hoopis analoogiline abiliides AstVisitor.VoidVisitor.

1. tase: muutujate sidumine funktsioonidest väljaspool

Esiteks peab AktkBinding töötama programmidega, milles pole funktsioonide definitsioone. Sel juhul tuleb iga Variable jaoks määrata vastav VariableDeclaration kasutades meetodit setBinding.

Näited mittekorrektsetest muutujate kasutustest

Defineerimata muutuja kasutamine

var x = y + 1

Plokimuutuja kasutamine plokist väljaspool

var x = readInt();

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

printInt(y) 

Näited korrektsetest muutujate kasutustest

Sama nimega erinevad muutujad erinevates plokkides

var x = readInt();

if x / 2 == 0 then {
    var d = 1;
    printInt(x + 1)
} else {
    var d = 2;
    printInt(x * d)
}

Sama nimega erinevad muutujad üksteise sees olevates skoopides (nt. Java seda ei luba)

var x = readInt();

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

printInt(x)

Enne plokimuutuja deklareerimist on nähtav välises skoobis olev muutuja

var x = 1;

if x / 2 == 0 then {
    printInt(x); /* kuvab ekraanile 1 */
    var x = 2;   /* siit edasi, kuni ploki lõpuni tähendab x plokimuutujat */
    printInt(x)  /* kuvab ekraanile 2 */
} else {
    pass()
};

printInt(x) /* kuvab ekraanile 1 */

2. tase: muutujate sidumine funktsioonide sees

Teiseks peab arvestama sellega, et osad funktsioonide kehades olevad muutujad ei ole deklareeritud mitte muutujadeklaratsiooniga, vaid funktsiooni parameetriga.

Näited

var x = 45;

fun printDouble(x:Integer) {
    print(x);
    print(x)
}

Siin tuleb print-väljakutse argumentides olevad x-id siduda funktsiooni parameetriga (week7.ast.FunctionParameter), kuigi välimisel tasemel on ka sama nimega muutuja deklaratsioon.

Kui aga programm on selline:

var x = 45;

fun printDouble(y:Integer) {
    print(x);
    print(x)
}

siis tuleb x-id siduda programmi esimesel real oleva muutuja deklaratsiooniga.

3. tase: muud kasulikud sidumised

Kolmandaks peaks teostama veel mõningaid spetsiifilisemaid sidumisi, mis on hiljem kasulikud:

1. Omistuslause (Assignment) tuleb siduda omistatava muutuja deklaratsiooniga/funktsiooni parameetriga kasutades meetodit setBinding. Eelnevalt sidusime ainult avaldistes esinevaid muututjaid (Variable), aga omistatav muutuja pole avaldis, seega seda on vaja veel eraldi käsitleda.
2. Funktsioonikutse (FunctionCall) tuleb siduda kutsutava funktsiooni definitsiooniga kasutades meetodit setFunctionBinding. Seda saab teha vaid AKTK funktsioonide jaoks; operaatorite ja sisseehitatud funktsioonide korral jätame selle puuduvaks (null).
3. Tagastuslause (ReturnStatement) tuleb siduda funktsiooni definitsiooniga, millest tagastatakse, kasutades meetodit setFunctionBinding. Siin pole rangelt võttes enam tegemist nimede sidumisega, kuid sellegipoolest on siin ka see sidumine teostada.

Tüübikontroll

AKTK grammatikasse ja AST-i lisasime algul juba võimaluse kirjutada muutujate ja funktsioonide tüüpe, kuid interpretaatori juures me neid ei vajanud. Nüüd aga küll, sest tahame neid kontrollida.

Implementeeri meetod check klassis AktkTypeChecker:

package week9;

import week7.ast.*;

public class AktkTypeChecker {

    public static void check(AstNode ast) {
        // Meetod peab viskama RuntimeException-i (või mõne selle alamklassi erindi), kui:
        // 1) programmis kasutatakse deklareerimata muutujaid või funktsioone,
        // mida pole defineeritud ei antud programmis ega "standardteegis"
        //    (vt. interpretaatori koduülesannet)
        // 2) programmis kasutatakse mõnd lihttüüpi, mis pole ei String ega Integer
        // 3) leidub muutuja deklaratsioon, milles pole antud ei tüüpi ega algväärtusavaldist
        // 4) programmis on mõnel avaldisel vale tüüp
        throw new UnsupportedOperationException();
    }
}

Skoopimise reeglid

Muutujate deklaratsioonide (VariableDeclaration/FunctionParameter) ja kasutuskohtade (Assignment ja Variable) seosed on määratud täpselt nii nagu ülal nimede sidumise juures. Esimeses osas kõigi sidumiste mõte oligi see, et neid hiljem maksimaalselt ära kasutada. Kui enne tüüpide kontrollimist nimede sidumine ära teha, siis tüübikontrolli juures ei pea skoopidest isegi mõtlema ega mingi andmestruktuuriga jälgima!

Tüübireeglid

• Toetatavad tüübid on Integer ja String.
  • Teiste nimedega tüüpide puhul tuleb visata erind.
• Aritmeetilisi operatsioone (+,-,*,/,%) lubame teha Integer-iga.
  • Seal hulgas unaarset miinust.
  • Plussi võib lisaks arvudele kasutada ka kahe String argumendiga (tulemuseks on String).
• Võrdlusoperatsioone saab teha Integer ja String-iga, kusjuures mõlemad operandid peavad olema sama tüüpi. Tulemuseks on alati Integer.
• Muutuja deklaratsioonides:
  • Ilma algväärtusavaldiseta deklaratsioonides (nt. var x) peab olema määratud ka tüüp (nt. var x: Integer).
  • Algväärtusega deklaratsioonis ei ole tüübi määramine kohustuslik:
    • Tüübi ärajätmisel (nt. var s = "tere!") määratakse muutuja tüüp avaldise tüübi järgi. Seejuures võib olla kasulik tuletatud tüüp muutuja deklaratsioonis salvestada, kasutades selleks setType meetodit.
    • Kui on antud nii tüüp kui ka algväärtusavaldis (nt. var s : String = "tere!"), siis tuleb kontrollida, et antud tüüp ja avaldise tüüp klapivad.
• Muutuja tüüp on fikseeritud, st. talle ei saa hiljem enam teist tüüpi väärtust omistada.
• If- ja while- lausete tingimuses oleva avaldise tüüp peab olema Integer.
• Kontrollida tuleb nii AKTK-s esinevate funktsioonide kui ka sisseehitatud funktsioonide väljakutsete korrektset kasutamist, st. argumentide arvu, nende tüüpe ja tagastustüüpi.
  • Pane tähele, et võib olla funktsioone, mis väärtust üldse ei tagastagi (sisseehitatult void, AKTK-s pole noolega -> tagastustüüpi antud).
  • Funktsiooni definitsioonis esineva tagastuslause avaldis peab olema seda tüüpi, mis definitsioonis tagastustüübiks oli märgitud.

Video juhuks, kui jääd alustamisega hätta: AktkBinding-u ja AktkTypeChecker-i algus.