Servizi per la didattica
PORTALE DELLA DIDATTICA

Formal languages and compilers

02JEUOV

A.A. 2018/19

Course Language

English

Course degree

Master of science-level of the Bologna process in Computer Engineering - Torino

Course structure
Teaching Hours
Lezioni 40
Esercitazioni in aula 10
Esercitazioni in laboratorio 10
Teachers
Teacher Status SSD h.Les h.Ex h.Lab h.Tut Years teaching
Rivoira Silvano Docente esterno e/o collaboratore   30 0 0 0 12
Teaching assistant
Espandi

Context
SSD CFU Activities Area context
ING-INF/05 6 B - Caratterizzanti Ingegneria informatica
The course is taught in English. This course is characterizing for the Software curriculum of the Master of Science in Computer Engineering, and it is held at the second semester of the first year. Its objectives are to introduce the basic elements of the theory of formal languages and to discuss their main application in the Computer field, that is the design of translators for programming languages (compilers).
The course is taught in English. This course is characterizing for the Software curriculum of the Master of Science in Computer Engineering, and it is held at the second semester of the first year. Its objectives are to introduce the basic elements of the theory of formal languages and to discuss their main application in the Computer field, that is the design of translators for programming languages (compilers).
-Knowledge of the properties of the different classes of formal languages (phrase-structure, context-sensitive, context-free, regular languages) - Knowledge of the properties of the different formalisms (grammars and automata) used to represent languages - Skill to represent a given language by means of grammars and automata - Knowledge of the phases composing the translation process of a programming language: lexical analysis, syntax analysis, semantic analysis, intermediate code generation, generation and optimization of the target code - Knowledge of the design techniques and tools available for the implementation of scanners (lexical analyzers), parsers (syntax analyzers), and syntax-directed translators - Skill to design and implement syntax-directed translators for programming languages, by means of scanner and parser generators
- Knowledge of the properties of the different classes of formal languages (phrase-structure, context-sensitive, context-free, regular languages) - Knowledge of the properties of the different formalisms (grammars and automata) used to represent languages - Skill to represent a given language by means of grammars and automata - Knowledge of the phases composing the translation process of a programming language: lexical analysis, syntax analysis, semantic analysis, intermediate code generation, generation and optimization of the target code - Knowledge of the design techniques and tools available for the implementation of scanners (lexical analyzers), parsers (syntax analyzers), and syntax-directed translators - Skill to design and implement syntax-directed translators for programming languages, by means of scanner and parser generators
The following knowledge is required: - Knowledge of basic concepts from the set theory: set operations, constructions and relations - Knowledge of the architecture of computer systems: processor structure and memory organization - Knowledge of the properties of programming languages and programming techniques - Knowledge of data structures (hash tables, trees, graphs) and their fundamental algorithms - Skill to develop programs in Java language
The following knowledge is required: - Knowledge of basic concepts from the set theory: set operations, constructions and relations - Knowledge of the architecture of computer systems: processor structure and memory organization - Knowledge of the properties of programming languages and programming techniques - Knowledge of data structures (hash tables, trees, graphs) and their fundamental algorithms - Skill to develop programs in Java language
Formal Languages (15 hours): - Classification - Regular languages (Regular grammars, Regular expressions, Finite state automata) - Context-free languages (Context-free grammars, Pushdown automata, LR(k) grammars, LL(k) grammars) - Turing machines Compilers (45 hours): - Compiler structure - Lexical analysis - Syntax analysis (Bottom-up analysis, Top-down analysis) - Syntax-directed translation (Attribute definitions, Bottom-up translators) - Semantic analysis and intermediate code generation (Type control, Intermediate languages, Analysis of declarations and instructions)
Formal Languages (15 hours): - Classification - Regular languages (Regular grammars, Regular expressions, Finite state automata) - Context-free languages (Context-free grammars, Pushdown automata, LR(k) grammars, LL(k) grammars) - Turing machines Compilers (45 hours): - Compiler structure - Lexical analysis - Syntax analysis (Bottom-up analysis, Top-down analysis) - Syntax-directed translation (Attribute definitions, Bottom-up translators) - Semantic analysis and intermediate code generation (Type control, Intermediate languages, Analysis of declarations and instructions)
Lectures (40 hours): - Formal Languages (15 hours) - Compilers (25 hours) Classroom practice (10 hours): - Generation of lexical analyzers by means of JFlex - Generation of syntax-directed translators by means of Cup Laboratory practice (10 hours): - Implementation of compiler components by means of JFlex e Cup
Lectures (40 hours): - Formal Languages (15 hours) - Compilers (25 hours) Classroom practice (10 hours): - Generation of lexical analyzers by means of JFlex - Generation of syntax-directed translators by means of Cup Laboratory practice (10 hours): - Implementation of compiler components by means of JFlex e Cup
Books: - J.E. Hopcroft, R. Motwani, J.D. Ullman - Introduction to Automata Theory, Languages, and Computation 3rd Edition, Pearson - Addison-Wesley, 2007 - A.V. Aho, M.S. Lam, R. Sethi, J.D. Ullman - Compilers: Principles, Techniques, and Tools, 2nd Edition, Pearson - Addison-Wesley, 2007 Materials available on the teaching Web site Slides used in classroom Video-recording of lectures and practice.
Books: - J.E. Hopcroft, R. Motwani, J.D. Ullman - Introduction to Automata Theory, Languages, and Computation 3rd Edition, Pearson - Addison-Wesley, 2007 - A.V. Aho, M.S. Lam, R. Sethi, J.D. Ullman - Compilers: Principles, Techniques, and Tools, 2nd Edition, Pearson - Addison-Wesley, 2007 Materials available on the teaching Web site Slides used in classroom Video-recording of lectures and practice.
Two written examinations have to be passed, also in different calls. The first test, lasting 40 minutes, is about the topics presented in the lectures. No material can be consulted during this test. The second test, lasting 80 minutes, consists in the development of a translator using JFlex and Cup. Any kind of material can be consulted during this test. Students must produce a complete and running version of their program after the second test, and send it to the lecturer within 3 working days. The final mark is the arithmetic mean of the marks of both tests.
Two written examinations have to be passed, also in different calls. The first test, lasting 40 minutes, is about the topics presented in the lectures. No material can be consulted during this test. The second test, lasting 80 minutes, consists in the development of a translator using JFlex and Cup. Any kind of material can be consulted during this test. Students must produce a complete and running version of their program after the second test, and send it to the lecturer within 3 working days. The final mark is the arithmetic mean of the marks of both tests.


© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
m@il