Subject: Formal languages and interpreters
Course: Syntax analysis and application theory
ECTS credits: 5
Language: Croatian/ English/ French
Duration: 1 semester
Status: compulsory for students of Informatics, elective for all other students at the Department and the Faculty
Method of teaching: 1 lecture hour – 1 hour of seminar – 2 hours of practical classes
Prerequisite: Introduction to Formal Languages and Automata
Assessment: written and oral exam

Course description:
Introduction: fundamental concepts of the formal languages theory, concept of syntax analysis. General procedures of syntax analysis: top-down syntax analysis, bottom-up syntax analysis, Cocke-Younger-Kasami syntax analysis algorithm, Early's syntax analysis procedure. One-pass syntax analysis: LL (k) language types, LLR (k) language types, grammars with relation priority, and efficiency of one-pass syntax analysis procedures. Languages with properties: definition of a language with properties, language with properties recognizer. Comparison of syntax analysis procedures.
Practical classes give examples that follow lectures. All theoretical discussions and definitions are followed with appropriate examples. Examples of grammar input and the execution of certain syntax analyses are mostly shown through don-syntax.
Written reports should include programs written in language appropriate for chosen procedures of one-pass and multiple-pass syntax analysis.
Lectures are given in a classical manner using chalk and board. Practical classes are given partly in a classical manner and partly using computers.

Course objectives:
Students are given fundamental knowledge of formal languages, especially from the theory of syntax analysis of programming languages and translation theory. Students are expected to independently define the language and possibly design the translator (either interpreter or preprocessor).

Quality check and success of the course: Quality check and success of the course will be done by combining internal and external evaluation. Internal evaluation will be done by teachers and students using survey method at the end of semester. The external evaluation will be done by colleagues attending the course, by monitoring and assessment of the course.

Reading list:
1. DOVEDAN, Zdravko: FORMALNI JEZICI • sintaksna analiza, Zagreb, Zavod za informacijske studije, 2003.

Additional reading list:
1. AHO, V. Alfred; ULLMAN, D. Jeffrey: The Theory of Parsing, Translation, and Compiling, vol. I: Parsing, Prentice-Hall,  1972.
2. AHO; SETHI; ULLMAN: Compilers: Principles, Techiques, and Tools, Addison-Wesley Publishing Company,  1986.
3. DENNING, J. P.; DENNIS, B. J.; QUALITZ, E. J.: Machines, Languages, and Computation, Prentice-Hall, 1978.
4. DOVEDAN, Zdravko: don-grammar, program za definiranje i transformiranje beskontekstnih gramatika, Zagreb, Filozofski fakultet, 2003.
5. DOVEDAN, Zdravko: don-sintax, program za sintaksnu analizu beskontekstnih jezika, Zagreb, Filozofski fakultet, 2003.
6. DOVEDAN, Zdravko: Pascal i programiranje (1), Zagreb, don, 1995.
7. GRUNE, D.: Parsing Techniques – A Practical Guide, Ellis-Horwood, 1990.
8. HOPCROFT, E. J.; ULLMAN, D. J.: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.
9. KALUŽNIN, A. L.: Što je matematička logika,  Zagreb, Školska knjiga 1975.
10. KUREPA, Svetozar: Uvod u matematiku, Zagreb, Tehnička knjiga, 1970.
11. TOMITA, M., editor: Current Issues in Parsing Technology, Kluwer Academic Publishers, 1991.
12. WIRTH, N.:     Algorithms + Data Structures = Programs, Prentice-Hall, 1976.
13. YEH, T. R., editor:    Applied Computation Theory: Analysis, Design, Modeling, Prentice-Hall, 1976.