Title:  Formal Languages and Compilers 

Code:  IFJ 

Ac.Year:  2010/2011 

Term:  Winter 

Curriculums:  

Language:  Czech 

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

Credits:  5 

Completion:  accreditation+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 



Guarantee:  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. 
