DIT - Automati i jezici

Naziv predmeta

Automati i jezici

Detalji
Kod
VSITE204
Skr.
AJEZ
ECTS
6
Godina
2
Semester
Zimski semestar
Vrsta
izborni
Razina HKO 7
Diplomski studiji
E-Learning
0%
Aktivnosti
DIT zg - Ljet 19/20
ECTS
Jedinice
Sati
Svega
P
1.5
15
3
45
A
1
15
2
30
L
0
0
0
0
S
0
0
0
0
KA
0
0
0
0
KP
0
2
1
0
PR
0
0
0
0
IP
0
0
0
0
IU
0
1
2
0
SU
3.5
1
105
105
NastavniciNositelji: Josip Divić, pred.
Asistenti: Mariza Maini, asist. vis. šk.
PreduvjetiNema
Sadržaj

Jezični procesori. Leksička, sintaktička i semantička analiza. Generiranje međukoda. Formalna definicija abecede, niza i jezika. Operacije među jezicima. Klasifikacija programskih jezika: imperativni, objektno orijentirani, funkcionalni i logički jezici. Jednostavni jednoprolazni kompilatori i interpreteri. Leksička analiza programskih jezika. Regularni jezici: Konačni automati. Regularni izrazi. Formalne gramatike. Regularne gramatike. Kontekstno neovisni jezici: Kontekstno neovisna gramatika. Potisni automat. Leksički generator - Lex. Sintaktička analiza. Top-down parseri. Generator parsera za LL(k) gramatiku. Bottom-up LR parseri i push-down automati. Generator parsera –Yacc. Sintaksno usmjereno prevođenje. Atribuirana gramatika. Apstraktno sintaktičko stablo i tablica simbola. Provjera tipova podataka. Generiranje međukoda i programskog koda za CISC procesore i virtualne stog procesore. Optimiranje koda. Primjer izrade kompilatora. Primjer izrade interpretera za funkcionalni jezik. Rekurzivno prebrojivi jezici: Turingov stroj. Gramatika neograničenih produkcija. Kontekstno ovisni jezici: Kontekstno ovisna gramatika. Linearno ograničeni automat. Razredba jezika, automata i gramatika: Strukturna složenost jezika. Složenost prihvaćanja jezika.

Ciljevi učenja

Osposobiti studenta za razumijevanje jezika i prevođenja.

Ishodi učenja

1. Objasniti leksičku, sintaktičku i semantičku analizu, abecedu, niz, jezik i operacije među jezicima, Turingov stroj i gramatiku neograničenih produkcija.
2. Nabrojati klase jezika, automata i gramatika, programske prevodioce klasificirati programske jezike.
3. Primijeniti programe za razlaganje.
4. Izraditi interpreter za funkcionalni jezik.

Sposobnosti

Kolegij pruža temeljna teoretska znanja s područja automata, gramatika i jezika kao osnovu jezgre računarstva.

Preporučena literatura

1. Srbljić, S.: Jezični procesori 1, Element, Zagreb, 2002.
2. Srbljić, S.: Jezični procesori 2, Element, Zagreb, 2002

Dodatna literatura
predavanja (P)
  1. Uvod, znak, abeceda, niz, operacije nad nizovima, jezik, operacije nad jezicima
  2. Konačni automati, deterministički konačni automati (DKA), definicija, minimizacija DKA
  3. minimizacija DKA
  4. Nedeterministički konačni automat (NKA), opis, definicija, konverzija u DKA
  5. Nedeterministički konačni automati s epsilon prijelazima (eps-NKA), opis, definicija, konverzija u nedeterministički automat bez epsilon prijelaza
  6. Konačni automati s izlazom, Mooreov automat, Mealyev automat, definicije, konverzija iz Mooreovog u Mealyev automat, konverzija iz Mealyevog u Mooreov automat
  7. Regularni izrazi, regularni jezici, operacije nad regularnim jezicima, algebarska pravila za regularne izraze, konstrukcija eps-NKA za zadani regularni izraz
  8. Formalna gramatika, kontekstno neovisna gramatika, Chomskyeva hijerarhija jezika, definicija kontekstno neovisne gramatike, jezik zadan gramatikom, generiranje niza, rekurzivno zaključivanje,
  9. Regularna gramatika, konstrukcija kontekstno neovisne gramatike iz zadanog DKA, konstrukcija kontekstno neovisne gramatike iz zadanog regularnog izraza, linearna gramatika, lijevo i desno linearna gramatika, konstrukcija NKA iz lijevo i desno linearne gramatike
  10. Nejednoznačnost, pojam nejednoznačnosti kod gramatike, rješavanje nejednoznačnosti, inherentno nejednoznačni jezici
  11. Pojednostavljenja gramatike, uklanjanje beskorisnih znakova, uklanjanje epsilon produkcija, uklanjanje jediničnih produkcija, Chomskyjev normalni oblik
  12. Potisni automat, definicija, konfiguracija potisnog automata, konstrukcija potisnog automata za zadanu kontekstno neovisnu gramatiku, deterministički potisni automat
  13. Parsiranje, parsiranje od vrha prema dnu, parsiranje od dna prema vrhu, funkcije First i Follow, LL(1) gramatika, izgradnja SLR parsera
  14. SLR parser i nejednoznačnost, rješavanje nejednoznačnosti dodatnim pravilima o asocijativnosti i prioritetu operatora
  15. Nije definirano
auditorne vježbe (A)
  1. Nije definirano
  2. Nije definirano
  3. Nije definirano
  4. Nije definirano
  5. Nije definirano
  6. Nije definirano
  7. Nije definirano
  8. Nije definirano
  9. Nije definirano
  10. Nije definirano
  11. Nije definirano
  12. Nije definirano
  13. Nije definirano
  14. Nije definirano
  15. Nije definirano
kolokvij - teorija (KP)
  1. Nije definirano
  2. Nije definirano
ispit - teorija (IU)
  1. Nije definirano
samostalno učenje (SU)
  1. kolokviji, konzultacije, samostalni rad u laboratoriju i samostalno učenje

Klaićeva 7, 10000 Zagreb, tel. 01/3764200 fax. 01/3764264