Prevođenje programskih jezika

I smer

Kurs Prevođenje programskih jezika je obavezan kurs na trećoj godini I smera u okviru kojeg se proučavaju osnovni koncepti prevođenja programskih jezika i leksičke analize:

  • Etape i faze procesa prevođenja programskih jezika
  • Regularni jezici i konačni automati
  • Leksička analiza. Alati Lex/Flex
  • Konteksno-slobodni jezici i potisni automati
  • Sintaksna analiza naniže. LL gramatike. Rekurzivni spust
  • Sintaksna analiza naviše. LR gramatike. Alat Yacc/Bison
  • Atributske gramatike. Uvod u semantičku analizu.
U okviru studija postoje i drugi kursevi koji se bave bliskim temama.

Predmetni nastavnici:

Asistenti:

NASTAVA

Nastava se sastoji iz dva časa predavanja i tri časa vezbi nedeljno.

Predmet vredi 6 ESPB.

PREDISPITNE OBAVEZE

  • Aktivno prisustvo na časovima (5 + 5 poena)
  • Testovi na predavanjima (10 poena)
Na predispitnim obavezama nema pragova.

ISPIT

  • Praktični ispit (55 poena, prag 22 poena)
  • Teorijski ispit (35 poena, prag 14 poena)

Da bi student mogao da izadje na teorijski deo ispita, neophodno je da prethodno ostvari prag na praktičnom delu. Teorijski i praktični deo se polažu nezavisno jedan od drugog (ne obavezno u istom roku). Jednom položeni deo ispita, bilo teorijski, bilo praktični, važi do kraja školske godine.

Polozen praktični deo ispita važi do kraja školske godine, nezavisno od izlazaka na teorijski deo (tj. čak i ako student padne na teorijskom delu ispita, praktični mu i dalje važi). Ukoliko student nije zadovoljan ostvarenim rezultatom na praktičnom delu ispita može izaći ponovo na praktični, pri čemu mu se prethodni rezultat automatski poništava (isto važi i za teorijski deo).

Za sve nejasnoće obratiti se nastavniku na mejl.

Nastavne teme po časovima

  • Proces prevodjenja programskih jezika. Kompilacija i interpretacija.
  • Azbuka, reč, jezik. Operacije nad jezicima. Regularni jezici i regularni izrazi.
  • Ograničenja regularnih jezika. Lema o razrastanju (pumping lemma). Kontekstno slobodni jezici i kontekstno slobodne gramatike. Stablo izvodjenja. Jednoznačne i višeznačne gramatike.
  • Transformacije gramatika. Eliminacija nekorisnih simbola. Eliminacija ε-pravila. Eliminacija jednostrukih pravila. Eliminacija leve rekurzije.
  • Konačni automati. Definicija i primeri. Deterministički konačni automati. Eliminacija ε-prelaza. Upotpunjavanje i determinizacija konačnog automata. Konstrukcija po podskupovima. Osobine prepoznatljivih jezika. Presek, unija, razlika, komplement. Nadovezivanje i Klinijevo zatvorenje.
  • Konstrukcija Tompsona i Gluškova. Minimizacija konačnog automata. Murov algoritam.
  • Algoritam eliminacije stanja. Klinijeva teorema.
  • Potisni automati. Deterministički potisni automati.
  • Sintaksna analiza naniže. LL(1) gramatike. Tablice LL(1) analize.
  • Sintaksna analiza naviše. LR(1) i SLR(1) gramatike. Automat LR-analize. Tablice SLR(1) analize.
  • Elementi semantičke analize. Atributske gramatike. Sintetizovani i nasledjeni atributi. Primeri.

Materijali sa predavanja

Primeri ispitnih rokova i ispitnih zadataka (teorijski ispit) mogu se videti ovde.

Nastavne teme

  • Regularni izrazi.
  • Programski jezik Python. Regularni izrazi u programskom jeziku Python. Leksička analiza.
  • Konačni automati. Implementacija konačnih automata u programskom jeziku Python.
  • Generator leksičkih analizatora - flex.
  • Sintaksna analiza. Gramatike. Transformacija gramatika.
  • Sintaskna analiza na niže. LL gramatike. Skupovi First i Follow. Rekurzivni spust. Potisni automati.
  • Sintaskna analiza na više. LR gramatike. Action i goto tablice.
  • Generator sintaksnih analizatora - yacc/bison.

