Title:

Formal Languages and Compilers

Code:IFJe
Ac.Year:2017/2018
Term:Winter
Curriculums:
ProgrammeBranchYearDuty
IT-BC-1HBCH-Recommended
IT-BC-3BIT2ndCompulsory
Language:English
News:
* This course is prepared for incoming Erasmus+ students only, and it is instructed in English.
* This course will be open if a certain/sure minimum of enrolled students is at least five students.

Public info:http://www.fit.vutbr.cz/study/courses/IFJe/public/
Credits:5
Completion:accreditation+exam (written)
Type of
instruction:
Hour/semLecturesSem. ExercisesLab. exercisesComp. exercisesOther
Hours:26130013
 ExaminationTestsExercisesLaboratoriesOther
Points:55200025
Guarantee:Meduna Alexander, prof. RNDr., CSc., DIFS
Lecturer:Charvát Lucie, Ing., DIFS
Krčmář Radim, Ing., DIFS
Instructor:Charvát Lucie, Ing., DIFS
Krčmář Radim, 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
Schedule:
DayLessonWeekRoomStartEndLect.Gr.St.G.EndG.
MonlecturelecturesC22814:0015:50INTE
MonexerciselecturesC22816:0016:50INTE
 
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, lexical analyzer; symbol table. (III) Context-free languages and syntax analysis: context-free grammars, pushdown automata, deterministic top-down syntax analysis (recursive descent), the essence of deterministic bottom-up syntax analysis. (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:
 
  • Basics of formal languages: alphabet, strings, languages.
  • Introduction to compiler design: structure of a compiler.
  • Regular languages and their models: regular expressions, finite automata.
  • Variants of finite automata.
  • Lexical analysis: lexical analyzer, symbol table.
  • Context-free languages and their models: context-free grammars, pushdown automata.
  • Pushdown automata and general parsing.
  • Deterministic top-down syntax analysis: recursive descent.
  • Deterministic bottom-up syntax analysis: simple precedence analysis.
  • Chomsky hierarchy and the corresponding models. Remarks and summary.
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.