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

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: 2018/19 -- 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.

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 Properties of Regular Languages by J. Ullman
4.4 Notes on Pumping Lemma
4.5 Notes on DFA State Minimization
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.1 Exercise: Lexical analizer
1.2 Lexical analizer code
2.1 Calculator: LEX, YACC, Patch for Ubuntu and Makefile
2.2 Calculator with file input LEX, YACC, Input-File and Makefile
2.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.
The deadline to email the project is: Thursday, 20th of June, 2019.

The project presentation will be held in Room E220 on Monday the 24th of June, 2019 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: Monday 8.April.2019 @ 14: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
2. Past MidTerm Exam
3. Past MidTerm Exam