Materijali sa časova

Ispitni zadaci

  • Januar 1 - 2024 - tekst i rešenje.
  • Januar 2 - 2024 - tekst i rešenje.
  • Jun 1 - 2024 - tekst i rešenje.
    Napomena: Upravljanje tipovima je rešeno pomoću void pokazivača bez neke ozbiljnije provere njihove ispravnosti da bi se izbeglo nepotrebno zatrpavanje detaljima. Ovakvo rešenje bi se u potpunosti priznalo na ispitu. Kompletno rešenje bi obuhvatalo izgradnju odgovarajuće hijerarhije klasa kojom bi se elegantno predstavili svi tipovi u programu i omogućila njihova jednostavna provera, ali to pokušajte da uradite za domaći. Takođe, reprezentacija grafa iskorišćena u rešenju nije jedina koja je moguća i vrlo verovatno nije najefikasnija.
  • Jun 2 - 2024 - tekst i rešenje
  • Sep 1 - 2024 - tekst i rešenje

Konsultacije

  • Snimak 08.08.2025. - link. Šifra za pristup snimku je PrevodjenjeProgramskihJezika2025.
  • Materijali 08.08.2025. - link.

Korisni linkovi

Literatura za predavanja

  • Duško Vitas. Prevodioci i interpretatori.
  • Alfred Aho, Ravi Sethi, Jeffrey Ullman: Compilers: principles, techniques, and tools.
  • Alfred Aho, Jeffrey Ullman: The theory of parsing, translation and compiling.
  • Nikola Ajzenhamer. Anja Bukurov. Prevodjenje programskih jezika

Literatura za vežbe

Anketa za izlazak na ispit u januar2 roku

Mole se svi studenti koji planiraju da izlaze na ispit u roku januar 2 (bilo na praktični, bilo na teorijski, ili oba) da se prijave putem ankete. Podsećamo da se oba dela ispita održavaju istog dana (subota, 23.8.) u različitim terminima i mogu se polagati nezavisno.

Rok za prijavu je petak, 22.8. u 13.00h. Mole se studenti koji ne planiraju da izlaze da se ne prijavljuju.

20.8.2025.

Zbirni rezultati ispita u roku januar1 (drugi tok)

Zbirni rezultati ispita u roku januar 1 (prvi tok) mogu se videti ovde (ods verzija) ili ovde (xls verzija).

Za uvid u radove (teorija) obratiti se Mirku mejlom. Upis ocena: po dogovoru.

14.08.2025.

Zbirni rezultati ispita u roku januar1 (prvi tok)

Zbirni rezultati ispita u roku januar 1 (prvi tok) mogu se videti ovde (ods verzija) ili ovde (xls verzija).

Za uvid u radove (teorija) obratiti se Milanu mejlom. Upis ocena: ponedeljak, 18.8. u 17:15h u Svetog Nikole, ili u nekom kasnijem terminu po dogovoru.

14.08.2025.

Januar 1 - Rezultati praktičnog ispita

Rezultate praktičnog ispita možete pogledati na sledećem linku.

Za uvid u radove javite se mejlom Vladimiru Kuzmanoviću do srede 13.08.2025. u 23:59.

12.08.2025.

Obaveštenje pred ispit u roku januar1

Mole se svi studenti koji polažu praktični u roku januar1 da na ispit dodju najkasnije u 8:45h, kako bismo na vreme krenuli sa razmeštanjem. Ispit počinje u 9h i održava se na Trgu.

Studenti koji polažu teorijski deo ispita treba da dođu najkasnije u 12:45h. Ispit počinje u 13h i održava se u učionici 706.

10.08.2025.

Praktični ispit - konsultacije

Konsultacije iz Prevođenja programskih jezika održaće se u četvrtak 08.08.2025. onlajn putam Webex-a sa početkom u 12h. Planirano vreme trajanja konsultacija je 3h.

Konsultacijama možete pristupiti pomoću sledećeg linka.

Šifru za pristup konsultacijama ste dobili na svoje alas mejlove.

07.08.2025.

Anketa za izlazak na ispit u januar1 roku

