Title:  Formal Languages and Compilers 

Code:  IFJe 

Ac.Year:  2016/2017 

Term:  Winter 

Curriculums:  

Language:  English 

Public info:  http://www.fit.vutbr.cz/study/courses/IFJe/public/ 

Credits:  5 

Completion:  accreditation+exam (written) 

Type of instruction:  Hour/sem  Lectures  Sem. Exercises  Lab. exercises  Comp. exercises  Other 

Hours:  26  13  0  0  13 

 Examination  Tests  Exercises  Laboratories  Other 

Points:  55  20  0  0  25 



Guarantee:  Meduna Alexander, prof. RNDr., CSc., DIFS 

Lecturer:  Soukup Ondřej, Ing., DIFS 
Instructor:  Krčmář Radim, Ing., DIFS Soukup Ondřej, Ing., DIFS 

Faculty:  Faculty of Information Technology BUT 

Department:  Department of Information Systems FIT BUT 

Prerequisites:  

Followups:  


Learning objectives: 

  Familiarity with formal languages and their models. Grasp of compiler construction. 
Description: 

  This course discusses formal languages and their models. Based on these models, it explains the construction of compilers. The lectures are organized as follows: (I) Basic notions: formal languages and their models, grammars, automata; compilers. (II) Regular languages and lexical analysis: regular languages and expressions, finite automata, lexical analyzer; symbol table. (III) Contextfree languages and syntax analysis: contextfree grammars, pushdown automata, deterministic topdown syntax analysis (recursive descent), the essence of deterministic bottomup syntax analysis. (IV) Semantic analysis and code generation: intermediate code generation, optimization, code generation. 
Knowledge and skills required for the course: 

  Discrete mathematics. 
Learning outcomes and competences: 

  Fundamental familiarity with the theory of formal languages. Ability of a compiler construction. 
Syllabus of lectures: 


 Basics of formal languages: alphabet, strings, languages.
 Introduction to compiler design: structure of a compiler.
 Regular languages and their models: regular expressions, finite automata.
 Variants of finite automata.
 Lexical analysis: lexical analyzer, symbol table.
 Contextfree languages and their models: contextfree grammars, pushdown automata.
 Pushdown automata and general parsing.
 Deterministic topdown syntax analysis: recursive descent.
 Deterministic bottomup syntax analysis: simple precedence analysis.
 Chomsky hierarchy and the corresponding models. Remarks and summary.

Fundamental literature: 


 Parsons, T. W.: Introduction to Compiler Construction. Freeman, New York, 1992.

Study literature: 


 Copy of lectures.
 Meduna, A.: Automata and Languages. London, Springer, 2000.

Controlled instruction: 

  Midterm. Checking the project solution by the teacher. 
Exam prerequisites: 

  To be allowed to take the final exam, the student has to obtain 20 points during the semester; out of these 20 points, at least five points have to be obtained from the project. 
