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 2022
Offered
2023/24
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 hierarchy: context-sensitive and monotonic languages, recursive and recursively enumerable languages.
Semantic analysis: outline
Condividi su