Title:

Formal Languages and Compilers

Code:IFJ
Ac.Year:2012/2013
Term:Winter
Study plans:
ProgramBranchYearDuty
IT-BC-3BIT2ndCompulsory
Language:Czech
Public info:http://www.fit.vutbr.cz/study/courses/IFJ/public/
Credits:5
Completion:accreditation+exam (written)
Type of
instruction:
Hour/semLecturesSem. ExercisesLab. exercisesComp. exercisesOther
Hours:3900013
 ExaminationTestsExercisesLaboratoriesOther
Points:55200025
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:Křena Bohuslav, Ing., Ph.D., DITS
Křivka Zbyněk, Ing., Ph.D., DIFS
Křoustek Jakub, Ing., DIFS
Solár Peter, Ing., DIFS
Vrábel Lukáš, Ing., DIFS
Zemek Petr, Ing., DIFS
Faculty:Faculty of Information Technology BUT
Department:Department of Information Systems FIT BUT
Prerequisites: 
Discrete Mathematics (IDA), DMAT
Follow-ups:
Principles of Programming Languages (IPP), DIFS
 
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) Context-free languages and syntax analysis: context-free grammars, pushdown automata and transducers, deterministic top-down syntax analysis (recursive descent), the essence of deterministic bottom-up 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:
  1. Formal languages.
  2. Translation of languages and the structure of a compiler.
  3. Regular languages and their models: regular expressions and finite automata.
  4. Lexical analysis: lexical analyzer; Lex; symbol table.
  5. Context-free languages and their models: context-free grammars and pushdown automata.
  6. Syntax analysis: deterministic syntax analysis, FIRST and FOLLOW, LL and LR grammars.
  7. Deterministic top-down syntax analysis: recursive descent.
  8. Deterministic bottom-up syntax analysis: simple precedence analysis, LR analysis; Yacc.
  9. Semantic analysis and intermediate form generation.
  10. Optimazation.
  11. Code generation.
  12. Chomsky hierarchy and the corresponding models.
  13. Remarks and summary. Preliminary discussion of the VYP contents.
Fundamental literature:
  1. Parsons, T. W.: Introduction to Compiler Construction. Freeman, New York, 1992.
Study literature:
  1. copy of lectures
  2. Meduna, A.: Automata and Languages. London, Springer, 2000.
  3. Meduna, A.: Elements of Compiler Design. New York, US, Tailor & Francis, 2008.
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.