Interpretation and Compilation of Programming Languages
Objectives
Knowledge
1.To know the architecture and techniques used in the design and implementation of interpreters, compilers and type systems
2.To know the essential components of the design of programming languages and corresponding semantics
3.To define programming languages by composition of base elements
Application
4.To define algorithms of the abstract representation of programs
5.To describe language semantics by interpreting, compiler and verification algorithms
6.To design and implement compiler procedures targeting machine code (assembly)
Soft-Skills
7.To reason about complex systems at different levels of abstraction
8.To design general purpose designs based on first principles
General characterization
Code
8152
Credits
6.0
Responsible teacher
Carla Maria Gonçalves Ferreira, Mário José Parreira Pereira
Hours
Weekly - 4
Total - 60
Teaching language
Português
Prerequisites
Advanced programming knowledge, data structures and algorithms
Bibliography
“Concepts in Programming Languages”, John C. Mitchell, Cambridge University Press. ISBN 0 521 78098 5
“Essentials of Programming Languages”, Daniel Friedman, Mitchell Wand, Christopher Haynes, MIT Press.
“Modern Compiler Implementation in Java” Andrew W. Appel, Cambridge University Press
“Modern Compiler Implementation in ML” Andrew W. Appel, Cambridge University Press
“The Study of Programming Languages”, Ryan Stansifer, Prentice Hall International Edition.
"Compilers: Principles, Techniques, and Tools", Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, Pearson Education, Inc
"Types and Programming Languages", Benjamin Pierce, MIT Press
Teaching method
The lectures introduce the various central topics to the course such as definitional interpreters, compilation techniques, intermediate representations, parsing and lexing, semantic analyses.
The labs consist in the implementation of small interpreters and compilers that illustrate the key concepts in small languages, incrementally, culminating in a larger sized project.
Evaluation method
Grading Components
The grading is made up of two components: laboratory and theoretical-practical.
Laboratory Component
The laboratory component is based on a development project and weights 30% of the final grade. The project aims at designing and implementing a compiler for subset of a programming language towards machine code (assembly). Such project is done in teams of two students, and the grading might be subject to eventual discussion.
In order to succeed, it is required that LComp >= 9.5.
Use of IA-assisted tools
The use of IA-assisted tools is fully allowed. However, its use must always be reported; otherwise, the student will be excluded from the corresponding handout.
Theoretical-Practical Component
The theoretical-practical component comprises two tests (lectures period) or a final exam. Tests and exams are written, open-book and done in person and individually. This component weights 70% of the final grade.
The theoretical-practical grade (TPComp) is the mean of the tests (T1 and T2) of
the exam grade (Ex):
TPComp = (T1 + T2) / 2 or TPComp = Ex.
In order to succeed, it is required TPComp >= 9.5.
Final Grade
The final grade (F), defined only if LComp >= 9.5, is:
- F = TPComp, if TPComp < 9.5;
- F = 0.3 LComp + 0.7 LComp, if TPComp >= 9.5.
All grade (T1, T2, Ex, LComp, TPComp) are rounded towards the nearest tenth, except the final grade (F) which rounded towards the nearest whole number.
Fraud -- Use of Electronic Devices
During an assessment, a student may not have any electronic devices capable of accessing the internet or with Bluetooth connectivity (e.g., smartphones, smartwatches, smartglasses, tablets, laptops) with them, even if they are turned off.
Violation of this rule results in immediate failure of the curricular unit by exclusion and will be reported to the Scientific Committee of the respective program.
Subject matter
1. Principles
Introduction to a compiler''s architecture: frontend and backend. Tools and languages for compiler construction.
2. Operational semantics of languages
The formal semantics of programs. Big-step and small-step operational semantics. Inference rules for defining evaluation relations. Big-step semantics of a While language. Interpreters in Java and OCaml.
3. Compiler''s frontend
Lexical analysis. Regular expressions and finite automata. Lexical analyzers generator tools: the lex family tools. Introduction to jflex and ocamllex.
Syntactic analysis. Top-down parsing. Bottom-up parsing. Syntactic analyzers generator tools: the yacc family tools. Introduction to cup and menhir.
Typing analysis. Type systems and well-typedness checkers. Proprierties and guarantees of type-checking. Implementation of a type system for a While language.
4. Compiler''s backend
Assembly code x86_64. Code generation. Optimizing compiler. Passage modes. Compilation of functional and object oriented languages.