Compilers

Teacher:

• Luca Tesei

ESSE3 Link

• Compilers - AY 2019/2020

Lectures schedule:

• Wed 11am-1pm Room AB1 Polo Lodovici, Via Madonna delle Carceri 9, Camerino, from 19/11/2019 on: Tue 11am-1pm Room AB3 Polo Lodovici, Via Madonna delle Carceri 9, Camerino
• Thu 2pm-4pm Room AB1 Polo Lodovici, Via Madonna delle Carceri 9, Camerino

Webex Room for Lecture Streaming

• Luca Tesei's room

Office hours:

• Luca Tesei's office hours are specified here, look at the notices for any variation. The place is Luca Tesei's office, 1st floor, Polo Lodovici, via Madonna delle Carceri 9, Camerino.

Official Acronym:

• The official acronym of the course is CMP1920

See the ESSE3 Description

The course will delve into the following topics (for students convenience chapters in the textbook are indicated within parenthesis)

• General Introduction to Compilers construction [ALSU - Ch.1]
  • Structure of a compiler
  • Evolution of programming languages
  • Generalities on programming languages
• Lexical Analysis [ALSU - Ch.3]
  • Lexical analysis objectives and issues
  • Tokens, patterns, and lexemes
  • Regular expressions and definitions
  • Finite Automata
    • DFA - Deterministic Finite Automata
    • NFA - Non Deterministic Finite Automata
  • From RegExp to NFA
  • From NFA to DFA
  • DFA Minimization
  • Recongnition of tokens
• Syntax Analysis [ALSU - Ch.4]
  • Introduction to CF grammars and Push-Down automata
  • Parse tree and derivations
  • Ambiguity
  • Top-down parsing
    • Left recursion and left factoring
    • Recursive descent parsing
    • FIRST and FOLLOW sets
    • Non recursive predictive parsing
    • Error recovery in predictive parsing
  • Bottom-up parsing
    • Reductions, Handles
    • Shift-reduce parsing
    • LR(0) automaton and table
    • SLR table
    • LR(1) automaton and table
    • LALR table
    • Error recovery in LR parsing
• Syntax-Directed Translation [ALSU - Ch.5 (section 5.5 excluded)]
  • Syntax-Directed Definitions
  • Inherited and Synthesized Attributes
  • Dependency Graphs
  • Syntax-Directed Translation Schemes
• Intermediate Code Generation [ALSU - Ch. 6 (sections 6.7,6.8,6.9 excluded)]
  • Three-Address Code
  • Type Checking
  • Control Flow Translation schemes

• [ALSU] Alfred V. Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman, Compilers -- Principles, Techniques and Tools, 2nd Edition, Addison-Wesley, 2007.

Lectures

1. 02/10/2019 - Watch the Lecture, Download the Lecture
2. 03/10/2019 - Watch the Lecture, Download the Lecture, Notes
3. 09/10/2019 - Watch the Lecture, Download the Lecture, Notes
4. 10/10/2019 - Watch the Lecture, Download the Lecture, Notes
5. 16/10/2019 - Watch the Lecture, Download the Lecture, Notes
6. 17/10/2019 - Lecture cancelled due to Hacktoberfest 2019
7. 23/10/2019 - Watch the Lecture, Download the Lecture, Notes
8. 24/10/2019 - Watch the Lecture, Download the Lecture, Notes
9. 30/10/2019 - Lecture cancelled due to Degree Ceremony
10. 31/10/2019 - Watch the Lecture, Download the Lecture, Notes
11. 06/11/2019 - Watch the Lecture, Download the Lecture, Notes, Original Knuth's paper on LR parsing (1965)
12. 07/11/2019 - Watch the Lecture, Download the Lecture, Notes
13. 13/11/2019 - Lecture cancelled due to Inauguration of the Academic Year
14. 14/11/2019 - Watch the Lecture, Download the Lecture, Notes
15. 19/11/2019 - Watch the Lecture, Download the Lecture, Notes
16. 21/11/2019 - Watch the Lecture, Download the Lecture, Notes
17. 26/11/2019 - Watch the Lecture, Download the Lecture, Notes
18. 28/11/2019 - Watch the Lecture, Download the Lecture, Notes
19. 03/12/2019 - Watch the Lecture, Download the Lecture, Notes
20. 05/12/2019 - Lecture cancelled due to a commitment of the teacher
21. 10/12/2019 - Watch the Lecture, Download the Lecture, Notes
22. 12/12/2019 - Watch the Lecture, Download the Lecture, Code
23. 17/12/2019 - Watch the Lecture, Download the Lecture, Notes
24. 18/12/2019 - Watch the Lecture, Download the Lecture, Notes
25. 19/12/2019 - Watch the Lecture, Download the Lecture, Notes

Textbooks

• Alfred V. Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman, Compilers -- Principles, Techniques and Tools, 2nd Edition, Addison-Wesley, 2007.
• Terence Parr The Definitive ANTLR4 Reference, The Pragmatic Programmers, 2012.

