Compilers

News

  • The page of the same course held in Academic Year 2018/2019 can be found at this link.
  • 28 November 2019: the lecture of Thursday 05/12/2019 has been cancelled due to a commitment of the teacher out of office.
  • 7 November 2019: starting from Tuesday 19/11/2019 lectures are scheduled on Tuesdays 11am - 1pm and on Thursdays 2pm- 4pm. The list of lectures below has been updated.
  • 7 November 2019: the lecture of Wednesday 13/11/2019 has been cancelled due to the Inauguration of the Academic Year.
  • 24 October 2019: the lecture of Wednesday 30/10/2019 has been cancelled because the teacher belongs to the committee for the Degree Ceremony.
  • 10 October 2019: the lecture of Thursday 17/10/2019 has been cancelled to allow the students to participate to the event Hacktoberfest 2019.
  • 24 September 2019: the course of the Academic Year 2019/2020 will start on Wednesday 2nd October at 11am in room AB1 of Polo Lodovici.

General Information

Teacher:

ESSE3 Link

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

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

Course Objectives

See the ESSE3 Description

Course Contents

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

Study Material

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

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