Home

Subject: Formal languages and interpreters
Course: Theory of translation and application
ECTS credits: 6
Language: Croatian/ English/ French
Duration: 1 semester
Status: elective
Method of teaching: 1 lecture hour – 1 hour of seminar – 2 hours of practical classes
Prerequisite: Syntax Analysis Theory and Application
Assessment: Written report defense

Course description:
Introduction. Programming languages: generations of programming languages, procedural and nonprocedural languages, defining programming languages, languages with properties. Introduction to translation: necessity for translators, translation steps, and types of translators. Lexical analysis: direct lexical analysis, indirect lexical analysis. Syntax analysis of programming languages: recursive top down syntax analysis, syntax analysis managed by the transition table and actions. Translations: interpreters and preprocessors.
Practical classes closely follow the lectures. All theoretical discussions and definitions are further explained with appropriate examples. As an example of a simple programming language, syntax and semantics of Wirth's PL/0 language will be shown. Direct lexical analysis and recursive top down syntax analysis will be shown using the program for computing the real expressions. Examples of interpreter will be shown through the realization of PL/0 language translators. Preprocessor will be shown through the language D (don-D program).
In written reports students are to write a preprocessor for chosen language.

Course objectives:
Basic knowledge of formal languages will be given with special interest in 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 • prevođenje, Zagreb, Zavod za informacijske studije, 2005.
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: FORMALNI JEZICI • sintaksna analiza, Zagreb, Zavod za informacijske studije, 2003.
5. DOVEDAN, Zdravko: don-grammar, program za definiranje i transformiranje beskontekstnih gramatika, Zagreb, Filozofski fakultet, 2003.
6. DOVEDAN, Zdravko: don-sintax, program za sintaksnu analizu beskontekstnih jezika, Zagreb, Filozofski fakultet, 2003.
7. DOVEDAN, Zdravko: don-D, pretprocesor jezika D, Zagreb, Filozofski fakultet, 2003.
8. DOVEDAN, Zdravko: Pascal i programiranje (1), Zagreb, don, 1995.
9. GRUNE, D.: Parsing Techniques – A Practical Guide, Ellis-Horwood, 1990.
10. HOPCROFT, E. J.; ULLMAN, D. J.: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.
11. KALUŽNIN, A. L.: Što je matematička logika,  Zagreb, Školska knjiga 1975.
12. KUREPA, Svetozar: Uvod u matematiku, Zagreb, Tehnička knjiga, 1970.
13. TOMITA, M., editor: Current Issues in Parsing Technology, Kluwer Academic Publishers, 1991.
14. WIRTH, N.:     Algorithms + Data Structures = Programs, Prentice-Hall, 1976.
15. YEH, T. R., editor:    Applied Computation Theory: Analysis, Design, Modeling, Prentice-Hall, 1976.