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

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: 2020/21 -- 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.

SYLLABUS
Course Syllabus

LECTURES
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. Lexical Analysis
6.1. Syntactic Analysis---Part 1
6.2. Syntactic Analysis---Part 2
6.3. Syntactic Analysis---Part 3
6.4. Syntactic Analysis---Part 4
7. Semantic Analysis Formalism
8. Semantic Analysis: Type Checking and Symbol Table
9. Intermediate Code Generation

TUTORIALS for the LAB
1. Introduction to C
2. Introduction to LEX
3. Introduction to YACC

LAB Exercises
1. Exercises on Context Free Grammars
2. Exercises on CFGs and Clean-Up Form
3. Exercises on Regular Expressions and Automata
4. Exercises on Parser Algorithms
5. Exercises on Code for Flow of Control Statements
5.1 Exercise: Lexical analizer
5.2 Lexical analizer code
6.1 Calculator: LEX, YACC, Patch for Ubuntu and Makefile
6.2 Calculator with file input LEX, YACC, Input-File and Makefile
6.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: 18 June 2021

PROJECT PRESENTATION
The project presentation will be held online in the FL&C TEAMS on 24th June 2021
To be included in the Project Presentation add your name to the following schedule file.

MID-TERM Exam on Formal Languages: 16 April 2021 @ 10: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: 9 February 2022.
Due to the online modality, the 9th of February there will be a 2 hours exam only on the Compilers part. For those who pass the Compilers part but need to pass also the Formal Language part, I will organise a mixed oral/written exam. The date of the FL exam will be agreed with the students. Remember that those missing the project should contact me to organise a project presentation before the exam. The exam will be done in the TEAMS platform. I will create a meeting in the TEAMS of the 2020/21 course. If you are not able to access the TEAMS let me know so I can invite you.

Final Exam: Results