Compilers
News
- 6 February 2019: The text and the solution of the written test of Wednesday 06/02/2019 is available in the Exams section below.
- 24 January 2019: The written test previously scheduled on 31/01/2019 was moved to Wednesday 06/02/2019 3.00pm. Please register on ESSE3 by 05/02/2019.
- 18 January 2019: an Errata Corrige has been published regarding the track of the project, please consult the relative section below.
- 20 December 2018: the lecture cancelled on 19 December 2018 is rescheduled on Thursday 17 January 2019 (last lecture, exercise session for the written test)
- 18 December 2018: the lecture of Wednesday 19 December 2018 is cancelled.
- 17 December 2018: the track of the project is online in the relative section.
- 09 October 2018: the lectures of Thursday 25th October 2018 and Wednesday 31st October 2018 are cancelled.
General Information
Teacher:
ESSE3 Link
Lectures schedule:
- Wed 11am-1pm Room AB2 Polo Lodovici, Via Madonna delle Carceri 9, Camerino
- Thu 11am-1pm Room AB3 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.
Course Objectives
D1 – KNOWLEDGE AND UNDERSTANDING
At the end of the course, the student should be able to:
- Identify all essential steps for automatically converting source code into assembly or other low-level languages.
- Explain how programs that process other programs treat the other programs as their input data.
- Describe the benefits of having program representations other than strings of source code.
- Distinguish a language definition (what constructs mean) from a particular language implementation (compiler vs. interpreter, run-time representation of data objects, etc.).
- Distinguish syntax and parsing from semantics and evaluation.
- Define formally different language recognisers, such as REGEXPs, NFAs, DFAs, CFGs
- Illustrate some of the basic algorithms to generate lexical analysers from lexical definitions
- Illustrate some of the basic algorithms to generate parsers from grammar definitions
- Identify key issues in syntax definitions: ambiguity, associativity, precedence.
D2 – APPLYING KNOWLEDGE AND UNDERSTANDING
At the end of the course, the student should be able to:
- Use formal grammars to specify the syntax of languages.
- Convert among equivalently powerful notations for a language, including among DFAs, NFAs, and regular expressions, and between PDAs and CFGs.
- Describe an abstract syntax tree for a small language.
- Write a program to process some representation of code for some purpose, such as an interpreter, an expression optimiser, or a documentation generator.
- Use declarative tools to generate parsers and scanners.
- Implement context-sensitive, source-level static analyses such as type-checkers.
- Describe semantic analyses using an attribute grammar.
- Define useful static analyses in terms of a conceptual framework such as dataflow analysis.
D3 – MAKING JUDGEMENTS
At the end of the course, the student should be able to:
- Determine a language’s place in the Chomsky hierarchy (regular, context-free, recursively enumerable).
D4 - COMMUNICATION SKILLS
At the end of the course, the student should be able to:
- Produce a detailed report on the design and implementation of a project
D5 – LEARNING SKILLS
At the end of the course, the student should be able to:
- Understand and use any new tool for the automatic generation of lexers and parsers
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
- 03/10/2018 - Watch the Lecture, Download the Lecture (in the first part of the lecture the desktop cannot be seen in the recording. I'm sorry for the mistake. During the first part we watched this wiki page, the table of contents of the book and the slides that are given in the following), Slides 1, Slides 2, Notes
- 11/10/2018 - Watch the Lecture, Download the Lecture, Slides, Notes - The last two pages of the notes contain the explanation of the last exercise that was left unsolved during the lecture
- 22/11/2018 - Watch the Lecture, Download the Lecture, Slides, Notes, Original Knuth paper on LR parsing
Exercise Sessions with Solutions
Lexical Analysis:
Syntax Analysis:
Semantic Analysis:
Sample Past Written Tests with Solutions
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
Project to be sent the day of the Partial Exam “CMP1819 Sess. X - Project” in each session X:
- 17/12/2018 - Track of the project, read carefully the submission guidelines. Errata Corrige of 18/01/2019, please download this archive and read the file Errata Corrige.txt
Exams
Exam Dates A.Y. 2018/2019 (Written Test Days) - For each session, projects can be sent by the day before the written test
31/01/2019 - 3pm06/02/2019 - 3pm - Room LA1, Text, Text with Solution (corrected on 20/02/2019 - there was an error in the solution of exercise 2)- 21/02/2019 - 3pm - Room AB1, Text, Text with Solution
- 12/06/2019 - 3pm - Room AA1
- 26/06/2019 - 3pm - Room AA1
- 11/09/2019 - 3pm - Room AB2, please register to the Partial Exam “CMP1819 Sess. VI - Written Test” on ESSE3 before 06/09/2019
- 25/09/2019 - 3pm - Room AB2, please register to the Partial Exam “CMP1819 Sess. VII - Written Test” on ESSE3 before 20/09/2019
- 25/03/2020 - 3pm - Room TBD, please register to the Partial Exam “CMP1819 Sess. VIII - Written Test” on ESSE3 before 20/03/2020
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 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 - 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
CMP1819-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 “CMP1819 Sess. XXX - Project” 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.
