02JEUOV

A.A. 2021/22

2021/22

Formal languages and 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 formal languages (compilers).

Formal languages and 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, highlighting its common use in many computer science and computer engineering disciplines, and to deepen the main application of this theory in the Computer field, that is the design and implementation of translators for formal languages (compilers).

Formal languages and 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 formal languages, by means of scanner and parser generators

Formal languages and 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, and of the main related algorithms - Skill to represent a given language by means of grammars and automata and to solve simple problems about languages - 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 formal languages, by means of scanner and parser generators

Formal languages and compilers

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 and compilers

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 the Java language

Formal languages and compilers

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 and compilers

Formal Languages (18 hours): - Classification - Regular languages (Regular grammars, Regular expressions, Finite state automata) and their application - Context-free languages (Context-free grammars, Pushdown automata, LR(k) grammars, LL(k) grammars) and their application - Turing machines and their application Compilers (42 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 and compilers

This course has many practical and theoretical implications on a number of computer engineering activities, not only related to programming languages and compilers. On the one hand, formal languages and automata theory are the foundations of many applications such as formal verification, intrusion detection, modeling, etc. On the other hand, compilers and translators are used today inside many software applications, especially those using domain-specific languages to manage their operation. Examples are simulators, robotics and quantum computing applications, and all applications providing Command Line Interfaces (CLI).

Formal languages and compilers

This course has many practical and theoretical implications on a number of computer engineering activities, not only related to programming languages and compilers. On the one hand, formal languages and automata theory are the foundations of many applications such as formal verification, intrusion detection, modeling, etc. On the other hand, compilers and translators are used today inside many software applications, especially those using domain-specific languages to manage their operation. Examples are simulators, robotics and quantum computing applications, and all applications providing Command Line Interfaces (CLI).

Formal languages and compilers

Lectures (39 hours): - Formal Languages (15 hours) - Compilers (24 hours) Classroom practice (10.5 hours): - Generation of lexical analyzers by means of JFlex - Generation of syntax-directed translators by means of Cup Laboratory practice (10.5 hours): - Implementation of compiler components by means of JFlex and Cup

Formal languages and compilers

Lectures (39 hours): - Formal Languages (18 hours) - Compilers (21 hours) Classroom practice (10.5 hours): - Generation of lexical analyzers by means of JFlex - Generation of syntax-directed translators by means of Cup Laboratory practice (10.5 hours): - Implementation of compiler components by means of JFlex and Cup

Formal languages and compilers

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.

Formal languages and compilers

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.

Formal languages and compilers

**Modalità di esame:** Prova scritta (in aula); Prova orale facoltativa; Prova pratica di laboratorio;

Formal languages and compilers

**Exam:** Written test; Optional oral exam; Practical lab skills test;

Formal languages and compilers

Two written examinations have to be passed, also in different calls of the same academic year. The first test, lasting 40 minutes, is about the topics presented in the lectures. Its aim is to check that the student has acquired the expected knowledge (see expected learning outcomes). It consists of open and close questions as well as short exercises. No material can be consulted during this test. The second test, lasting 80 minutes, aims at checking that the student has acquired the expected skills (see expected learning outcomes). It consists in the development of a translator using JFlex and Cup in the Lab. Any kind of material can be consulted during this test, but access to the internet is forbidden during the 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. The students have the possibility to request the assignment of a project which substitutes the second test.

Gli studenti e le studentesse con disabilità o con Disturbi Specifici di Apprendimento (DSA), oltre alla segnalazione tramite procedura informatizzata, sono invitati a comunicare anche direttamente al/la docente titolare dell'insegnamento, con un preavviso non inferiore ad una settimana dall'avvio della sessione d'esame, gli strumenti compensativi concordati con l'Unità Special Needs, al fine di permettere al/la docente la declinazione più idonea in riferimento alla specifica tipologia di esame.

Formal languages and compilers

**Exam:** Written test; Optional oral exam; Practical lab skills test;

Formal languages and compilers

Two written examinations have to be passed, also in different calls of the same academic year. The theory test, lasting 40 minutes, is about the topics presented in the lectures. Its aim is to check that the student has acquired the expected knowledge (see expected learning outcomes). It consists of open and closed questions as well as short exercises. No material can be consulted during this test and use of any electronic device is forbidden. The practice test, lasting 90 minutes, aims at checking that the student has acquired the expected skills (see expected learning outcomes). It consists in the development of a translator using JFlex and Cup in the Lab. Any kind of material can be consulted during this test, but access to the internet is forbidden during the test. After the end of the practice test, each participant must produce a complete and running version of their program, and send it to the lecturer within 3 working days. The final mark is the arithmetic mean of the marks of both tests (the two test are equally weighted and both marks are expressed in the range 0-30 with the possibility of laude). Laude in the final mark is assigned if both tests have been passed with laude or if one has been passed with laude and the other one with 30. An oral exam will be requested by the teachers only in case of doubts about the evaluation of the theory or practice test. The oral exam will consist of extra questions or exercises aiming at resolving the doubts the teachers had in the evaluation. The students have the possibility to request the assignment of a project which substitutes the practice test.

Gli studenti e le studentesse con disabilità o con Disturbi Specifici di Apprendimento (DSA), oltre alla segnalazione tramite procedura informatizzata, sono invitati a comunicare anche direttamente al/la docente titolare dell'insegnamento, con un preavviso non inferiore ad una settimana dall'avvio della sessione d'esame, gli strumenti compensativi concordati con l'Unità Special Needs, al fine di permettere al/la docente la declinazione più idonea in riferimento alla specifica tipologia di esame.

Formal languages and compilers

**Modalità di esame:** Prova orale facoltativa; Prova scritta su carta con videosorveglianza dei docenti; Prova scritta tramite l'utilizzo di vLAIB e piattaforma di ateneo;

Formal languages and compilers

Two written examinations have to be passed, also in different calls of the same academic year. The first test (theory), lasting 30 minutes, is about the topics presented in the lectures. Its aim is to check that the student has acquired the expected knowledge (see expected learning outcomes). It consists of open and closed questions as well as short exercises. No material can be consulted during this test. The second test (practice), lasting 90 minutes, aims at checking that the student has acquired the expected skills (see expected learning outcomes). It consists in the development of a translator using JFlex and Cup in a vLAIB virtual machine. For this second test, course material will be available in the vLAIB machine itself, including copy of slides, examples etc, while the internet will not be accessible. After the end of the practice test, each participant must produce a complete and running version of their program, and send it to the lecturer within 3 working days. The final mark is the arithmetic mean of the marks of both tests. In case of doubts about the evaluation of one or both of the tests, an oral exam can be requested. The students have the possibility to request the assignment of a project which substitutes the practice test.

Formal languages and compilers

**Exam:** Optional oral exam; Paper-based written test with video surveillance of the teaching staff; Written test via vLAIB using the PoliTo platform;

Formal languages and compilers

Two written examinations have to be passed, also in different calls of the same academic year. The theory test, lasting 30 minutes, is about the topics presented in the lectures. Its aim is to check that the student has acquired the expected knowledge (see expected learning outcomes). It consists of open and closed questions as well as short exercises. No material can be consulted during this test. The practice test, lasting 90 minutes, aims at checking that the student has acquired the expected skills (see expected learning outcomes). It consists in the development of a translator using JFlex and Cup in a vLAIB virtual machine. For this second test, course material will be available in the vLAIB machine itself, including copy of slides, examples, etc, while the internet will not be accessible. After the end of the practice test, each participant must produce a complete and running version of their program, and send it to the lecturer within 3 working days. The final mark is the arithmetic mean of the marks of both tests (the two test are equally weighted and both marks are expressed in the range 0-30 with the possibility of laude). Laude in the final mark is assigned if both tests have been passed with laude or if one has been passed with laude and the other one with 30. An oral exam will be requested by the teachers only in case of doubts about the evaluation of the theory or practice test. The oral exam will consist of extra questions or exercises aiming at resolving the doubts the teachers had in the evaluation. The students have the possibility to request the assignment of a project which substitutes the practice test.

Formal languages and compilers

**Modalità di esame:** Prova scritta (in aula); Prova orale facoltativa; Prova scritta su carta con videosorveglianza dei docenti; Prova scritta tramite l'utilizzo di vLAIB e piattaforma di ateneo;

Formal languages and compilers

The students can choose between the online exam (see previous description) and the onsite exam. In the onsite exam, the two tests are the same as in the online exam, but they take place at Labinf. During the practice test, any kind of material can be consulted but access to the internet and use of any personal electronic device is forbidden.

Formal languages and compilers

**Exam:** Written test; Optional oral exam; Paper-based written test with video surveillance of the teaching staff; Written test via vLAIB using the PoliTo platform;

Formal languages and compilers

If admitted to the blended exam, the students can choose between the online exam and the onsite exam (see previous descriptions) . In the onsite exam, the two tests are the same as in the online exam, but they take place in the Lab.

© Politecnico di Torino

Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY

Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY