logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2019/2020
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*AZZZZ089182 - FORMAL LANGUAGES AND COMPILERS
051890 - FORMAL LANGUAGES AND COMPILERS AND EMBEDDED SYSTEMS 1
Ing Ind - Inf (Mag.)(ord. 270) - MI (263) MUSIC AND ACOUSTIC ENGINEERING*AM089182 - FORMAL LANGUAGES AND COMPILERS
Ing Ind - Inf (Mag.)(ord. 270) - MI (481) COMPUTER SCIENCE AND ENGINEERING - INGEGNERIA INFORMATICA*AM089182 - 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

  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 Earley 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.

Prerequisiti
  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).

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
Risorsa bibliografica obbligatoriaStefano Crespi Reghizzi, Luca Breveglieri, Angelo Morzenti, Formal Languages and Compilation, Editore: Spinger, Anno edizione: 2019, ISBN: 978-3-030-04878-5 https://link.springer.com/book/10.1007/978-3-030-04879-2#toc
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


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
schedaincarico v. 1.6.1 / 1.6.1
Area Servizi ICT
22/02/2020