Koncepti i Implementacija Programskih Prevodilaca: Od Semantike do Optimizacije

Tabele simbola i semantička analiza

Tabele simbola su strukture podataka koje u programskim prevodiocima čuvaju informacije o simboličkim imenima koja se koriste u programu. Kako se simbolička imena mogu koristiti za imenovanje različitih tipova entiteta u programu (promenljivih, konstanti, funkcija, korisničkih tipova podataka i sl.), jasno je da su informacije koje se pamte o simboličkim imenima veoma raznorodne.

Tabele simbola se koriste u semantičkoj analizi u dve svrhe:

• Za proveru tipova podataka koji učestvuju u izrazima (type checking).
• Za proveru opsega važenja imena (scope checking).

Pojam atributnih grešaka

Da bi se proverila semantička ispravnost (ili realizovala bilo koja naredna faza prevođenja), često je potrebno da se uz simbole koji učestvuju u smenama pamte i neke dodatne informacije o njima. Dodatne informacije o simbolima se nazivaju atributi simbola, a ovakve gramatike atributne gramatike. Sintaksno stablo obogaćeno vrednostima atributa simbola se naziva obeleženo (kotirano) sintaksno stablo.

Pojam sintaksno-upravljanog prevođenja

Rutine za proveru semantičke ispravnosti, kada se pridružuju pravilima (smenama gramatike), odnosno semantičke rutine, izvršavaju se u neterminalnim čvorovima sintaksnog stabla. Generalizacija ove ideje — sintaksno-upravljano prevođenje — podrazumeva da se sve naredne faze prevođenja realizuju tako što se odgovarajuće rutine izvršavaju u čvorovima sintaksnog stabla.

Metode za predstavljanje simbola u tabeli simbola

Zajednička karakteristika svih tipova entiteta koji se imenuju su ime i tip kojem pripadaju. Simboli se predstavljaju složenim tipovima podataka koji imaju strukturu grafa. U tim grafovima koriste se dva osnovna tipa čvorova:

• Type nodes (ili structure nodes) – čvorovi kojima se predstavljaju tipovi.
• Object nodes – čvorovi kojima se predstavljaju imenovani entiteti u programu.

S obzirom na raznorodnost podataka koji se o entitetima i tipovima pamte u tabeli simbola, postoje dva osnovna pristupa za implementaciju ova dva tipa čvora:

1. Flat pristup: Jedinstvena struktura podataka sadrži sve podatke koji se mogu pamtiti o svim mogućim vrstama entiteta (odnosno tipova).
2. Objektno-orijentisani pristup: U apstraktnoj klasi se pamti ono što je zajedničko za sve vrste entiteta (tipova), a u konkretizovanim izvedenim klasama ono što je karakteristično za konkretne vrste entiteta/tipova.

Metode za realizaciju sintaksno-upravljanog prevođenja

Koriste se dve metode:

• Jednoprolazni prevodioci: Svi atributi su istog tipa, prilagođeni algoritmu sintaksne analize. Kod top-down algoritama se koriste nasleđeni, a kod bottom-up generisani atributi.
• Višeprolazni prevodioci: Mogu da budu definisani i nasleđeni i generisani atributi. U prvom prolazu se generiše samo sintaksno stablo, koje se potom obilazi više puta, pri čemu se prilikom svakog obilaska izračunavaju novi atributi.

Šta se podrazumeva pod pojmom „obeleženo (notirano) sintaksno stablo“? Sintaksno stablo obogaćeno vrednostima atributa simbola se naziva obeleženo sintaksno stablo.

Strukture podataka za implementaciju tabele simbola

Za predstavljanje tabele simbola mora se koristiti neka od dinamičkih struktura podataka. Najčešće korišćene su:

1. Lančane liste

• Traženje simbola: Sporo.
• Dodavanje novih simbola: Jako brzo.
• Brisanje simbola: Brzo.

2. Uređena binarna stabla

• Traženje simbola: Brže nego u slučaju lančane liste.
• Dodavanje simbola: Sporije.
• Brisanje simbola: Jako sporo.
• Utrošak memorije: Veći nego kod lančane liste.

