Unit FORMAL LANGUAGES AND COMPILERS
- Course
- Informatics
- Study-unit Code
- 55067206
- Curriculum
- In all curricula
- Teacher
- Arturo Carpi
- Teachers
-
- Arturo Carpi
- Hours
- 42 ore - Arturo Carpi
- CFU
- 6
- Course Regulation
- Coorte 2021
- Offered
- 2022/23
- Learning activities
- Base
- Area
- Formazione informatica di base
- Academic discipline
- INF/01
- Type of study-unit
- Obbligatorio (Required)
- Type of learning activities
- Attività formativa monodisciplinare
- Language of instruction
- Italian
- Contents
- Phases of compiling
Finite state automata, regular languages, right-linear grammars, pumping lemma lexical analyzers.
Context-free grammars, ambiguous grammars, normal forms, pushdown automata, parsing algorithms.
Chomsky hyerarchy.
Semantic analysis: outline. - Reference texts
- J. Hopcroft, R. Motwani, J. Ullman, Automi, linguaggi e calcolabilità, Pearson, 2009
A.V. Aho, R. Sethi, J.D. Ullman, Compilers. Principles, Techniques and Tools, Addison Wesley, 1988
D. Grune, C.J.H. Jacobs, Parsing techniques, Springer, 2008 (1. edizione disponibile on line)
A. de Luca, F.D'Alessandro, Teoria degli Automi Finiti, Springer, 2013 - Educational objectives
- The main knowledges acquired with this course will concern:
fundamentals of formal language theory
understanding of formal syntactical and semantical aspects of programming languages
behaviour of interpreters and compilers.
The course will give to the student the ability of designing lexical and syntactical analyzers for simple programming languages. - Prerequisites
- In order to attend the course, the student should have some basic knowledge of Discrete Mathematics and, in particular, the notions of function, relation, equivalence, order set, semigroup, graph.
Moreover, it would be useful to know the most simple algorithms on directed graphs (accessibility, connection checking, etc.) - Teaching methods
- Lectures
- Other information
- -
- Learning verification modality
- The final evaluation consists in a written and an oral exam.
The written exam has a maximal duration of 90 minutes.. It consists in the solution of four algorithmic/computational problems. It is aimed at verifying the student ability in applying the knowledge acquired in the course for the solution of practical problems.
The oral exam is a discussion of the average duration of 30 minutes. It is aimed at verifying the actual understanding of the theoretical contents of the course, as well as the knowledge level of the arguments of the syllabus. Moreover, this test will allow to verify the public speaking ability of the student, in particular with the use of an adequate technical language.
The written exam has a validity of 12 months. After this period, a student who has not completed the evaluation will have to give again both written and oral exam.
On student request, exam may be given in English or French. - Extended program
- Preliminaries on programming languages and compilers, examples, problems
Alphabet, words, languages, grammars, operations on languages
Lexical analysis: finite state automata, deterministic and non deterministic model, regular languages and Kleene's theorem, minimal automaton and Myhill-Nerode theorem, right linear grammars, pumping lemma, lexical analyzers, closure properties of regular languages.
Sintactycal analysis: context-free grammars, ambiguous grammars and inherently ambiguous languages, pumping lemma for context-free languages, Chomsky and Greibach normal forms, pushdown automata, accepting by empty stack or final state, characterization of context-free languages by means of pushdown automata, algorithm CYK, predictive parsing, grammars LL(1).
Chomsky hyerarchy: context-sensitive asnd monotonic languages, recursive and recursively enumerable languages.
Semantic analysis: outline