Slides

1. Introduction
2. Lexical Analysis
3. Syntax Analysis
4. Semantic Analysis I
5. Semantic Analysis II
6. ANTLR 4, Slides Code

Exercise Sessions with Solutions

Lexical Analysis:

1. Lexical Analysis Exercise Session I
2. Lexical Analysis Exercises 3-4-5

Syntax Analysis:

1. Syntax Analysis Exercise Session I
2. Syntax Analysis Exercise Session II
3. Syntax Analysis Exercise 1

Semantic Analysis:

1. Semantic Analysis Exercise 1
2. Semantic Analysis Exercise 3
3. Semantic Analysis Exercise 5
4. Semantic Analysis Exercise 9

Sample Past Written Tests with Solutions

1. Text1, Solution of Text1
2. Text2, Text2 with Solution
3. Text3, Text3 with Solution
4. Text4, Text4 with Solution

Project to be sent the day of the Partial Exam “CMP1920 Sess. X - Project Delivery” in each session X:

1. The description of the project to develop using the ANTLR4 tool is available here.

Exam Dates A.Y. 2019/2020 (Written Test Days) - For each session, projects can be sent by the day before the written test (see Partial Exams “CMP1920 Sess. XXX - Project Delivery” in ESSE3)

1. 05/02/2020 - 3pm - Room TBD, please register to the Partial Exam “CMP1920 Sess. I - Written Test” on ESSE3 before 31/01/2020
2. 19/02/2020 - 3pm - Room TBD, please register to the Partial Exam “CMP1920 Sess. II - Written Test” on ESSE3 before 14/02/2020 - Text, Text with Solutions
3. 24/06/2020 - 3pm - Room TBD, please register to the Partial Exam “CMP1920 Sess. III - Written Test” on ESSE3 before 19/06/2020
4. 08/07/2020 - 3pm - Room TBD, please register to the Partial Exam “CMP1920 Sess. IV - Written Test” on ESSE3 before 03/07/2020
5. 22/07/2020 - 3pm - Room TBD, please register to the Partial Exam “CMP1920 Sess. V - Written Test” on ESSE3 before 17/07/2020
6. 09/09/2020 - 3pm - Room TBD, please register to the Partial Exam “CMP1920 Sess. VI - Written Test” on ESSE3 before 04/09/2020
7. 23/09/2020 - 3pm - Room TBD, please register to the Partial Exam “CMP1920 Sess. VII - Written Test” on ESSE3 before 18/09/2020
8. 24/03/2021 - 3pm - Room TBD, please register to the Partial Exam “CMP1920 Sess. VIII - Written Test” on ESSE3 before 19/03/2021

For registration, please consult the ESSE3 Portal after login.

Exam rules

The exam consists of a written test, containing open-answer questions, together with one project, realised with the ANTLR tool (see section “Projects” above). The Written Test and the Project are two independent Partial Exams (see the exam sessions in the ESSE3 career system) and can be passed in different exam sessions. The final grade, which is the average of the grades of the two Partial Exams, can be obtained and registered only if both the Partial Exams have been passed with a grade of at least 18/30.

Registration for the written tests must be done using the Student Career System ESSE3 here. Please note that the registration deadline is usually 3 working days before the written test date. This course is not mandatory for any MSc curriculum, therefore students will not be able to register for the written test until they communicate to the Secretary Office (Tiziana Jajani c/o Student Secretary Office - Opening Hours) their choice to attend to this course, code [ST1184] COMPILERS. During the exercise sessions throughout the course samples of the written test questions will be presented with solutions. During the written test students can consult a hand-written A4 paper of their production for reference.

Instructions for Sending Projects

Students must create a folder in Google Drive, using the Google account associated to their email name.surname@studenti.unicam.it

The folder must contain all the files relative to the project and a written report, in English, which describes all the phases of the developing of the project. The use of screenshots is encouraged to show, within the report, the runs and the results of the project.

The folder must be named

CMP1920-Project-N-APP-X-Surname-Name

where N is the number of the realised project (according to the section “Projects” above) and X is the number of the exam session (Appello) as specified for each date of the written test above.

The folder must be shared (using Google Drive facilities) with luca.tesei@unicam.it and andrea.polini@unicam.it by 11.59pm of the day before the written test scheduled for the selected session X.

Students that send the project must also register to the Partial Exam “CMP1920 Sess. XXX - Project Delivery” in ESSE3, specified for each exam session.

Exam Results

• The results will be communicated through this site or by email (depending on the number of students).
• Contextually to the communication of the results, students will be invited to accept or reject the evaluation.
• A positive evaluation (>=18/30) of each Partial Exam (Written Test and Project) remains valid for one year or until the student retries the Partial Exam.
• If both grades (Written Test and Project) are accepted, the final grade will be registered in ESSE3.