Ispitna pitanja iz Prevodilaca i interpretatora


(ispitna pitanja za školsku 1999/2000.)

  • Jezički procesori. Sintaksa i semantika programskog jezika
  • Struktura i funkcije kompilatora
  • Karakter, azbuka, niska (reč), jezik, operacije nad jezicima
  • Pojam gramatike. Jezik definisan gramatkom
  • Hijerarhija Čomskog
  • Regularni skupovi, regularni izrazi, regularni jezici
  • Veza između desno-linearnih gramatika i regularnih jezika
  • Leksička analiza
  • Veza između regularnih izraza i konačnih automata
  • Konačni automati (nederministički i deterministički automati)
  • Konstrukcija determinističkog konačnog automata
  • Minimizacija determinističkog konačnog automata
  • Konačni i potisni transduktori
  • Primene konačnih automata u obradi prirodnih jezika
  • Rukovanje tabelom simbola
  • Alokacija memorije
  • Kontekst-slobodne gramatike i jezici. Izvođenje i drvo izvođenja
  • Klasifikacija metoda sintaksičke analize
  • Metoda rekurzivnog spusta
  • Sintaksna analiza naniže
  • Sintaksna analiza naviše
  • Algoritam sintaksne analize za LL(1) gramatike
  • Algoritam sintaksne analize za LR(1) gramatike
  • Potisni automat (konfiguracija, relacija prelaska, jezik PA)
  • Prihvatanje reči praznom potisnom listom
  • Veza običnih i proširenih potisnih automata
  • Veza potisnih automata i kontekst-slobodnih gramatika (analiza naniže)
  • Veza potisnih automata i kontekst-slobodnih gramatika (analiza naviše)
  • Deterministički potisni automat, deterministički KSJ i veza sa KSJ
  • Formalno prevođenje. Shema sintaksno-vođenog prevođenja
  • Karakterizacija prevođenja preko kontekst-slobodnih gramatika
  • Semantička analiza preko semantičkih rutina (generisanje koda)
  • Proširene i atributske gramatike
  • Prošireni regularni izrazi. Regularna definicija. Primeri implementacije u lex-u i awk-u
  • Generisanje leksičkih analizatora (lex i veza sa generatorom parsera)
  • Ulazni sistem leksičkog analizatora
  • Organizacija ulazne datoteke u lex-u
  • Metode predstavljanja tablica u LeX-u i način konsultovanja
  • Struktura funkcije yylex() (gramzivi algoritam; izlaz iz lex-a
  • Konstrukcija tablica za SLR(1)-gramatike
  • Konstrukcija tablica za kanonski LR(1) i LALR(1)
  • Ulazna i izlazna datoteka iz sistema yacc
  • Generisanje kompilatora
  • Transformacije KSG (leva rekurzija, eliminacija leve rekurzije)
  • Transformacije KSG (e-pravilo, jednostruka pravila, eliminacija ciklusa)
  • Transformacije KSG (suvišna slova, leva faktorizacija)
  • Liste, rekurzija i asocijativnost operatora