81609 - Languages, Compilers and Computational Models

Learning outcomes

At the end of the course the student knows: - foundational aspects of logics, automata, regular expressions and grammars - techniques for the design and implementation, via compilers, of programming languages - languages, models and techniques for the description and property verification of concurrent and distributed software systems.

Course contents

Automata and formal languages:
- finite state automata
- regular expressions and their relationship with finite state automata
- context free grammars
- pushdown automata and their relationship with context free grammars
- Turing machines
- recursive and recursively enumerable languages and their relationship with Turing machines

Basic logic:
- propositional logic
- predicate logic

Compilers: 
- lexical analyzers 
- syntactic analyzers 
- static program checking 
- code generation 

Computational models:
- transition systems for the modeling of system behavior
- temporal logics for property specification and verification
- concurrent finite state processes with synchronization and interleaving
- Petri nets

Readings/Bibliography

Hopcroft, Motwani, Ullman. "Automi, Linguaggi e Calcolabilità", terza edizione. Addison-Wesley, 2009.

Aho, Lam, Sethi, Ullman. "Compilatori: principi, tecniche e strumenti", seconda edizione. Addison-Wesley, 2009.

Huth, Ryan. "Logic in Computer Science: Modelling and Reasoning about Systems", second edition. Cambridge University Press, 2004.

Teaching methods

Lectures with whiteboard/PC/beamer and experiences in laboratory.

As concerns the teaching methods of this course unit, all students must attend Module 1, 2 on Health and Safety online.

Assessment methods

The final examination is a written test with two kinds of questions:
- theoretical questions aiming at the verification of the assessment of the theoretical concepts;
- exercises aiming at the verification of the ability to apply the theoretical concepts on simple use-cases.

An optional additional project, that can be performed in groups of at most 4 students, is used to verify the ability of students to implement programming languages. Such a project consists in developing a compiler for a functional language with object orientation.

The written test allows the student to obtain a maximum mark of 27 over 30, which can be incremented (up to 7 additional points) by means of the project.  

Teaching tools

Whiteboard, PC, beamer, computer laboratory.

Office hours

See the website of Mario Bravetti