logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2017/2018
Scuola Scuola di Ingegneria Industriale e dell'Informazione
Insegnamento 089182 - FORMAL LANGUAGES AND COMPILERS
Docente Breveglieri Luca Oddone
Cfu 5.00 Tipo insegnamento Monodisciplinare

Corso di Studi Codice Piano di Studio preventivamente approvato Da (compreso) A (escluso) Insegnamento
Ing - Civ (Mag.)(ord. 270) - MI (495) GEOINFORMATICS ENGINEERING - INGEGNERIA GEOINFORMATICA*AZZZZ051890 - FORMAL LANGUAGES AND COMPILERS AND EMBEDDED SYSTEMS 1
089182 - FORMAL LANGUAGES AND COMPILERS
Ing Ind - Inf (Mag.)(ord. 270) - MI (481) COMPUTER SCIENCE AND ENGINEERING - INGEGNERIA INFORMATICA*AM089182 - FORMAL LANGUAGES AND COMPILERS

Programma dettagliato e risultati di apprendimento attesi

Course target

 

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, used for compilation.

 

Detailed programme of lecture classes

  1. 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.
  2. 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 Early parsing algorithm.
  3. Syntax-driven translation, direct and inverse translation, language homomorphim and substitution,
    syntactic translation schemata, transducer automata, and syntactic analysis and translation.
  4. 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.
  5. Static flow analysis of programs.

 

Detailed programme of exercise classes

  1. Modelisation of the lexicon and the syntax of a simple programming language (C-like).
  2. Design of a compiler for translation into an intemediate executable machine language (for a register-based processor).
  3. Use of the automated programming tools Flex and Bison for the construction of syntax-driven
    lexical and syntactic analysers and translators.

 

Course prequisites 

  1. Notions of theoretical computer science: theory of automata, predicate calculus (order zero and one),
    recursion theory and decidability, and computational complexity.
  2. Notions of the theory of algorithms and data structures.
  3. 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).

Note Sulla 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).


Bibliografia
Risorsa bibliografica obbligatoriaStefano 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-3
Risorsa bibliografica facoltativaStefano 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


Mix Forme Didattiche
Tipo Forma Didattica Ore didattiche
lezione
34.0
esercitazione
18.0
laboratorio informatico
0.0
laboratorio sperimentale
0.0
progetto
0.0
laboratorio di progetto
0.0

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
schedaincarico v. 1.6.2 / 1.6.2
Area Servizi ICT
04/06/2020