Programski prevodioci 1

Programski prevodioci 1
Osnovne informacije
Šifra	13S114PP1, 13E114PP1
Semestar	7
Status	obavezni
Stranica	ir4pp1.etf.rs
ESPB	6
Odsek	SI, RTI

Programski prevodioci 1 je obavezni predmet u sedmom semestru na SI i RTI.

Korisne veze

• ETF SI (modifikacije)
• ETF Materijali (Box) (rešenja starijih rokova)
• Studentski video snimci rešenja zadataka sa vežbi i rokova (obrađeno celo kolokvijumsko gradivo, a ispitno zaključno sa „rekurzivnim spustom“)
• Slike prezentacija Kristijana Žiže (snimljene vežbe 2020)
• Neki saveti za izradu projekta

Nastava

Oblasti se na sledeći način obrađuju po blokovima:

• Prvi blok:
  • leksička analiza (konačni automati, minimizacija automata, konverzija iz nedeterminističkog u deterministički, konverzija regularnog izraza u DKA, leksički procesori),
  • generatori leksičkih analizatora (JFlex),
  • sintaksna analiza (uvod u gramatike i jezike),
  • potisni automati
• Drugi blok:
  • parsiranje od dna ka vrhu (LR(0) parseri, SLR(1) parseri, LALR(1) parseri, oporavak od grešaka),
  • generatori parsera (CUP),
  • parsiranje od vrha ka dnu (LL(1) gramatike, transformacija u LL(1), konstrukcija parsera po principu rekurzivnog spusta),
  • atributivno-translacione gramatike (S-atributivne i L-atributivne gramatike)
  • apstraktna sintaksna stabla (AST-CUP)
• Treći blok:
  • tabela simbola (konkretna realizacija na projektu, različite moguće organizacije, slučaj višestrukog nasleđivanja),
  • Mikrojava virtuelna mašina (memorijski segmenti, instrukcije, prevođenje izraza, prevođenje kontrolnih struktura, prevođenje poziva metoda, nasleđivanje i virtuelni mehanizam),
  • generisanje međukoda (četvorke, trojke, graf toka kontrole, SSA forma),
  • izvršno okruženje (kontrolne i pristupne veze, displeji, stabla aktivacije),
  • generisanje x86 koda (životni vek promenljivih, getreg algoritam)

Gradivo koje se obrađuje isključivo na predavanjima uključuje modelovanje konačnih automata u kodu, S-atributivne i L-atributivne gramatike, uključivanje akcija i atributa u parser konstruisan po principu rekurzivnog spusta, apstraktna sintaksna stabla i višestruko nasleđivanje. Gradivo iz JFlex, CUP i apstraktnih sintaksnih stabala, iako teoretski može da dođe na kolokvijumima, se jako retko pojavljuje. Gradivo S-atributivnih i L-atributivnih gramatika se češće pojavljuje na ispitu nego na kolokvijumu.

Svi materijali sa vežbi i predavanja mogu se pronaći na stranici predmeta, u nesrećnoj kombinaciji različitih formata (ZIP, RAR, DOC, PDF i PPT). Prezentacije Kristijana Žiže, čije su snimljene vežbe iz 2020. godine, nisu dostupne (obrisao ih je kada je odlazio sa predmeta), ali su dostupne slike tih prezentacija iz odeljka sa korisnim vezama. Na vežbama i predavanjima se takođe mogu pominjati zbirka ili udžbenik, one su dostupne sa stranice predmeta (doduše teško vidljive) i iz odeljka sa literaturom.

Projekat

Projekat na predmetu nosi 40 bodova i obavezan je. Uslov za izlazak na ispit je barem 20 bodova osvojenih na odbrani projekta. Predaje se do dan ili dva pred odbranu, sa malo ranijom inicijalnom predajom radi formiranja rasporeda (kao na OO1 i OO2). Projekat je podeljen na 3 nivoa, gde nivo A nosi 20, nivo B 30 i nivo C 40 bodova (moguće je osvojiti i broj bodova između ukoliko projekat ispunjava deo zahteva za viši nivo, ili ukoliko modifikacija na odbrani samo delimično radi). Obično za svaki nivo bude po jedan zahtev specifičan za tu školsku godinu, ali se nivo B generalno razlikuje od nivoa A po tome što zahteva implementaciju funkcija, a nivo C od nivoa B po tome što zahteva implementaciju klasa. Na kraju izrade projekta traži se i dokument sa izveštajem o projektu.

Postavka projekta se ne menja mnogo kroz godine. U januarskom i februarskom roku važi jedna postavka, u julskom se na tu postavku doda još zahteva i u avgustovskom i septembarskom još više zahteva. Projekat je moguće braniti samo jednom po postavci! Ovo znači da ukoliko padnete odbranu u januaru, nemate pravo na odbranu u februaru, i slično za avgustovki rok.

