Course details
Formal Languages and Compilers
IFJ Acad. year 2007/2008 Winter semester 5 credits
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.
Guarantor
Language of instruction
Completion
Time span
- 39 hrs lectures
- 13 hrs projects
Department
Subject specific learning outcomes and competences
Fundamental familiarity with the theory of formal languages. Ability of a compiler construction.
Learning objectives
Familiarity with formal languages and their models. Grasp of compiler construction.
Prerequisite knowledge and skills
discrete mathematics
Study literature
- kopie přednášek (elektronické i papírové)
- Meduna, A.: Automata and Languages. London, Springer, 2000.
- Meduna, A.: Elements of Compiler Design. New York, US, Tailor & Francis, 2008.
Fundamental literature
- Parsons, T. W.: Introduction to Compiler Construction. Freeman, New York, 1992.
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.
Progress assessment
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.
Controlled instruction
Midterm. Checking the project solution by the teacher.