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

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