Formal Languages and Compilers
|Hour/sem||Lectures||Sem. Exercises||Lab. exercises||Comp. exercises||Other|
|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|
| || ||Familiarity with formal languages and their models. Grasp of compiler construction.|
| || ||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.
- 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).|
- Parsons, T. W.: Introduction to Compiler Construction. Freeman, New York, 1992.
- copy of lectures
- Meduna, A.: Automata and Languages. London, Springer, 2000.
- Meduna, A.: Elements of Compiler Design. New York, US, Tailor & Francis, 2008.
| || ||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).|
| || |
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.
| || ||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.|