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.

Tokom ove školske godine neće biti moguć prenos poena ostvarenih na predispitnim obavezama iz prethodnih školskih godina.

ISPIT

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

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, bez obzira na rezultat drugog dela ispita (npr. ako student položi praktični, a zatim padne teorijski, praktični mu i dalje važi). Ukoliko student nije zadovoljan ostvarenim rezultatom na delu ispita, može ga polagati ponovo, čime mu se automatski poništava prethodni rezultat.

Da bi ispit bio položen, potrebno je ostvariti pragove na praktičnom i teorijskom delu, kao i sakupiti bar 51 poen u zbiru.

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

Otkazana predavanja - Grupa 3i2

Predavanja za grupu 3i2 sutra neće biti održana. O nadoknadi ćemo se dogovoriti sledećeg utorka na redovnom času.

01.12.2025.

Nadoknada predavanja - Grupa 3i2

Nadoknada predavanja za grupu 3i2 će biti održana u subotu 22.11.2025 u 8:15h preko Webex platforme.

20.11.2025.

Nadoknada vežbi - Grupa 3i1a

Po preporuci, nadoknada propuštenog časa za grupu 3i1a će biti održana u subotu 22.11.2025. godine po rasporedu časova, odnosno, sa početkom u 08:15 u zgradi u ulici Vatroslava Jagića.

19.11.2025.

Vežbe - Grupa 3i1b

Vežbe iz PPJ za grupu 3i1b koje se održavaju utorkom će počinjati od 11:30h.

17.11.2025.

Početak školske godine

Nastava iz Prevodjenja programskih jezika (PPJ) u jesenjem semestru školske 2025/26 godine počinje 12.11.2025. 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.

10.11.2025.

Zbirni rezultati ispita u dodatnom ispitnom roku (II tok)

Zbirni rezultati ispita u dodatnom ispitnom roku (II tok) mogu se videti ovde (ods format) ili ovde (xls format).

Uvid u radove mejlom. Upis ocene: u terminu predavanja tokom predstojećeg semestra.

10.11.2025.

Zbirni rezultati ispita u dodatnom ispitnom roku (I tok)

Zbirni rezultati ispita u dodatnom ispitnom roku (I tok) mogu se videti ovde (ods format) ili ovde (xls format).

Uvid u radove mejlom. Upis ocene: u terminu predavanja tokom predstojećeg semestra.

10.11.2025.

Dodatni rok - Rezultati praktičnog ispita

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

Za uvid u radove javite se mejlom Stefanu Milenkoviću do cetvrtka 06.11.2025. u 23:59.

06.11.2025.

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