Od materijala za projekat relevantne su vežbe iz JFlex, CUP, tabele simbola i Mikrojava virtuelne mašine. Pored toga, na stranici predmeta postoje snimci i izvorni kod jednog studenta koji radi jedan mini-projekat po fazama, koji mogu biti korisni kao uvod u alate za izradu projekta i primere implementacije određenih zahteva. Veći deo koda sa tih snimaka može se iskoristiti radi implementacije zahteva za nivo A na projektu. Na snimcima se kao okruženje za izradu koristi Eclipse, ali bilo koje okruženje instalirano u računarskim laboratorijama na fakultetu je prihvatljivo. Takođe je dostupan vodič za izradu projekta.

Odbrana projekta se organizuje nekoliko dana pre ispita. Na odbrani se prvo rade modifikacije, zatim asistentu ili demonstratoru pokaže da modifikacija radi i potom brani osnovni projekat. Odbrana osnovnog projekta obično nije mnogo detaljna, već se pokrenu javni testovi i vidi da li rade (daju dobar ispis), eventualno otkomentarišu neke linije koje treba da izazovu greške. Tom prilikom se retko testira oporavak od sintaksnih greški i razne specifikacije ispisa propisane postavkom. U izveštaj sa projekta se ne ulazi. Struktura projekta koja u postavci piše da je neophodna nije zapravo neophodna. Neke od modifikacija prethodnih godina dostupne su iz odeljka sa korisnim vezama.

Stari projekti dostupni su sa stranice predmeta (godine 2021/2022 su dostupni na http://ir4pp1.etf.rs/Domaci/2021-2022, prethodne godine na http://ir4pp1.etf.rs/Domaci/2020-2021 i tako dalje, ali ne postoji lako dostupna lista domaćih na jednom mestu).

Ispitni rokovi

Ispitni rokovi se ponekad objavljuju na stranici predmeta, i ponekad imaju rešenja u vidu slikanih vežbanki studenata koji su osvojili maksimalan broj bodova.

Rokovi koji su rešeni na vikiju su:

• Januar 2018
• Januar 2020
• Januar 2021
• Januar 2022
• Januar 2023
• Januar 2024
• K 2023
• K1 2012
• K1 2015
• K1 2017
• K1 2019
• K1 2022
• K2 2015
• K2 2017
• K2 2019
• K2 2020
• K2 2022
• Septembar 2023
• Februar 2021

Ukoliko želite da dodate rok, posetite stranicu za pravljenje roka.

Literatura

Postoji jedna zbirka zadataka i jedan udžbenik iz predmeta, dostupni sa stranice predmeta:

• "Zbirka zadataka iz Programskih prevodilaca 1", D.Velašević, D.Bojić, 2000 izdavač: Elektrotehnički fakultet Univerziteta u Beogradu
• "Programski prevodioci 1", D.Bojić, M.Vukasović, 2022 (verzija 0.9)

Na zbirku se obično poziva iz materijala sa vežbi. Udžbenik opširno pokriva gradivo sa predavanja, ali kako još uvek nije došao do stabilne verzije ume imati čudne jezičke konstrukte koji ga čine neoptimalnim za spremanje ispita.

Način ocenjivanja

SI

• $K_1$, $K_2$ — bodovi sa prvog i drugog kolokvijuma koji se održavaju u prvoj i drugoj kolokvijumskoj nedelji i nadoknađuju se preko bodova sa ispita (0-20)
• $D$ — bodovi sa projekta (0-40)
• $I$ — bodovi sa ispita (0-60)
• Bodovi sa ispita/kolokvijuma: $P_1 = max\left(\frac{1}{3} I + K_1 + K_2, \frac{2}{3} I + K_1, \frac{2}{3} I + K_2, I\right)$
• Bodovi: $P = P_1 + D$
• Uslov: $D \geq 20$, $P_1 \geq 31$

Bodovi	$P \leq 51$	$50 < P \leq 61$	$60 < P \leq 71$	$70 < P \leq 81$	$80 < P \leq 91$	$91 < P$
Ocena	5	6	7	8	9	10

RTI

Kako na RTI ima samo jedan kolokvijum od 30 bodova, konačni bodovi se računaju po formuli: $P = D + max\left(\frac{1}{2} I + K, I\right)$.

Potrebna pomoć

• Na ovom predmetu fale postavke rokova. Pomozite vikiju pamćenjem/prepisivanjem rokova i postavljanjem na viki.
• Na ovom predmetu fale rešenja rokova. Pomozite vikiju rešavanjem rokova i postavljanjem njihovih rešenja na viki.

  Rokovi koji su prepisani a nisu rešeni su:

  • Januar 2023
  • Septembar 2023
  • K 2023
  • Januar 2024

  Rokovi kojima nedostaje poneko rešenje su:

  • K1 2012
  • K1 2022
  • K2 2022
  • Januar 2022
  • Februar 2021