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 22/23 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
|
Nastavnici | Nositelji:Asistenti: Josip Divić, pred. |
Preduvjeti | Nema |
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) | - Uvod, znak, abeceda, niz, operacije nad nizovima, jezik, operacije nad jezicima
- Konačni automati, deterministički konačni automati (DKA), definicija, minimizacija DKA
- minimizacija DKA
- Nedeterministički konačni automat (NKA), opis, definicija, konverzija u DKA
- Nedeterministički konačni automati s epsilon prijelazima (eps-NKA), opis, definicija, konverzija u nedeterministički automat bez epsilon prijelaza
- Konačni automati s izlazom, Mooreov automat, Mealyev automat, definicije, konverzija iz Mooreovog u Mealyev automat, konverzija iz Mealyevog u Mooreov automat
- Regularni izrazi, regularni jezici, operacije nad regularnim jezicima, algebarska pravila za regularne izraze, konstrukcija eps-NKA za zadani regularni izraz
- Formalna gramatika, kontekstno neovisna gramatika, Chomskyeva hijerarhija jezika, definicija kontekstno neovisne gramatike, jezik zadan gramatikom, generiranje niza, rekurzivno zaključivanje,
- 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
- Nejednoznačnost, pojam nejednoznačnosti kod gramatike, rješavanje nejednoznačnosti, inherentno nejednoznačni jezici
- Pojednostavljenja gramatike, uklanjanje beskorisnih znakova, uklanjanje epsilon produkcija, uklanjanje jediničnih produkcija, Chomskyjev normalni oblik
- Potisni automat, definicija, konfiguracija potisnog automata, konstrukcija potisnog automata za zadanu kontekstno neovisnu gramatiku, deterministički potisni automat
- Parsiranje, parsiranje od vrha prema dnu, parsiranje od dna prema vrhu, funkcije First i Follow, LL(1) gramatika, izgradnja SLR parsera
- SLR parser i nejednoznačnost, rješavanje nejednoznačnosti dodatnim pravilima o asocijativnosti i prioritetu operatora
- Nije definirano
|
auditorne vježbe (A) | - Nije definirano
- Nije definirano
- Nije definirano
- Nije definirano
- Nije definirano
- Nije definirano
- Nije definirano
- Nije definirano
- Nije definirano
- Nije definirano
- Nije definirano
- Nije definirano
- Nije definirano
- Nije definirano
- Nije definirano
|
kolokvij - teorija (KP) | - Nije definirano
- Nije definirano
|
ispit - teorija (IU) | - Nije definirano
|
samostalno učenje (SU) | - kolokviji, konzultacije, samostalni rad u laboratoriju i samostalno učenje
|