Formal Languages and Compilers -- A.Y. 2019/2020

Free University of Bozen-Bolzano
Faculty of Computer Science
Bachelor in Computer Science (BSc)

This page contains the material relevant to Formal Languages and Compilers (academic Year: 2019/20 -- Second Semester) module including lecture handouts and practical material. All enquiries regarding the module should be addressed to Prof. Alessandro Artale.
The course has also a practical aspect with Lab exercises concerning the construction of a compiler for a sub-language of the "C" programming language.

Exam Procedure after COVID
To limit the number of written exams, for the students who did not pass the Mid-Term exam on the Formal Language part, there will be an oral exam after the evaluation of both the Project and the written exam on the Compiler part of the course.
To be admitted to the oral exam students must have reached a pass mark in both the Project and the written Compiler exam.

Course Syllabus

1. Introduction to Compilers
2. Formal Languages Theory: Grammars and Language Classification
3. Normal Form and Properties of CFL's by J. Ullman
3.1 Normal Form for CFL's: Iterative Algorithms
4. Regular Languages and Finite Automata
4.1 Introduction to Finite Automata by J. Ullman
4.2 Non-Deterministic Finite Automata by J. Ullman
4.3 Notes on DFA State Minimization
4.4 Properties of Regular Languages by J. Ullman
4.5 Notes on Pumping Lemma
5. Parse Trees and Ambiguous Grammars
6. Lexical Analysis
7.1. Syntactic Analysis---Part 1
7.2. Syntactic Analysis---Part 2
7.3. Syntactic Analysis---Part 3
7.4. Syntactic Analysis---Part 4
8. Semantic Analysis Formalism: Syntax Directed Translation
9. Semantic Analysis: Type Checking and Symbol Table
10. Intermediate Code Generation

1. Introduction to C
2. Introduction to LEX
3. Introduction to YACC

LAB Exercises
1. Exercises on Grammars
2. Exercises on CFGs and Clean-Up Form
3. Exercises on Regular Expressions and Automata
4. Exercises on Regular Expressions and Automata
5. Exercises on Parser Algorithms
6.1 Exercise: Lexical analizer
6.2 Lexical analizer code
7.1 Calculator: LEX, YACC, Patch for Ubuntu and Makefile
7.2 Calculator with file input LEX, YACC, Input-File and Makefile
7.3 Calculator Ambiguous + Debugger YACC, Makefile

Past Exam Paper - Compilers
1.1 Past Exam Paper - Compilers
1.2 Past Exam Paper - Compilers
1.3 Past Exam Paper - Compilers

PROJECT -- 30% of the Final Mark
Students will be involved in a project concerning the development of a Compiler. Students should form teams of 2/3 people and decide the language to implement.
Guidelines for the Project
The deadline to email the project is: Friday 28th August, 2020.

The project presentation will be held online in the FLC Tams on Monday 31st August, 2020 starting at 10:00am.
To be included in the Project Presentation add your name to the following schedule file.

MID-TERM Exam on Formal Languages: 21.04.20 @ 16:00
Topics of the Mid-Term exam are: Formal Language Theory, Notions of Grammar and Derivation, Context-Free-Languages and Context-Free-Grammars, Normal Forms for CFLs, Regular Languages and Regular Expressions, Determinist and Non-deterministic Finite Automata, Parse Trees and Ambiguous Grammars.

Students who pass the mid-term exam can avoid the part of the final exam concerning Formal Languages.

Mid-Term exam: Results.

1. Past MidTerm Exam (Solution)
2. Past MidTerm Exam (Solution)
3. Past MidTerm Exam

FINAL Exam: 24.June.2020
Final Exam: Results