logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2014/2015
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 Ind - Inf (Mag.)(ord. 270) - MI (434) INGEGNERIA INFORMATICA* AM089182 - 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 (a register-based processor, M68000-like).
  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, computational complexity.
  2. Notions of algorithm and data structure theory.
  3. Notions of programming and 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 (http://corsi.metid.polimi.it)
there are samples of exam proofs with solutions. An oral proof, optional, is reserved for the candidates who have obtained a high
grade in the written proof. 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

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
schedaincarico v. 1.6.1 / 1.6.1
Area Servizi ICT
19/11/2019