Mole se svi studenti koji planiraju da izlaze na ispit u roku januar 1 (bilo na praktični, bilo na teorijski, ili oba) da se prijave putem ankete. Podsećamo da se oba dela ispita održavaju istog dana (ponedeljak, 11.8.) u različitim terminima i mogu se polagati nezavisno.

Rok za prijavu je subota, 9.8. u 23.59h. Mole se studenti koji ne planiraju da izlaze da se ne prijavljuju.

6.8.2025.

Termini teorijskog dela ispita

Teorijski deo ispita u svim ispitnim rokovima biće održan istog dana kada i praktični, samo kasnije, u terminu od 13h do 15h u učionici 706.

S obzirom na izuzetno gust raspored ispita u predstojećim rokovima, odlučeno je da se dozvoli polaganje teorijskog dela čak i ako praktični deo ispita nije položen. Jednom položen teorijski deo važi do kraja školske godine, kao i praktični (osim ako student ne izađe ponovo na teorijski deo ispita, u kom slučaju mu se prethodni rezultat automatski poništava). Praktični i teorijski deo ispita se ne moraju polagati u istom roku.

Napominjemo da ovo važi samo u tekućoj školskoj godini, s obzirom na vanredne okolnosti u kojima se ceo nastavni i ispitni proces odvija. Od sledeće školske godine važe stara pravila.

Za sve nejasnoće, obratite se nastavniku mejlom.

1.8.2025.

Poeni sa predispitnih obaveza -- II tok

Zbirni poeni sa predispitnih obaveza za II tok mogu se videti ovde (ods format), odnosno ovde (xls format). Molim sve studente da provere svoje poene i hitno jave profesoru mejlom ako uoče neku grešku.

26.2.2025.

Poeni sa predispitnih obaveza -- I tok

Zbirni poeni sa predispitnih obaveza za I tok mogu se videti ovde (ods format), odnosno ovde (xls format). Molim sve studente da provere svoje poene i hitno jave profesoru mejlom ako uoče neku grešku.

25.2.2025.

Vežbe - 9.1.2025

Vežbe planirane za 09.01.2025. kalendarom aktivnosti i rasporedom časova, održaće se onlajn putem Webex-a u subotu 11.01.2025. od 10-13h, blokada do 17. Link za praćenje nastave biće naknadno okačen.

Link za praćenje vežbi: link.
Šifra za praćenje: #

09-10-....01.2025.

Vežbe - grupa 3i2a

U sredu 20.11.2024. vežbe će se održati u terminu 13-16h u sali JAG1, umesto u terminu od 12-15h.

19.11.2024.

Predavanja - Grupa 3i2

Naredni dvočas predavanja za grupu 3i2 (četvrtak, 21.11 od 10:15) biće održan preko platforme Webex (link).

15.11.2024.

Vežbe - grupa 3i2a

U sredu 13.11.2024. vežbe će se održati u terminu 14-17h u sali JAG1, umesto u terminu od 12-15h.

12.11.2024.

Vežbe - nadoknada

Nadoknada vežbi kod Stefana Milenkovića održaće se u petak 8.11.2024. od 12-15h u sali N252. Redovan čas vežbi držaće se u uobičajenom terminu od 15-18h u sali N202.

06.11.2024.

Predavanja - Grupa 3i2

Nadoknada izgubljenog dvočasa predavanja za grupu 3i2 je u utorak od 17:15 preko platforme Webex (link)

03.11.2024.

Vežbe

Vežbe iz PPJ za sve grupe držaće se u terminima navedenim u rasporedu časova.

27.10.2024.

Predavanja - Grupa 3i2

Ove nedelje neće biti predavanja. Dogovorićemo se o terminu nadoknade na sledećem dvočasu.

21.10.2024.

Vežbe - Grupa 3i2b

U prve tri nedelje semestra, vežbe iz PPJ za grupu 3i2b držaće se sredom od 15-18h u učionici JAG1.

05.10.2024.

Početak školske godine

Nastava iz Prevodjenja programskih jezika (PPJ) počinje 7.10.2024. po rasporedu časova koji je objavljen na veb strani Fakulteta.

Sve informacije vezane za predmet u toku semestra i kasnije tokom ispitnih rokova će se nalaziti isključivo na ovoj stranici.

30.09.2024.

Matematički fakultet, Univerzitet u Beogradu
školska 2019/20. godina