Title:

Formal Languages and Compilers

Code:IFJ
Ac.Year:2010/2011
Term:Winter
Curriculums:
ProgrammeBranchYearDuty
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:Č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: 
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:
 
  • 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.
  • Context-free languages and their models: context-free grammars and pushdown automata.
  • Syntax analysis: deterministic syntax analysis, FIRST and FOLLOW, LL and LR grammars.
  • Deterministic top-down syntax analysis: recursive descent.
  • Deterministic bottom-up 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.