Title:  Formal Languages and Compilers 

Code:  IFJ 

Ac.Year:  2010/2011 

Term:  Winter 

Curriculums:  

Language of Instruction:  Czech 

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

Credits:  5 

Completion:  credit+exam (written) 

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

Hours:  39  0  0  0  13 

 Examination  Tests  Exercises  Laboratories  Other 

Points:  55  20  0  0  25 



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

Lecturer:  Burgetová Ivana, Ing., Ph.D., DIFS Křivka Zbyněk, Ing., Ph.D., DIFS Meduna Alexander, prof. RNDr., CSc., DIFS 
Instructor:  Čermák Martin, Ing., DIFS Koutný Jiří, Ing., DIFS Křena Bohuslav, Ing., Ph.D., DITS Křoustek Jakub, Ing., DIFS Solár Peter, Ing., DIFS Zemek Petr, 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 and transducers, lexical analyzer; Lex; symbol table. (III) Contextfree languages and syntax analysis: contextfree grammars, pushdown automata and transducers, deterministic topdown syntax analysis (recursive descent), the essence of deterministic bottomup syntax analysis; Yacc. (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: 


 Formal languages.
 Translation of languages and the structure of a compiler.
 Regular languages and their models: regular expressions and finite automata.
 Lexical analysis: lexical analyzer; Lex; symbol table.
 Contextfree languages and their models: contextfree grammars and pushdown automata.
 Syntax analysis: deterministic syntax analysis, FIRST and FOLLOW, LL and LR grammars.
 Deterministic topdown syntax analysis: recursive descent.
 Deterministic bottomup syntax analysis: simple precedence analysis, LR analysis; Yacc.
 Semantic analysis and intermediate form generation.
 Optimazation.
 Code generation.
 Chomsky hierarchy and the corresponding models.
 Remarks and summary. Preliminary discussion of the VYP contents.
 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 written exam, the student has to obtain 20 points during the semester; out of these 20 points, at least five points has to be obtained for the programming part of the project.  
