Attribuutide kasutamine koodi genereerimisel

Olgu .C (Code) tekstilise väärtusega attribuut, millesse salvestatakse vastavale mitteterminalile vastav väljundkoodi lõik; .P on lekseemide Ident ja Const korral attribuudud, mis algväärtustatakse juba skaneerimisel ja milles on vastavalt viit identifikaatorile nimede tabelis ja konstandil - selle väärtus, s.t. vastav arv; mitteterminali avaldis attribuut P on selle (alam)avaldisele jaoks genereeritud (seda alamavaldist tähistav) muutuja. Need translaatori poolt genereeritud muutujad on siin kõik kujul T1, T2 jne (translaatori poolt genereeritud muutujad ei või segi minna programmis esinevatega, sellepärast on "päris" translaatoris ajutiste muutujate nimed palju keerulisemad, näiteks _@T1, _@T2,...). Numbrilise indeksi saamiseks genereeritud muutujatele kasutatakse globaalmuutujat N, mille väärtus suureneb ühe võrra iga selle kasutamise järel; muutuja N algväärtustamist ja muutmist siin ei vaadelda. Lihtsustamiseks eeldatakse, et lähte- ja objektkoodi aritmeetiliste operatsioonide tähistused on samad, s.t. näiteks "+" tähistab mõlemas liitmist jne.

Lihtsa omistuslausele vastav väljundkoodi genereerimise võib siis kirjeldada järgmiste semantiliste tegevustega (siin || on stringide kokkukirjutamine (konkatenatsioon), sellist tähistust kasutatakse näiteks programmeerimiskeeles PL-1):

omistuskäsk nool Ident := avaldis
{ omistuskäsk.C = avaldis.C || Ident.P || ":=" || avaldis.P}

s.t. avaldise arvutamise koodi lõppu lisatakse käsk: Ident.P := avaldis.P, kus Ident.P on identifikaator (s.t. selle nimekuju), avaldis.P - avaldise väärtust salvestav abimuutuja

avaldis nool avaldis op avaldis
{ avaldis.P = "T" || N ; /* genereeritakse uus tähistus */
avaldis.C = avaldis1.C || avaldis2.C || avaldis.P || ":=" || avaldis1.P || op || avaldis2.P }
avaldis nool op avaldis /* unaarne operatsioon, näit miinus */
{ avaldis.P = "T" || N ; /* genereeritakse uus tähistus */
avaldis.C = avaldis1.C || avaldis.P || ":=" || op || avaldis1.P }
avaldis nool Ident
{ avaldis.P = Ident.P } avaldis nool Const
{ avaldis.P = Const.P } op  nool + | - | * | /

puu3Selliste süntaktiliste tegevustega saadakse näiteks omistuskäsu attribuudi .C väärtuseks käsu A := -B * (C+D) abstrakse süntaksi (kirjeldatud ülalesitatud grammatikaga) läbimisel programmilõik (muutuja N algväärtus on 1)

T1 := -B
T2 := C + D
T3 := T1 * T2
A := T3

Ajutiste muutujate kasutamisega avaldise transleerimisel on seotud palju optimiseerimisprobleeme: tegelikult vajatakse neid ju ainult vastava alamavaldise arvutamiseks, pärast seda on nad kasutud ja ainult reostavad nimede tabelit ja isegi suhteliselt väga lihtsate avaldiste korral saab transleeritud koodi optimiseerida. Näiteks täisnurkse kolmnurga hüpotenuusi arvutamise käsu c = sqrt(a*a + b*b) transleerimine ülalesitatud skeemiga annaks tulemuseks

T1 := a
T2 := T1 * T1
T3 := b
T4 := T3 * T3
T5 := T2 + T4
T6 := sqrt(T5)
c := T6


Kuid see kuue abimuutujaga kood on samaväärne järgmise vaid kaht abimuutujat kasutava koodiga:

T1 := a
T1 := T1 * T1
T2 := b
T2 := T2 * T2
T2 := T2 + T1
T2 := sqrt(T2)
c := T2

Ka seda saaks (sõltuvalt objektkeele täimise keskkonnast ja järgnevatest/eelnevatest programmiridadest) veel optimiseerida. Kui seda koodi täidetakse näiteks C-s ja muutujaid a, b rohkem ei kasutata, võivad omistamised T1 := a, T2 := b olla ülearused, kiirem oleks kohe T1 := a * a, T2 := b * b . Kuid kui suurusi a, b vajatakse veel mõnes järgnevas käsus ja T1, T2 on protsessori (kiired) registrid, võivad omistamised T1 := a, T2 := b (ja nende väärtuste säilitamine, s.t. T1 := T1 * T1 asemel T3 := T1 * T1 ) olla väga otstarbekad. Ka täiesti uute muutujate (nimede) genereerimine uue alamavaldise jaoks on täielik resursside (mälu, nimede tabel) raiskamine - uue muutuja vajaduse korral peaks translaator leidma juba genereeritud muutujate seas sellise, mida enam ei vajata ja kasutama seda. Optimaalne ajutiste muutujate kasutamine ja nende mälukasutuse projekteerimine on NP-täielik probleem.


Ülesandeid:
1. Kuidas peaks täiendama ülaltoodud skeemi, kui soovitakse lisada produktsioonid käskude jada transleerimiseks:

käsud nool käsk | käsk; käsud
käsk nool omistuskäsk

2. Kuidas peaks täiendama eeltoodud skeemi, kui objektkeeles (keeles, millesse transleeritakse) ei ole binaarsed operatsioonid samad, vaid nende esimene (vasakpoolne) operand peab alati olema üks ja sama fikseeritud muutuja (register) ja operatsiooni tulemus salvestatakse taas samas muutujas, seega näiteks sisendtekst

C := A + B

peaks teisenema selliseks (fikseeritud muutuja on R):

R := A
R += B /* s.t. R := R+B */
C := R

Objektkeeles kasutatakse peale omistamise := ka C-keelest tuntud operatsioon+omistamine operaatoreid +=, -=, *=, /= .

Küsimused, probleemid: ©2004 Jaak Henno