Formal Languages and Compilers

Teacher:

• Luca Tesei

Lectures schedule:

• Wed 2pm-4pm Room AB1 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.

The course intends to provide to the students the theoretical background to understand how a language compiler can be built. The general architecture of a compiler is presented and which are the tools and mechanisms (theoretical and practical) need in order to derive a real compiler. Competences are put in place with the construction of a simple compiler for a simple language.

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

Lectures

1. 07/03/2018 Watch Lecture, Download Lecture, Slides
2. 08/03/2018 Watch Lecture, Download Lecture, Slides, Notes
3. 15/03/2018 Watch Lecture, Download Lecture, Slides, Notes
4. 21/03/2018 Watch Lecture, Download Lecture, Slides, Notes
5. 22/03/2018 Watch Lecture, Download Lecture, Notes
6. 28/03/2018 Watch Lecture, Download Lecture, Slides, Notes
7. 29/03/2018 Watch Lecture, Download Lecture, Slides, Notes
8. 04/04/2018 Watch Lecture, Download Lecture, Slides, Notes
9. 11/04/2018 Watch Lecture, Download Lecture, Slides, Notes
10. 12/04/2018 Watch Lecture, Download Lecture, Slides, Notes
11. 18/04/2018 Watch Lecture, Download Lecture, Slides, Notes
12. 26/04/2018 Watch Lecture, Download Lecture, Slides, Notes
13. 02/05/2018 Watch Lecture, Download Lecture, Slides, Notes
14. 03/05/2018 Watch Lecture, Download Lecture, Slides, Notes
15. 09/05/2018 Watch Lecture, Download Lecture, Slides, Notes
16. 10/05/2018 Watch Lecture, Download Lecture, Notes
17. 16/05/2018 Watch Lecture, Download Lecture, Slides, Code 1, Code 2
18. 17/05/2018 Watch Lecture, Download Lecture, Slides, Code (Refactored, Eclipse Project), Notes
19. 23/05/2018 Watch Lecture, Download Lecture, Slides, Notes
20. 24/05/2018 Watch Lecture, Download Lecture, Slides, Notes
21. 30/05/2018 Watch Lecture, Download Lecture, Notes

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. June 14th, 2016
2. July 5th, 2016

Textbooks

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

Project to be sent the day before the written test:

1. Project 2017-18

Exam Dates A.Y. 2017/2018

1. I Appello - Written test on Thursday 21/06/2018 at 3pm, Room AB3 - No students
2. II Appello - Written test on Thursday 12/07/2018 at 3pm, Room AB3 - Text of the written test, Solution of the written test
3. III Appello - Written test on Thursday 13/09/2018 at 3pm, Room AB3
4. IV Appello - Written test on Thursday 27/09/2018 at 3pm, Room AB3
5. V Appello - Written test on Thursday 31/01/2019 at 3pm, Room TBA
6. VI Appello - Written test on Thursday 21/02/2019 at 3pm, Room TBA
7. VII Appello - Written test to be scheduled in June/July 2019
8. VIII Appello - Written test to be scheduled in June/July 2019

Exam rules

The exam consists of a written test, containing open-answer and/or closed-answer questions, together with one project, realised with the ANTLR tool (see section “Projects” above). The project must be sent by the day before the written test to which the student is registered (see section “Instructions for Sending Projects” below). 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.

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 the BSc and for any MSc curriculum, therefore BSc students or MSc 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 at Campus, Via D'Accorso SNC, Camerino Opening Hours) their choice to attend to this course, code [ST0989] FORMAL LANGUAGES AND COMPILERS.

Please note that any student who did not send the project the before the day of the written test will be excluded from the written test. In case of re-trying of the written test the project must be re-sent.

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

FLC1718-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.

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. In case of acceptance, the grade will be registered in ESSE3.