Ing Ind - Inf (Mag.)(ord. 270) - CR (263) MUSIC AND ACOUSTIC ENGINEERING

*

M

ZZZZ

089182 - FORMAL LANGUAGES AND COMPILERS

Ing Ind - Inf (Mag.)(ord. 270) - MI (481) COMPUTER SCIENCE AND ENGINEERING - INGEGNERIA INFORMATICA

*

M

ZZZZ

089182 - FORMAL LANGUAGES AND COMPILERS

Obiettivi dell'insegnamento

The final objective of the course consists of learning the concepts, the algorithms and the automated tools that are used to define artificial languages and to translate them into other languages, that is, tools that are used for compilation.

Risultati di apprendimento attesi

Dublin descriptors

expected learning outcomes

knowledge and understanding

After successfully completing the course, the student:

knows the fundamental notions and models of artificial language, regular and context-free language, regular expression, finite and pushdown automaton, determinism and non-determinism, grammar (BNF and extended), syntax tree, ambiguity, and their relationships of equivalence and inclusion

knows the basic transformations of automata and grammars, for exposing determinism, eliminating redundancy and ambiguity, and normalizing automaton and grammar forms

knows the fundamental abstract syntactic structures of artificial languages: list, hierarchical list, nested block, expression and parenthetical structure

knows the notion of parsing an artificial language, the basic LR (bottom-up) and LL (top-down) LR deterministic parsing algorithms, their generalizations to an extended grammar (EBNF), their relations with language families, grammars and automata, and the general deterministic Early parsing algorithm

knows the fundamental notions of translation and semantic, syntax-directed translation, attribute grammar, static flow analysis, for defining the semantics of an artificial language

knows the fundamental operations and data structures of the compiler for a programming language: lexical and syntax analyzer and machine code generator, and symbol table and syntax tree

applying knowledge and understanding

After successfully completing the course, the student:

is able to transform regular expressions, grammars and automata, for exposing determinism, removing redundancy, ambiguity and errors, or normalizing them

is able to design regular expressions and grammars for modelling syntactic structures or a whole artificial language, starting from an informal description or a prerequisite list, and is able to add simple semantics to an artificial language by means of a syntax-directed scheme or an attribute grammar

is able to design a deterministic parser for an artificial language, of type (extended) LR, LL or Early, to use it to compute a syntax tree, and to autonomously design a simple code generator for compiling the language into low-level (machine or assembly) code, also by using the standard complier-design tools Flex and Bison

is able to autonomously design a simple semantic analyzer for an artificial language, based on the attribute grammar model

lifelong learning skills

After successfully completing the course, the student:

is able to autonomously understand and model the syntax and semantics of new artificial languages, in particular the programming ones

is able to autonomously understand and model the structure of a compiler for a new simple artificial language, with limited optimization, or for an extension of an existing one with new features

is able to contribute in bringing artificial language functionalities and technology into complex software systems and applications

Argomenti trattati

Detailed programme of lecture classes

Definition of language, theory of formal languages, regular expressions, context-free grammars, ambiguity, grammars of regular (rational) languages, syntax trees, properties of the families of regular (rational) and context-free languages, main syntactic structures and limitations of the context-free languages.

Analysis and recognition (parsing) of phrases, phrase recognition algorithms (parsing algorithms) and automata, finite deterministic and non-deterministic automata, pushdown automata, deterministic languages, ascending and recursive descending syntactic analysis, and Earley parsing algorithm.

Syntax-driven translation, direct and inverse translation, language homomorphim and substitution, syntactic translation schemata, transducer automata, and syntactic analysis and translation.

Semantic translation driven by syntax, semantic functions and attribute grammars, hints to compiler structure and design, examples of sematic check and translation, one-pass and multiple-pass computation of the attributes.

Static flow analysis of programs.

Detailed programme of exercise classes

Modelisation of the lexicon and the syntax of a simple programming language (C-like).

Design of a compiler for translation into an intemediate executable machine language (for a register-based processor).

Use of the automated programming tools Flex and Bison for the construction of syntax-driven lexical and syntactic analysers and translators.

Prerequisiti

Notions of theoretical computer science: theory of automata, predicate calculus (order zero and one), recursion theory and decidability, and computational complexity.

Notions of the theory of algorithms and data structures.

Notions of computer programming, and the knowledge of the C language (some skill is required in writing a new program and in extending an existing one).

Modalità di valutazione

The exam consists of a written proof, divided in two parts (theory and exercise - see above). On the course website (on the BeeP platform) there are samples of exam proofs with solutions. An oral proof, optional, is reserved, at the discretion of the teacher, for the candidates who have obtained a high grade in the written proof, or in cases when issues concerning the written exam need to be clarified. The written proof is open-book (textbook and personal notes allowed).

Type of assessment

Description

Dublin descriptor

Written test

Solution of numerical problems

· analyze the behaviour of a regular expression, a grammar or an automaton

Exercises focusing on design aspects

design grammars and automata for informally specified syntactic structures

design a syntax analyzer (LR, LL, Early, possibly extended) for simple grammars, and simulate its behaviour

design small parts of a translator or semantic analyzer, for simple grammars

update a prototypal compiler (modelled in C language) for a simple programming language (Java-like) and add to it syntactic and semantic features, to extend the language compiled

1,2

1, 2, 5

Bibliografia

Stefano Crespi Reghizzi, Luca Breveglieri, Angelo Morzenti, Formal Languages and Compilation, Editore: Spinger, Anno edizione: 2013, ISBN: 978-1-4471-5514-0 http://www.springer.com/computer/theoretical+computer+science/book/978-1-4471-5513-3Stefano Crespi Reghizzi, Luca Breveglieri, Angelo Morzenti, Linguaggi formali e compilazione Nuova edizione 2015, Editore: Esculapio, Anno edizione: 2015, ISBN: 978-88-7488-875-7 Note:

Italian version of the English textbook by the same authors

Software utilizzato

Nessun software richiesto

Forme didattiche

Tipo Forma Didattica

Ore di attività svolte in aula

(hh:mm)

Ore di studio autonome

(hh:mm)

Lezione

32:00

48:00

Esercitazione

18:00

27:00

Laboratorio Informatico

0:00

0:00

Laboratorio Sperimentale

0:00

0:00

Laboratorio Di Progetto

0:00

0:00

Totale

50:00

75:00

Informazioni in lingua inglese a supporto dell'internazionalizzazione

Insegnamento erogato in lingua
Inglese

Disponibilità di materiale didattico/slides in lingua inglese

Disponibilità di libri di testo/bibliografia in lingua inglese

Possibilità di sostenere l'esame in lingua inglese

Disponibilità di supporto didattico in lingua inglese