Naziv kolegija: Teorija sintaksne analize i primjene
Nastavnik: prof. dr. sc. Zdravko Dovedan Han
ECTS-bodovi: 6
Jezik: hrvatski
Trajanje: jedan semestar (8.)
Status: obavezan za studente jednopredmetnog diplomskog studija informatike, istraživački smjer, izborni za ostale studije
Oblik nastave: 1 sat predavanja - 2 sata seminara - 1 sat vježbi
Uvjeti: Algoritmi i strukture podataka i Uvod u formalne jezike i automate
Ispit: pismeni i usmeni
Sadržaj
Uvod: temeljni pojmovi teorije formalnih jezika. Uvod u teoriju sintaksne analize: parsiranje, prepoznavanje. Prepoznavanje regularnih jezika: konačni prepoznavač, regularni izrazi i pretraživanje. Prepoznavači beskontekstnih jezika: stogovni prepoznavač, prepoznavač s praznim stogom, prošireni stogovni automat, gramatika i ekvivalentni prošireni stogovni automat. Višeprolazno parsiranje: silazna sintaksna analiza, uzlazna sintaksna analiza. Tablični postupci sintaksne: Cocke-Younger-Kasamijev algoritam (CYK), Earleyjev postupak parsiranja. LL(k) jezici i sintaksna analiza: jezici tipa LL(k), predikatna sintaksna analiza, sintaksna analiza LL(1) jezika. LR(k) jezici i sintaksna analiza: jezici tipa LR(k), LR(0) gramatike i stogovni prepoznavači, sintaksna analiza LR(1) jezika, gramatike s relacijom prioriteta. Prepoznavač kontekstnih jezika: dvostruko-stogovni prepoznavač, dvostruko-stogovni prepoznavač s jednim stanjem, Turingov stroj. Prepoznavač jezika sa svojstvima: jezici sa svojstvima, prepoznavač jezika sa svojstvima.
Sadržaj vježbi
Vježbe slijede predavanja. Sva teorijska razmatranja i definicije upotpunjavaju se odgovarajućim primjerima. Svi se algoritmi implementiraju u jeziku Python.
Sadržaj seminara
Rješavanje individualnog projektnog zadatka izradom praktičnog programskog rješenja (parsera ili prepoznavača) u jeziku Python, a za izabrani postupak sintaksne analize. Student predstavlja svoj rad u pisanom obliku i brani ga usmeno pred predmetnim nastavnikom.
Opće i specifične kompetencije
Student će dobiti temeljna znanja iz discipline formalnih jezika, posebno sintaksne analize, neophodna za primjenu u identifikaciji ulaznog jezika i definiranju postupka za njegovu sintaksnu analizu.
Ishodi učenja
Nakon uspješno savladanog predmeta, student će moći:
1) Definirati pojam sintaksne analize .
2) Modelirati regularni izraze za prepoznavanje regularnih jezika.
3) Provesti istraživanja o efikasnosti postupaka sintaksne analize beskontekstnih jezika.
4) Primijeniti optimalan postupak sintaksne analize.
5) Primijeniti stečena znanja u drugim predmetima studija.
Način održavanja nastave
- Predavanja: kombinirano, klasično (ploča) i prikazom primjera izvedbom na PCu i projiciranjem uz istodobno pisanje primjera programa od strane studenata na svojim računalima.
- Vježbe: rješavanje postavljenih zadataka i pisanje programa na računalu.
- Seminar: rješavanje zadanog projektnog (seminarskog) rada uz konzultiranje s predmetnim nastavnikom.
Obveze studenata i uvjeti
Obvezno pohađanje nastave (predavanja i vježbi).
Način provjere znanja
Praćenje rada i aktivnosti studenata tijekom semestra:
- pohađanje predavanja – 10 bodova,
- posebna isticanja na vježbama – do 10 bodova.
Seminarski rad:
- Obrana seminarskog rada – 80 bodova
Skala ocjena:
dovoljno (2) 50% - 59%
dobro (3) 60% - 69%
vrlo dobro (4) 70% - 79%
izvrsno (5) 80% - 100%
Obavezna literatura
- Dovedan Han, Z.: FORMALNI JEZICI I PREVODIOCI • sintaksna analiza i primjene, Element, Zagreb, 2012.
Preporučena literatura
-
Aho, V. A.; Ullman, D. J.: The Theory of Parsing, Translation, and Compiling, vol. I: Parsing,
Prentice-Hall, 1972. - Dovedan, Z.: FORMALNI JEZICI • sintaksna analiza, Zagreb, ZIS, 2003.
- Dovedan Han, Z.: Pascal s tehnikama programiranja (1), VVG, Velika Gorica, 2011.
- Dovedan Han, Z.: FORMALNI JEZICI I PREVODIOCI • regularni izrazi, gramatike, automati, Element, Zagreb, 2012.
- Grune, D.: Parsing Techniques – A Practical Guide, Ellis-Horwood, 1990.
- Tomita, M., editor: Current Issues in Parsing Technology, Kluwer Academic Publishers, 1991.
- Wirth, N.: Algorithms + Data Structures = Programs, Prentice-Hall, 1976.