3. Hash tabele (Rasute tabele)

• Traženje simbola: Izuzetno brzo.
• Dodavanje simbola: Takođe brzo.
• Brisanje simbola: Sporo.
• Utrošak memorije: Veći nego kod lančane liste jer u hash tabeli uvek ostaje dosta nepopunjenih polja.

Pojam atributnih grešaka (ponovljeno)

Da bi se proverila semantička ispravnost, često je potrebno da se uz simbole pamte dodatne informacije (atributi). Gramatike sa ovim svojstvom su atributne gramatike, a stablo je obeleženo (kotirano) sintaksno stablo.

Implementacija za jezike sa ugnježdenim opsezima važenja

Postoje dva pristupa:

• Svi simboli se smeštaju u jedinstvenu tabelu simbola, pri čemu se uz svaki simbol pamti i nivo opsega na kojem je definisan. Po zatvaranju bloka, iz tabele se brišu svi simboli definisani u njemu.
• Za svaki opseg važenja imena pravi se posebna tabela simbola i one se smeštaju na stek. Po zatvaranju bloka, iz steka se izbacuje tabela koja odgovara tom opsegu.

Problemi kod posebnih tabela po opsegu:

• Pristup imenu van tekućeg opsega usporava traženje (pretražuje se više tabela).
• Kod hash tabela dolazi do rasipanja prostora ako je broj imena u opsegu mali, pa se tada često koriste lančane liste.

Type Checker i provera tipova

Type checker je najbitnija komponenta semantičkog analizatora. On proverava da li su broj operanada i njihovi tipovi u izrazima odgovarajući. Tip definiše opseg vrednosti podataka i skup operacija nad njima. Tipove imaju: promenljive, konstante, funkcije i izrazi. Postoje ugrađeni i korisnički definisani tipovi.

Provera tipova u aritmetičkim izrazima: Koristeći atributne gramatike, proverava se da li su učesnici u izrazu kompatibilni po tipu podataka.

Vrste atributa u atributnim gramatikama

Vrednosti atributa se određuju semantičkim rutinama pridruženim produkcionim pravilima. Na osnovu propagacije, dele se na:

• Generisani (Sintetizovani) atributi: Vrednosti terminalnih simbola određuje leksički analizator. Vrednosti neterminalnih simbola se izračunavaju kao funkcije atributa dece u stablu. Propagiraju se odozdo naviše.

Za pravila oblika: X → Y1 Y2 . . . Yn, semantičke rutine su: X.a = f(Y1.a, Y2.a, . . . , Yn.a).

• Nasleđeni atributi: Vrednosti se izračunavaju kao funkcije atributa roditeljskog čvora i atributa simbola na istom nivou levo od posmatranog simbola. Propagiraju se odozgo naniže.

Pravila oblika: X → Y1, Y2, . . . , Yn, semantičke rutine su: Yk.a = f(X.a, Y1.a, ..., Yk-1.a, Yk+1.a, ..., Yn.a).

Semantičke rutine i međukodovi

Pojam semantičke rutine: Simbolima gramatike se dodaju atributi čije se vrednosti računaju preko semantičkih rutina. Postoje dva načina pridruživanja:

• Sintaksno upravljane definicije: Definicije rutina na visokom nivou, bez detalja o redosledu primene.
• Translacione šeme: Pokazuju tačan redosled primene pravila, što je bliže samoj implementaciji.

Zašto se uvode međukodovi?

• Prenosivost koda: Generisanje koda za različite ciljne mašine na osnovu istog međukoda.
• Optimizacija koda: Mašinski nezavisna optimizacija na nivou međukoda.

Vrste međukodova

• Visokog nivoa: Apstraktno sintaksno stablo (AST), poljska inverzna notacija.
• Niskog nivoa: Pseudo-asemblerski jezici, troadresni međukod.

Razlika između sintaksnog stabla i AST-a: Sintaksno stablo prikazuje ceo postupak izvođenja reči, dok je AST redukovana reprezentacija koja se generiše direktno ili transformacijom sintaksnog stabla.

