Title:  Formal Languages and Compilers 

Code:  IFJe 

Ac.Year:  2013/2014 

Sem:  Winter 

Curriculums:  

Language of Instruction:  English 

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

Credits:  5 

Completion:  credit+exam (written) 

Type of instruction:  Hour/sem  Lectures  Seminar Exercises  Laboratory Exercises  Computer Exercises  Other 

Hours:  26  13  0  0  13 

 Exams  Tests  Exercises  Laboratories  Other 

Points:  55  20  0  0  25 



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

Lecturer:  Soukup Ondřej, Ing. (FIT) Vrábel Lukáš, Ing. (DIFS) Zemek Petr, Ing. (DIFS) 
Instructor:  Belal Alkomiet (DIFS) Soukup Ondřej, Ing. (FIT) Vrábel Lukáš, Ing. (DIFS) Zemek Petr, Ing. (DIFS) 

Faculty:  Faculty of Information Technology BUT 

Department:  Department of Information Systems FIT BUT 

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 competencies: 

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