Compilers

Code:

EIC0028

Acronym:

COMP

Keywords
Classification	Keyword
OFICIAL	Programming

Instance: 2020/2021 - 2S

Active?	Yes
Web Page:	https://teams.microsoft.com/l/team/19%3a863496861fd04b7a869f33ed7e8cb752%40thread.tacv2/conversations?groupId=1d256bf6-e8f7-46fa-89e0-c21504d6f8e0&tenantId=b7821bc8-67cc-447b-b579-82f7854174fc
Responsible unit:	Department of Informatics Engineering
Course/CS Responsible:	Master in Informatics and Computing Engineering

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
MIEIC	173	Syllabus since 2009/2010	3	-	6	56	162

Teaching language

Suitable for English-speaking students

Objectives

Provide concepts that allow to:

- understand the languages’ compilation phases, in particular for imperative and object-oriented (OO) languages;

- specify the syntax and semantics of a programming language;

- understand and use the data structures and the main algorithms used to implement compilers.

Learning outcomes and competences

The skills and learning outcomes will allow students to:

- develop and implement in software language processing systems of artificial languages and information textually specified under certain lexical and grammar rules;

- design and implement in software the various compiler stages, namely:

- regular expressions and finite automata;

- syntactic and semantic analyzers;

- semantic analyzers;

- code optimization;

- code generators having processors or virtual machines as a target;

Working method

B-learning

Pre-requirements (prior knowledge) and co-requirements (common knowledge)

Imperative programming languages, object-oriented programming languages.

Data structures and algorithms.

Theory of Computation.

Program

- Introduction. Compilation phases and typical structure of a compiler.

- Lexical analysis. Regular expressions and finite automaton. - Syntax analysis. Grammars. Syntax analysis’ algorithms. Error handling.

- Semantic analysis. Type checking.

- Execution environments. Memory organization and schemes for parameter passing.

- High and Low-level intermediate representations. Intermediate code generation techniques.

- Register allocation.

- Code optimizations and final code generation techniques.

Mandatory literature

Appel, Andrew Wilson; Modern Compiler Implementation in Java, Cambridge University Press, 2002. ISBN: ISBN 0-521-82060-X
A. Aho, M. Lam, R. Sethi, J. Ullman; Compilers: Principles, Techniques, and Tools, 2nd Edition, Addison Wesley, 2007. ISBN: 0321486811
Alfred V. Aho... [et al.]; Compilers. ISBN: 0-321-49169-6

Complementary Bibliography

Cooper, Keith D.; Engineering a compiler. ISBN: 1-55860-699-8
Terence Parr; The Definitive ANTLR Reference - Building Domain Specific Languages, The Pragmatic Bookshelf, 2007. ISBN: 978-09787392-4-9
Louden, Kenneth C.; Compiler construction. ISBN: 0-534-93972-4
Muchnick, Steven; Advanced Compiler Design and Implementation, Morgan Kaufman Publishers, 1997. ISBN: ISBN 1-55860-320-4
Pedro Reis Santos, Thinault Langlois; Compiladores - da Teoria à Prática, FCA, 2014. ISBN: 978-972-722-768-6

Teaching methods and learning activities

Lectures: presentations, complemented by examples, demonstrations, and clues for the lab work.
Labs: discussions and problem solving related to the practical work.

Software

JASMIN, http://jasmin.sourceforge.net/.
ANTLR - Another Tool for Language Recognition
JavaCC, https://javacc.dev.java.net/
COINS, http://www.coins-project.org/international/

keywords

Technological sciences > Technology > Computer technology > Software technology

Evaluation Type

Distributed evaluation with final exam

Assessment Components

Designation	Weight (%)
Participação presencial	0,00
Teste	40,00
Trabalho laboratorial	60,00
Total:	100,00

Amount of time allocated to each course unit

Designation	Time (hours)
Elaboração de projeto	50,00
Estudo autónomo	56,00
Frequência das aulas	56,00
Total:	162,00

Eligibility for exams

Finalizing the lab assignment with a minimum grade of 10 (out of 20).
Maximum of three absences in the TP classes.

Calculation formula of final grade

Final grade (all marks from 0 to 20)

• AD: Distributed Evaluation consists of three components (min: 10.0 marks)
•  LHA: Lecture and homework activities (homework and quizzes during the lectures): 15%
•  PRJ: Compiler Project: 70%
• CA: Challenge activities (2 challenges during the semester): 15%
• AD = 0.15 x LHA + 0.70 x PRJ + 0.15 x CA
• FEG: final exam grade (min: 8.0 marks), “Época Normal” (First Round Exam) or “Época de Recurso” (Second Round Exam)
• AD Grade (ADG) =
• AD if AD <= FEG+3
• FEG+3, otherwise
• Final Grade = rounded(0.70 x ADG + 0.30 x FEG)

Passing in the distributed evaluation:

• Distributed evaluation (AD) not inferior to 10.0 marks and a maximum of 3 non-justified absences on the lab (TP) classes

Components contributing to the Compiler Project (PRJ) mark:

• First checkpoint: 5%
• Second checkpoint: 10%
• Third checkpoint: 10%
• Final work: 55%
• Presentation/Discussion: 20%

 

Internship work/project

During the UC, the students work on a project which requires a substantial percentage of the topics addressed in the UC. Usually, there have been two options for the projects:

(a)    Development of a complete mini-compiler. Usually, this project requires the various stages of a compiler having a simplified programming language as the starting point. An abstract grammar in EBNF of the input language is usually given to the students. The compiler usually involves a code generation stage targeting the Java virtual machine (JVM).

(b)    Development of a language translator or a language processor/interpreter. In this case, the projects involve syntactic analysis of the programs in the input language, its intermediate representations, and the code generation in the target language or the interpretation using the intermediate representation.

There are three checkpoints during the semester. These checkpoints are used to acquire the status of the work done, of the options taken, and of the distribution and planning of the work to be done by the group members.

 

Special assessment (TE, DA, ...)

The AD activities (including the practical lab assignment) are mandatory. Due to its duration and complexity, the practical lab assignment must be completed within the semester. Finalizing the AD with a minimum grade of 10.0 (out of 20).

FIRST ROUND/SECOND ROUND:

- Exam (EX).

The final grade (mark) is obtained as presented in section: "Final Mark".

Classification improvement

The classification of the distributed component (AD) cannot be improved in the present academic year and it is used in the two rounds ("normal" and "recurso"). The grade obtained in the component related to the first exam ("Época Normal") can be improved with the final exam ("Época de Recurso") or in the next occurrence of the UC. The grade obtained in the component related to the final exam ("Época de Recurso")  can be improved in the next occurrence of the UC.

Observations

Practical Lab assignment:

- Development of the lexical, syntactical, and semantic analysis’ phases and of the compiler’s code generation for a simple imperative language.

- This assignment should be done in groups of 4 students at the maximum.

Exams are examinations with limited consultation (partial open book).

The students that have passed the course in the previous academic year can avoid a new distributed component (AD) classification. In this case, the AD grade previously obtained will be used in the equations to calculate the final grade in the course, and with the weights of the components for the final grade used in the previous year.