Languages and Compilers
A.Y. 2024/2025
Learning objectives
The course aims to introduce the basic concepts related to lexical and syntactical analysis, and the interpretation techniques emerging in the context of formal languages. Grammar and algorithmic aspects are addressed, both from a theoretical point of view, and with particular regard to some case studies for which practical solutions, based on standard software tools, are presented.
Expected learning outcomes
The students should be able to apply the concepts, techniques and tools shown in the lectures to the design and development of grammars and interpreters for simple languages. The student must fully understand and be able to discuss, with clear and appropriate language, his solutions and their possible criticalities, comparing them to other available solutions.
Lesson period: Second semester
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course can be attended as a single course.
Course syllabus and organization
Single session
Responsible
Lesson period
Second semester
Course syllabus
Regarding the general field of formal languages:
* basics: alphabet, language, grammar;
* Chomsky hierarchy, with particular reference to regular and context-free languages (and related normal forms);
* recognition and generation: derivations, ambiguities, syntactic trees;
* finite-state and stacked automata, deterministic and non-deterministic.
Regarding aspects related to translation:
* lexical analysis and token division: regular expressions, relationship with finite state automata;
* grammatical analysis and parsing: general non-directional techniques, general directional techniques (top-down and bottom-up), deterministic techniques (LL and LR);
* transpilers. interpreters and translators: basic notions, grammars with attributes, general patterns.
* basics: alphabet, language, grammar;
* Chomsky hierarchy, with particular reference to regular and context-free languages (and related normal forms);
* recognition and generation: derivations, ambiguities, syntactic trees;
* finite-state and stacked automata, deterministic and non-deterministic.
Regarding aspects related to translation:
* lexical analysis and token division: regular expressions, relationship with finite state automata;
* grammatical analysis and parsing: general non-directional techniques, general directional techniques (top-down and bottom-up), deterministic techniques (LL and LR);
* transpilers. interpreters and translators: basic notions, grammars with attributes, general patterns.
Prerequisites for admission
Here is some preliminary knowledge that it is good to have acquired in a solid way before attending the lessons:
* demonstration techniques, with particular regard to that by induction,
* programming, with particular regard to recursion,
* elementary data structures (lists, stacks, queues and dictionaries); graphs and trees and related visit algorithms (width, depth ...),
* basic aspects of formal languages.
* demonstration techniques, with particular regard to that by induction,
* programming, with particular regard to recursion,
* elementary data structures (lists, stacks, queues and dictionaries); graphs and trees and related visit algorithms (width, depth ...),
* basic aspects of formal languages.
Teaching methods
Lectures. Attendance is recommended.
Teaching Resources
Course textbooks are:
* Dick Grune and Ceriel J. H. Jacobs (2008), Parsing Techniques. A Practical Guide, Springer, New York;
* Torben Ægidius Mogensen (2017), Introduction to Compiler Design, Springer International Publishing AG.
* Terence Parr (2009), Language Implementation Patterns, The Pragmatic Bookshelf.
A reference text for formal languages, useful as an in-depth analysis, is the classic:
* John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman (2007), Introduction to Automata Theory, Languages, and Computation, Pearson.
* Dick Grune and Ceriel J. H. Jacobs (2008), Parsing Techniques. A Practical Guide, Springer, New York;
* Torben Ægidius Mogensen (2017), Introduction to Compiler Design, Springer International Publishing AG.
* Terence Parr (2009), Language Implementation Patterns, The Pragmatic Bookshelf.
A reference text for formal languages, useful as an in-depth analysis, is the classic:
* John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman (2007), Introduction to Automata Theory, Languages, and Computation, Pearson.
Assessment methods and Criteria
There are no ongoing tests. The final exam consists of an individual oral interview in that focuses on a software project developed by the student, in agreement with the teacher. During this interview, the candidate must demonstrate:
* knowledge of definitions and fundamental theoretical notions, and understanding of the functioning of the various lexical and syntactic analysis and translation algorithms;
* the ability to apply this knowledge to a simple concrete case, both in relation to grammatical and algorithmic aspects;
* the ability to use a tool for the automatic generation of analyzers and / or translators.
* knowledge of definitions and fundamental theoretical notions, and understanding of the functioning of the various lexical and syntactic analysis and translation algorithms;
* the ability to apply this knowledge to a simple concrete case, both in relation to grammatical and algorithmic aspects;
* the ability to use a tool for the automatic generation of analyzers and / or translators.
INF/01 - INFORMATICS - University credits: 6
Lessons: 48 hours
Professor:
Santini Massimo
Shifts:
Turno
Professor:
Santini MassimoProfessor(s)
Reception:
http://santini.dsi.unimi.it/d/ricevimento.html
room 5007, via Celoria, 18