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.

Predmetni nastavnici:

• dr Milan Banković
• dr Mirko Spasić

Asistenti:

• Vladimir Kuzmanović
• Stefan Milenković

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)

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.

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.

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

• Uvodno predavanje
• Formalni jezici. Regularni jezici i regularni izrazi. Kontekstno slobodne gramatike i jezici. Transformacije gramatika.
• Konačni automati.
• Leksička analiza.
• Potisni automati.
• Sintaksna analiza.
• Semantička analiza.

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

• Regularni izrazi - materijali 3i2.
• Regularni izrazi u Pajtonu - materijali 3i2.
• Regularni izrazi u Pajtonu - materijali 3i2.
• Leksička analiza - Flex - materijali 3i2.
• Programski jezik C++ - materijali 3i2.
• Bison - Uvod - materijali 3i2.
• Bison - Nastavak - materijali 3i2.
• Programski Jezik C++ - Nasledjivanje - materijali 3i2.
• Bison - Sintaksna stabla - materijali 3i2.
• Bison - Sintaksna stabla - materijali 3i2.
• Bison - Sintaksna stabla - materijali 3i2.
• LL analiza - rekuzivni spust, potisni automat - materijali 3i2.

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

Korisni linkovi

• Regex101
• Grep
• Brzi python3 tutorijal
• Zvanična dokumentacija za re modul u python3.
• Flex
• Bison
• Learn C++

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

• Alfred Aho, Ravi Sethi, Jeffrey Ullman: Compilers: principles, techniques, and tools.
• Vladimir Kuzmanović, Ana Vulović: Zbirka zadataka.
• Stefan Milenković: Sintaksna stabla
• Mirko Spasić: Snimci vežbi od ranijih godina
• Regularni izrazi: Primeri, Tutorijal, Kalkulator
• Grep
• Brzi python3 tutorijal
• Zvanična dokumentacija za re modul u python3.
• Flex
• Bison