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

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

This page contains the material relevant to Formal Languages and Compilers (academic Year: 2017/18 -- First 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 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
11. Code Optimization
12. Run-Time Environment
12.1 Run-Time Environment (Addendum/Example)

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
3. Lecture 4: Exercice 1 YACC
4. Lecture 4: Exercice 2 YACC
5. Programming Languages Resources
6.1 Past Exam Paper - Formal Languages
6.2 Past Exam Paper - Formal Languages
6.3 Past Exam Paper - Formal Languages
7.1 Past Exam Paper - Compilers
7.2 Past Exam Paper - Compilers
7.3 Past Exam Paper - Compilers
7.4 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: To be fixed.

The project presentation will be held on: Room E331 on Thursday the 25th of January, 2018 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.November.2017
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