Title:

Formal Languages and Compilers

Code:IFJ
Ac.Year:2017/2018
Term:Winter
Curriculums:
ProgrammeBranchYearDuty
IT-BC-1HBCH-Recommended
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:Handlíř Jaroslav, Ing., DIFS
Kocman Radim, Ing., DIFS
Křena Bohuslav, Ing., Ph.D., DITS
Křivka Zbyněk, Ing., Ph.D., DIFS
Martiško Jakub, Ing., DIFS
Milkovič Marek, 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.
Monexam - řádná2018-01-08D10515:0017:502BIA
Monexam - řádná2018-01-08D10515:0017:502BIB
Monexam - řádná2018-01-08D10515:0017:503BIT
Monexam - řádná2018-01-08D020615:0017:502BIA
Monexam - řádná2018-01-08D020615:0017:502BIB
Monexam - řádná2018-01-08D020615:0017:503BIT
Monexam - řádná2018-01-08D020715:0017:502BIA
Monexam - řádná2018-01-08D020715:0017:502BIB
Monexam - řádná2018-01-08D020715:0017:503BIT
Monexam - řádná2018-01-08E11215:0017:502BIA
Monexam - řádná2018-01-08E11215:0017:502BIB
Monexam - řádná2018-01-08E11215:0017:503BIT
Monexam - řádná2018-01-08E10415:0017:502BIA
Monexam - řádná2018-01-08E10515:0017:502BIB
Monexam - řádná2018-01-08A11215:0017:502BIA
Monexam - řádná2018-01-08A11315:0017:502BIB
Tueexam - 2. oprava2018-01-30D10515:0017:502BIA
Tueexam - 2. oprava2018-01-30D10515:0017:502BIB
Tueexam - 2. oprava2018-01-30D10515:0017:503BIT
Thuexam - 1. oprava2018-01-18D10510:0012:502BIA
Thuexam - 1. oprava2018-01-18D10510:0012:502BIB
Thuexam - 1. oprava2018-01-18D10510:0012:503BIT
Thuexam - 1. oprava2018-01-18D020610:0012:502BIA
Thuexam - 1. oprava2018-01-18D020610:0012:502BIB
Thuexam - 1. oprava2018-01-18D020610:0012:503BIT
Thuexam - 1. oprava2018-01-18D020710:0012:502BIA
Thuexam - 1. oprava2018-01-18D020710:0012:502BIB
Thuexam - 1. oprava2018-01-18D020710:0012:503BIT
Thuexercise - Demonstrační cvičení2017-10-19D10517:0018:502BIA
Thuexercise - Demonstrační cvičení2017-10-19D10517:0018:502BIB
 
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: semantic checks, intermediate code generation, optimization, code generation.
Knowledge and skills required for the course:
  Knowledge of 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 grammars.
  • Deterministic top-down syntax analysis: recursive descent.
  • Deterministic bottom-up syntax analysis: simple precedence analysis; Yacc.
  • Semantic analysis and intermediate form generation.
  • Optimization.
  • Code generation.
  • Chomsky hierarchy and the corresponding models.
  • Remarks and summary. Preliminary discussion of the VYPe contents.
Syllabus - others, projects and individual work of students:
 Students in teams (3 through 4 students per a team) implement a compiler/interpreter of a simple programming language (including a documentation).
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.
  • Meduna, A.: Elements of Compiler Design. New York, US, Tailor & Francis, 2008.
Controlled instruction:
  The midterm test takes place approximately in the middle of the semester without a spare or correction term (20 points). To apply theoretical knowledge, students work on a team project (25 points). Continuously, the team leader checks team's progress. Finally, there is a final exam with two correction terms (55 points).
Progress assessment:
  
There is a midterm test for 20 points without a spare or correction term. Students solve one team project during the semester (25 points) that is handed over before given deadline.
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 four points has to be obtained for the programming part of the project.