Programski prevodioci

Cilj i ishod predmeta

Upoznavanje studenata sa problemima prevođenja sa jednog programskog jezika na drugi, principima rada programskih prevodilaca, alatima za njihovo pravljenje i načinom njihove implementacije. Razumevanje programskog prevodioca kao jednog od ključnih alata u pravljenju programa. Mogućnost uključivanja u pravljenje programskog prevodioca.

Teorijska nastava

Nastanak viših programskih jezika i programskih prevodilaca. Klasifikacija kompajlera. Evaluacija kompajlera. Aktuelni izazovi pred razvojem kompajlera. Kompajlerske infrastrukture (GCC, LLVM). Teorija formalnih jezika (gramatike, hijerarhija Čomskog). Leksička analiza (osnovni algoritam skeniranja, osnovne dileme, regularni izrazi, nedeterministički i deterministički konačni automati, tabelarna implementacija konačnih automata, Lex). Semantička analiza (konteksno slobodne gramatike, višesmislenost i prevazilaženje, pristupi obradi greške u parsiranju, apstraktno sintaksno stablo, rekurzivno silazno parsiranje, leva rekurzija i prevazilaženje, prediktivno parsiranje, LL1 tabela, uzlazno parsiranje, Yacc). Semantička analiza (opseg, tabela simbola, okruženje tipa, tip metode, statička i dinamička kontrola tipa). Generisanje koda (organizacija izvršavanja, aktivacioni zapis, alociranje, poravnanje, stek mašina, arhitektura MIPS). Osnovi optimizacije koda (pravila evaluacije, međukod, bazični blok, graf kontrole toka, lokalna i globalna optimizacija).

Praktična nastava

Parsiranje stringa u jeziku C i u jeziku Python. Regularni jezici, vežba pisanja regularnih jezika. Početak pisanja jednostavnog interpretera za jezik C u jeziku Python. Leksička analiza i prepoznavanje tokena. Implementacija konačnog automata za konkretnu kontekstno nezavisnu gramatiku. Parsiranje matematičkih izraza upotrebom odgovarajuće kontekstno nezavisne gramatike. Generisanje apstraktnog sintaksnog stabla. Implementacija jednostavnih elemenata jezika C: funkcije, biblioteke, deklaracije, if, while, for. Implementacija semantičke analize. Uvod u okruženje LLVM.