Memorisanje AST-a: Može biti statičko ili dinamičko. Mogu se koristiti procedure za redukciju (da se ne generišu dupli čvorovi), čime se dobija struktura usmerenog acikličnog grafa (DAG).

Troadresni međukod

Troadresni međukod se može memorisati pomoću:

• Quadruples (četvorke): Slogovi sa četiri polja: operator (op), arg1, arg2 i rezultat (rez).
• Triples (trojke): Slogovi sa tri polja. Rezultat se ne čuva eksplicitno, već se na njega ukazuje preko pozicije sloga.
• Indirect triples: Dodatna lista pokazivača na triples slogove, pogodno za optimizaciju (preuređivanje naredbi bez menjanja osnovne strukture).

Naredbe troadresnog koda

Sastoji se od jednostavnih instrukcija sa najviše jednim operatorom. Primer: x + y * z postaje t1 = y * z; t2 = t1 + x.

Osnovne naredbe uključuju: dodeljivanje (x := y op z), kopiranje (x := y), labele (L:), skokove (goto L, if x relop y goto L), pozive potprograma (param x, call p, n) i rad sa poljima (x := y[i]).

Direktna redukcija

Zamena složenih operacija jednostavnijima:

• Stepenovanje (X²) → množenje (X * X).
• Množenje/deljenje stepenom dvojke → shift operacije.
• Deljenje konstantom → množenje recipročnom vrednošću.

Optimizacija koda

Osnovna (peephole) optimizacija: Vrši se lokalno nad malom grupom naredbi („prozor“). Transformacije uključuju:

• Eliminisanje redundantnih naredbi (npr. izbacivanje uzastopnih Store i Load istog registra).
• Optimizacija toka programa.
• Algebarska uprošćenja.
• Korišćenje mašinskih idioma (specifične instrukcije procesora, autoinkrementiranje, korišćenje steka).

Graf toka upravljanja

Kod se deli na osnovne blokove (čvorove grafa) gde se naredbe izvršavaju sekvencijalno. Grane predstavljaju skokove. Koristi se za identifikaciju celina koda pre optimizacije.

Optimizacija petlji

• Migracija koda (code motion): Izbacivanje izraza čija se vrednost ne menja unutar petlje van nje.
• Eliminacija indukcionih promenljivih: Ako promena jedne promenljive direktno zavisi od druge (npr. brojač petlje), kod se može uprostiti.
• Direktna redukcija u petljama: Zamena „skupljih“ operacija „jeftinijim“ (npr. množenje sabiranjem).

Upravljanje memorijom u toku izvršenja

Zadaci komponente za upravljanje memorijom:

• Organizacija memorije (kod, podaci, klase memorije).
• Pristup podacima u različitim zonama.
• Upravljanje memorijom pri pozivu i povratku iz potprograma.

Strategije alokacije

1. Statička alokacija: Sadržaj se ne menja tokom izvršenja. Ne podržava rekurziju jer svaki potprogram ima samo jedan fiksni aktivacioni slog.
2. Dinamička alokacija (Heap): Koristi se kod dinamičkih jezika. Podaci i aktivacioni slogovi ostaju na heap-u dok ih garbage collector ne ukloni.
3. Polustatička (Stek) alokacija: Memorija se deli na statičku zonu (kod, globalni podaci) i dinamičku (Stack za aktivacione slogove i Heap za objekte). Podržava rekurziju.

Aktivacioni slog

Za svaki poziv potprograma generiše se aktivacioni slog koji sadrži:

• Rezultat koji se vraća.
• Stvarne parametre.
• Upravljačke linkove (veza sa pozivajućim modulom).
• Linkove za pristup nelokalnim podacima.
• Status procesora (registri, brojač naredbi).
• Lokalne podatke potprograma.
• Privremene podatke (međurezultati).

Prevođenje poziva i povratka

Sekvenca poziva: Skup instrukcija za rezervaciju prostora, smeštanje parametara na stek, čuvanje konteksta procesora (registri AX, BX, itd.) i promenu baznog pokazivača (BP).

Sekvenca povratka: Upis rezultata, oslobađanje prostora za lokalne promenljive, vraćanje konteksta procesora, vraćanje starog BP-a i povratak (RET) u pozivajući modul.