Pisi-Algoli transleerimisskeem

Järgnevas on ühendatud varemesitatud semantilised tegevused veidi suuremaks näiteks, mis sisaldab ka Pisi-Algoli suunamised; välja on jäänud vaid sisend-väljundlaused, sest nende transleerimisskeem sõltub operatsioonisüsteemist. Siin kasutatakse eelnevas esitatud protseduure out, BACK ja MERGE. Allpooolesitatud abstraktse süntaksi grammatikas esinevad terminalid (võtmesõnad, omistamismärk, tehtemärgid) on vaid esituse lihtsustamiseks, nendega ei ole seotud mingeid semantilisi tegevusi ja abstraktse süntaksi puus nad tegelikult enam ei esine (neid kasutati varem, süntaksipuu konstrueerimisel); mitteterminali m kasutatakse vaid jooksva märgendi (globaalne muutuja!) ln väärtuse säilitamiseks; globaalset muutujat N kasutatakse nagu varemgi uute identifikaatorite genereerimisel. Nagu varemgi lisab uue käsu genereerija  out  alati  käsu ette märgendi,  mis saadakse muutujast  ln ; muutuja ln väärtus  suureneb pärast seda automaatselt.

programm lause | programm lause
{ programm.N = ln}
lause  omistamine | tingimuslause | while_lause
omistamine   Ident := avaldis
{out( Ident.P || ":=" || avaldis.P )}
tingimuslause  IF tingimus THEN m programm ENDIF
{BACK(tingimus.T, m.Q);
BACK(tingimus.F, programm.N)
}
while_lause  WHILE tingimus DO m programm ENDLOOP
{out("GOTO" || tingimus.Q;);
BACK(tingimus.T, m.Q);
BACK(tingimus.F, (programm.N)+1)
}
tingimus  m loogiline
{tingimus.Q = m.Q
tingimus.T = loogiline.T
tingimus.F = loogiline.F
}
| loogiline OR m loogiline
{BACK(loogiline1.F, m.Q)
tingimus.T := MERGE(loogiline1.T, loogiline2.T)
tingimus.F := loogiline2.F
}
| loogiline AND m loogiline
{BACK(loogiline1.T, m.Q)
tingimus.F := MERGE(loogiline1.F, loogiline2.F)
tingimus.T := loogiline2.T
}
| NOT loogiline
{tingimus.T = loogiline.F

tingimus.F = loogiline.T
}
loogiline   avaldis relop avaldis
{loogiline.T := ln;
loogiline.F := ln+1;
out("IF" !! avaldis1.P !! relop !! avaldis2.P !! "GOTO" _ );
out("GOTO" _);
}
 m 
{ m.Q := ln; }
avaldis  avaldis op avaldis
{ avaldis.P = "T" !! N ; /* genereeritakse uus tähistus */
out( avaldis.P !! ":=" !! avaldis1.P !! op !! avaldis2.P)
}
avaldis  op avaldis /* unaarne operatsioon, näit miinus */
{ avaldis.P = "T" !! N ; /* genereeritakse uus tähistus */
out( avaldis.P !! ":=" !! op !! avaldis1.P)
}
avaldis  Ident
{ avaldis.P = Ident.P }
avaldis  Const
{ avaldis.P = Const.P }

See skeem esitab olulisemate imperatiivsetes programeerimiskeeltes kasutatavate juhtimisskeemide transleerimise ideed. Täieliku, töötava translaatori saamiseks jääb veel veidi teha: nimede tabel(tabelid) peavad vastama lähtekeele moodulite süsteemile (lokaalsete ja globaalsete muutujate nähtavuse, skoobi probleemid), mälukasutus tuleb optimiseerida - kui lokaalset muutujat (näiteks tsükliloendajat) enam ei vajata, tuleb vastav mäluosa vabastada (garbage collection) jne jne.

Translaatori "tagumist otsa" (back end), s.t. väljundkoodi genereerimist, mälujaotust ja mitmesuguseid translaatori töökiiruse ja mälu kasutamise optimiseerimise probleeme siin ei käsitleta. Töökiiruse tõstmiseks on enamuses protsessorites oma, sisemine mälu ja registrid, kuhu salvestamine ja salvestatud väärtuste kättesaamine toimub väga kiiresti. Registrite ja mitmesuguste vahemälude optimaalseks kasutamiseks on väga oluline masinkoodi käskude täitmise järjekord: kui äsja arvutatud väärtust on varsti vaja, pole mõtet hakata seda saatma põhimälusse, vaid muuta genereeritud käskude järjekorda nii, et seda kasutataks niipea kui võimalik (seda on lihtne teha näiteks +=, -=, ++ jt. analoogiliste operatsioonide transleerimisel). Registrite optimaalne kasutamine (instruction allocation, register scheduling) on NP-keerulised probleemid (eriti paralleeltööga programmeerimiskeelte translaatorites), kuid nende uurimine ja lahtiharutamine kuulub pigem üldise programmeerimistehnoloogia alasse ja sellepärast neid siin ei käsitleda.


Ülesandeid:
1. Mis genereeritakse käskude

X := 10
Y := 20
WHILE X + Y > 2 * X DO
IF X < 25 THEN X := X + Y / 5 ENDIF
Y := Y - 1
ENDDO
Z := X + Y

transleerimisel?

2. Lisa eelnevale ka until-tüüpi tsükli transleerimise skeem; käsu süntaks võiks olla

until_lause DO m programm UNTIL tingimus ENDLOOP

3. Lisa eelnevale ka määratud arvu kordustega tsükli transleerimise skeem; käsu süntaks võiks olla

for_lause FOR algväärtustamine UNTIL lõppväärtus DO m programm ENDLOOP
algväärtustamine omistamine
lõppväärtus Const

4. Täienda Pisi-Algoli süntaksit nii, et programmi tekstis saaks kasutada ka reakommentaare (eraldajaks // - edasi kuni rea lõpuni on kommentaar ) ja blokikommentaare (eraldajate /* */ vahel)

5. Lisa Pisi-Algolile case-lause, nii et see võtaks vastu näiteks sellise näite (Ruby case-lause süntaks, kõik when-osad on avaldised):

case Inflation
when < 1: 
	dont_worry
	be_happy
when 1..2:
	start_thinking
when 2..4:
	sack_government
	change_to_euro
when >4:
	move_abroad
else          
	 'only single-digit numbers are allowed'
end

Küsimused, probleemid: ©2004-2013 Jaak Henno