First cycle
degree courses
Second cycle
degree courses
Single cycle
degree courses
School of Engineering
COMPUTER ENGINEERING
Course unit
COMPILERS
INP6075737, A.A. 2019/20

Information concerning the students who enrolled in A.Y. 2018/19

Information on the course unit
Degree course Second cycle degree in
COMPUTER ENGINEERING
IN0521, Degree course structure A.Y. 2009/10, A.Y. 2019/20
N0
bring this page
with you
Number of ECTS credits allocated 6.0
Type of assessment Mark
Course unit English denomination COMPILERS
Department of reference Department of Information Engineering
E-Learning website https://elearning.dei.unipd.it/course/view.php?idnumber=2019-IN0521-000ZZ-2018-INP6075737-N0
Mandatory attendance No
Language of instruction Italian
Branch PADOVA
Single Course unit The Course unit can be attended under the option Single Course unit attendance
Optional Course unit The Course unit can be chosen as Optional Course unit

Lecturers
Teacher in charge GIORGIO SATTA ING-INF/05

ECTS: details
Type Scientific-Disciplinary Sector Credits allocated
Core courses ING-INF/05 Data Processing Systems 6.0

Course unit organization
Period Second semester
Year 2nd Year
Teaching method frontal

Type of hours Credits Teaching
hours
Hours of
Individual study
Shifts
Lecture 6.0 48 102.0 No turn

Calendar
Start of activities 02/03/2020
End of activities 12/06/2020
Show course schedule 2019/20 Reg.2009 course timetable

Examination board
Board From To Members of the board
3 A.A. 2019/2020 01/10/2019 15/03/2021 SATTA GIORGIO (Presidente)
MORO MICHELE (Membro Effettivo)
PIZZI CINZIA (Supplente)
2 A.A. 2018/2019 01/10/2018 15/03/2020 SATTA GIORGIO (Presidente)
MORO MICHELE (Membro Effettivo)
PIZZI CINZIA (Supplente)

Syllabus
Prerequisites: In order to be able to successfully attend this class, a good understanding is assumed for topics traditionally taught in a basic course on automata theory and formal languages: specifically, we require knowledge of regular expressions, finite state automata, context-free grammars and push-down automata. We also require basic knowledge of computer programming and procedural programming languages, in particular the programming language C. Finally, a general knowledge of most common algorithms and data structures is assumed, including trees and graphs.
Target skills and knowledge: This course has three main goals: (i) learning of technics for the translation from a high-level programming language into CPU instructions; (ii) development of skills for the design of a simple compiler; (iii) development of soft-skills needed for team-working.

More specifically, the knowledge to be acquired regards:
1. the techniques underlying the main functions of a compiler front-end: lexical, syntactic and semantic analysis
2. translation techniques guided by the syntactic structure
3. some techniques for static analysis of computer programs and for code optimization

Through the work in small groups for the design and the realisation of a mini-compiler, the student also develops the following technical skills and soft skills:
1. technical familiarity with practical tools (Flex and Bison) for the realisation of software translators
2. ability to identify solutions, based on the acquired knowledge (problem solving)
3. team-working skills

I would like to add a short comment on the motivations for studying compiler theory. First, this subject has a foundational role in the field of computer science: the theory of compilers is probably the most important scientific contribution to the development and dissemination of computer technology. Secondly, this subject presents important application perspectives. Even if the student will never be involved in his or her working career in the project of a new compiler (very few companies in the world deal with this task) it is highly probable that he/she will be using methodologies and techniques that are part of compiler theory: from automata and grammars as formalisms for defining the behaviour of a software system, to techniques for realising translators much simpler than a real compiler, such as the interpreters for a configuration file, for an interface language, or for a command language to an app or to any electronic device.
Examination methods: The verification of the acquired knowledge and the expected skills is carried out by means of two tests:
1. mandatory written test, consisting in questions concerning theoretical knowledge acquired during the course and exercises based on the application of translation techniques
2. mandatory project (groups of up to two people) involving the design of a simple high-level programming language and the realisation of a compiler for that language; the project is continuously followed by the teacher and is concluded with a final presentation and discussion
Assessment criteria: The evaluation criteria used to verify the acquired knowledge and skills at the final examination are:
1. completeness of theoretical knowledge
2. ability to solve translation problems

The criteria used during the intermediate and final presentations for the project evaluation, in order to verify the acquisition of technical skills and soft-skills required, are:
1. familiarity with the used tools
2. ability to develop and communicate ideas within the project
3. team working skill

For the overall evaluation, the active participation in the technical discussions on the electronic forum during the class will also be considered, as well as the merits acquired in the solution of the contests proposed during the class.
Course unit contents: Introduction: Programming languages and language processors. Machine languages, assembly language and evolution of programming languages. Compilers, interpreters, and virtual machine. Compiler structure and compilation steps. Front end and back end. Passes of a compiler.

Lexical analysis: Preliminary operations, tokens and lexemes. Regular expressions and regular definitions. Elimination of ambiguity. Finite state deterministic and non-deterministic automata, their implementation and simulation. Automatic generation of a lexical analyzer: the Flex tool.

Syntactic analysis: Context-free grammars, derivation trees and ambiguity. Deterministic and non-deterministic stack automata. Syntactic errors and error handling methods. Top-down parser: recursive descent parser and LL(1) parser. Elimination of left recursion; left factorisation, First and Follow sets. Bottom-up parser: shift-reduce parser, LR(0) items and SLR parser. Automatic generation of parser and translator: the Bison tool.

Semantic analysis: Static and dynamic semantics. Grammars with attributes. Syntax-directed translation. Annotated syntactic tree, attribute-value computation, and dependency graph. Grammars with S-attributes and grammars with L-attributes. Topological order of the dependency graph. Type checking, type equivalence and type coercion. Symbol table.

Code generation: Intermediate code and three-address code. Data structures for the implementation of the three-address code. Code generation for the most frequent programming constructs: definitions, arrays, if, while. Examples of machine-independent code optimization.
Planned learning activities and teaching methods: The class is delivered through frontal lessons using digital teaching material (text and video) distributed to students in advance of each meeting. There will also be intermediate meetings between the teacher and the working groups to guide the development of the assigned projects. In order to facilitate discussion, collaboration and self-assessment of the learning process by thestudents, two electronic forums supervised by the teacher are provided on the moodle platform, where theoretical aspects of compilers and, respectively, practical aspects of project development can be discussed. Finally, to encourage the active participation of students in the class and to motivate the students to keep updated with the topics, small contests are proposed by the teacher, which are awarded with bonuses that are taken into account in the final evaluation.
Additional notes about suggested reading: Class topics are covered by the reference textbook. Additional teaching material is also provided through the moodle platform, in the form of slides, handouts with exercises, and video by experts of compiler theory.
Textbooks (and optional supplementary readings)
  • A.V. Aho, M.S. Lam, R. Sethi, J.D. Ullman, Compilatori: Principi, tecniche e strumenti. --: Pearson Education Italia, 2009. seconda edizione Cerca nel catalogo

Innovative teaching methods: Teaching and learning strategies
  • Lecturing
  • Problem based learning
  • Working in group
  • Problem solving
  • Flipped classroom
  • Active quizzes for Concept Verification Tests and class discussions
  • Use of online videos
  • Loading of files and pages (web pages, Moodle, ...)

Innovative teaching methods: Software or applications used
  • Moodle (files, quizzes, workshops, ...)

Sustainable Development Goals (SDGs)
Quality Education