Interpretacija programa

Obavijesti

• Prvo predavanje (M. Horvat) iz Interpretacije programa u akademskoj godini 2020/21. održat će se u srijedu, 10. ožujka 2021. u 10 sati, preko Zooma.

O kolegiju (iz akademske godine 2018/19.)

• kolegij na prvoj godini diplomskog studija Matematika i računarstvo
• Merlin - svakako upišite ako planirate slušati!
• nastava: Marko Horvat i Vedran Čačić, predavanja i vježbe otprilike u omjeru 2:1
• ljetni semestar, akademska godina 2018./19.: petkom od 11 do 14 sati
• Praktikum 3 ili predavaonica 110 (default), prema obavijesti na webu
• pravila polaganja
• Gradivo:
  1. dio semestra: teorija formalnih jezika (Chomskyjeva hijerarhija)
  2. dio semestra: leksička, sintaksna i semantička analiza programskih jezika

Nastavni materijali

• slajdovi
• repozitorij
• Literatura:
  • Michael Sipser: Introduction to the Theory of Computation, 3rd edition (Poglavlja: 1.1,1.2,1.3,1.4,2.1,2.2,2.3,3.1,3.2,4.1,4.2,5.1,5.3)
  • Siniša Srbljić: Jezični procesori 1, Jezični procesori 2
  • Andrew W. Appel: Modern Compiler Implementation
• Slični kolegiji:
  • #CS143: Compilers (Stanford)
  • #CS164: Programming Languages and Compilers (Berkeley)
• Zanimljivi linkovi:
  • Base CS -- nekoliko vrlo high-level članaka o raznim aspektima leksičke, sintaksne i semantičke analize
  • Marianne writes a programming language (transkripti) -- podcast o avanturi jedne "tehnološke antropologinje", koja je ničim izazvana jednog dana odlučila dizajnirati vlastiti programski jezik [svaka epizoda je dijalog s posebno odabranim gostom ili gostima]

Zadaci za vježbu

• Linkovi:
  • Goddard's CpSc3500
  • CSCI 2400 Models of Computation
• U Sipseru ima hrpa zadataka!
• Održani prvi kolokviji:
  • Redovni: 2016, 2017, 2018, 2019, 2021
  • Popravni: 2016, 2017, 2018, 2019
• Održani drugi kolokviji:
  • Redovni: regularni izrazi, digitalni sklopovi, LOOP-programi, λ-račun, recepti
  • Popravni: μLOGO, aritmetika u ℚ, kemijske formule, nTeX
  • Zadaci doc. Puljića
• Stare zadaće

FAQ

Zašto Interpretacija programa ne koristi generatore lexera i parsera (flex, bison, ...)?

Jer je Python bolji jezik za opisivanje algoritama nego bilo koji od tih jezika. Implementirajući lexer i parser naučit ćete kako lexer i parser funkcioniraju. Programirajući bison naučit ćete kako programirati bison, ali reduce/reduce conflict će vam i dalje biti misterija. Neki ljudi s puno iskustva u dizajnu programskih jezika se slažu sa mnom.

Zašto ne koristimo error recovery nego prekinemo obradu nakon prve greške?

Zato što je ponovo pokretanje kompajlera (ili bilo kakvog analizatora) nakon ispravljanja pojedine greške najčešće brži način rada. U samom početku rada s npr. gccom studenti brzo nauče da gledaju samo prvu poruku o grešci, a ostale zanemare. (U davna vremena batch kompajliranja bez interakcije s korisnikom, nije bilo tako. Ali ta vremena su daleko iza nas.)

Zašto Token nije/jest hashable?

(U novijim verzijama biblioteke jest, ali ostatak odgovora i dalje vrijedi.) Jer najčešće kad mislite da želite Token koristiti kao ključ u rječnicima, zapravo želite koristiti njegovu vrijednost. Token je zadan tipom i sadržajem, a za imalo kompliciranije tokene, vrijednost nije injektivna funkcija ta dva argumenta. Recimo, tokeni različitih sadržaja 255 i 0xff imaju istu vrijednost u većini modernih jezika, pa nema smisla jednog od njih koristiti kao ključ u npr. nekoj implementaciji polja (vrijednost neće biti pronađena pod onim drugim).