Credits
6
Types
Specialization complementary (Computing)
Requirements
  • Prerequisite: TC
Department
CS
The interaction person-machine is often performed by using programming languages. Behind each language there are translation and interpretation tools that enable the program execution. The most known examples of this type of tools are the compilers and interpreters. This course will study the structure of these tools to learn how to analyse the language, translate the statements into instructions of the target machine and optimize the code for a more efficient execution.

The course will also cover language translators beyond the world of compilers. A significant part of the course will be devoted to a project designing a language translator or interpreter. The students will be allowed to propose its own project: a command interpreter to control a robot, a language to describe musical partitures, a language to visualise animations, a language to describe logic circuits, etc. The project will be carried out by teams with two persons. The project may also be combined with the project of another course if there is a suitable synergy.

Teachers

Person in charge

  • Jose Miguel Rivero Almeida ( )

Others

  • Lluis Padro Cirera ( )

Weekly hours

Theory
2
Problems
0
Laboratory
2
Guided learning
0
Autonomous learning
6

Competences

Transversal Competences

Teamwork

  • G5 [Avaluable] - To be capable to work as a team member, being just one more member or performing management tasks, with the finality of contributing to develop projects in a pragmatic way and with responsibility sense; to assume compromises taking into account the available resources.
    • G5.3 - To identify the roles, skills and weaknesses of the different members of the group. To propose improvements in the group structure. To interact with efficacy and professionalism. To negotiate and manage conflicts in the group. To recognize and give support or assume the leader role in the working group. To evaluate and present the results of the tasks of the group. To represent the group in negotiation involving other people. Capacity to collaborate in a multidisciplinary environment. To know and apply the techniques for promoting the creativity.

Technical Competences

Common technical competencies

  • CT1 - To demonstrate knowledge and comprehension of essential facts, concepts, principles and theories related to informatics and their disciplines of reference.
    • CT1.2C - To use properly theories, procedures and tools in the professional development of the informatics engineering in all its fields (specification, design, implementation, deployment and products evaluation) demonstrating the comprehension of the adopted compromises in the design decisions.
  • CT4 - To demonstrate knowledge and capacity to apply the basic algorithmic procedures of the computer science technologies to design solutions for problems, analysing the suitability and complexity of the algorithms.
    • CT4.1 - To identify the most adequate algorithmic solutions to solve medium difficulty problems.

Technical Competences of each Specialization

Computer science specialization

  • CCO1 - To have an in-depth knowledge about the fundamental principles and computations models and be able to apply them to interpret, select, value, model and create new concepts, theories, uses and technological developments, related to informatics.
    • CCO1.2 - To demonstrate knowledge about the theoretical fundamentals of programming languages and the associated lexical, syntactical and semantic processing techniques and be able to apply them to create, design and process languages.
  • CCO2 - To develop effectively and efficiently the adequate algorithms and software to solve complex computation problems.
    • CCO2.3 - To develop and evaluate interactive systems and systems that show complex information, and its application to solve person-computer interaction problems.

Objectives

  1. Knowing the general structure of compilers and interpreters of programming languages.
    Related competences: CCO1.2,
  2. Learn the techniques of lexical analysis and methods for generating scanners
    Related competences: CCO1.2, CT1.2C, CT4.1,
  3. Knowing parsing techniques and methods for generating parsers.
    Related competences: CCO1.2, CT1.2C, CT4.1,
  4. Learn the techniques of semantic analysis of programming languages.
    Related competences: CCO1.2, CT1.2C, CT4.1,
  5. Knowing the structure of an interpreter and the basic concepts on virtual machines.
    Related competences: CCO1.2, CT1.2C, CT4.1,
  6. Learn techniques of compiler code generation.
    Related competences: CCO1.2, CT1.2C, CT4.1,
  7. Learn the for code optimization of a compiler.
    Related competences: CCO1.2, CT1.2C, CT4.1,
  8. Learn how to organize a working group to perform a task of average complexity.
    Related competences: G5.3,
  9. Learn how to design programming languages ​​for applications in various areas of IT.
    Related competences: CCO1.2, CT1.2C, G5.3, CCO2.3, CT4.1,
  10. Learn how to develop a medium-complexity project for the design and translation/interpretation of a programming language.
    Related competences: CT1.2C, G5.3, CCO2.3, CT4.1,

Contents

  1. Introduction.
    Elements of a programming language. Compilers and interpreters: concept and differences. Structure and phases of a compiler and an interpreter.
  2. Lexical analysis.
    Objectives of lexical analysis. Review of the theory of regular languages and finite automata. Construction of lexical analyzers from indeterministic automata. Lexical analysis tools.
  3. Syntax analysis.
    Goals of parsing. Review of the theory of context-free languages and pushdown automata. Ambiguous grammars and right and left recursion. Construction of top-down parsers. Construction of bottom-up parsers.
  4. Syntax trees.
    Concrete and abstract syntax trees. Construction of syntax trees. Information stored in syntax trees.
  5. Semantic Analysis.
    Names and objects in a programming language. Objects lifetime. Static and dynamic name visibility. Function activation blocks. Symbol tables. Type checking.
  6. Interpreters and virtual machines.
    Interpretation of a programming language. Concept of virtual machine. Types of interpreters. Phases of an interpreter. Internal and intermediate representations: tree, three-address code, stack machine code. Access to local and non-local names. Examples of virtual machines.
  7. Code generation.
    Intermediate code. Code generation for arithmetic and Boolean expressions. Code generation for instructions: assignment, conditional instruction, iterative instruction. Functions: activation, parameter and result return blocks. Access to data structures.
  8. Code optimization.
    Basic blocks and local optimizations. Control flow graph. Data flow analysis for global optimizations. Variable life and use/definition. Global optimizations: common subexpressions, dead code, constant propagation and copy propagation. Loop optimizations: invariants and induction variables.

Activities

Activity Evaluation act


Lab test


Objectives: 3 7
Week: 12
Type: lab exam
Theory
0h
Problems
0h
Laboratory
3h
Guided learning
0h
Autonomous learning
2h

Project


Objectives: 9 10 8
Week: 15 (Outside class hours)
Type: theory exam
Theory
1h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
8h

Learning general concepts about languages, compilers and interpreters.

The basic activity is to attend class to acquire knowledge of this topic and to have an overall view of the course. The student will be able to consult specialized books in the case that he or she wishes to expand on some particular aspect.
Objectives: 3 7 9
Contents:
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
2h

Theory test


Objectives: 3 7 9
Week: 15 (Outside class hours)
Type: theory exam
Theory
3h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
6h

Learning about the theory and techniques of lexical analysis.

The student will attend the theoretical classes and devote time to studying the theory of lexical analysis and performing exercises proposed by the professor. Some of the knowledge acquired will have to be applied to the subject project.
Objectives: 2
Contents:
Theory
3h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
5h

Learning about the theory and design techniques of descending syntactic analyzers.

The student will attend the class to acquire the theoretical knowledge. In addition, you will have to consolidate these concepts with your personal study and with the resolution of the proposed problems in class. Some of the knowledge acquired will be used in the project.
Objectives: 3
Contents:
Theory
3h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
6h

Learning about the theory and design techniques of ascending syntactic analyzers.

The student will attend the class to acquire the theoretical knowledge. In addition, you will have to consolidate these concepts with your personal study and with the resolution of the proposed problems in class.
Objectives: 3
Contents:
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
3h

Learning about the construction of abstract syntax trees.

The student will attend the class to acquire the theoretical knowledge. In addition, it will have to consolidate these concepts with its personal study and the resolution of proposed problems in class.
Objectives: 3 4
Contents:
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
3h

Learning from semantic analysis theory and techniques

The student will attend the class to acquire the theoretical knowledge. In addition, it will have to consolidate these concepts with its personal study and the resolution of proposed class problems.
Objectives: 4
Contents:
Theory
4h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
3h

Learning about the design of interpreters and virtual machines

The student will attend the class to acquire the knowledge on the subject. In addition, it will have to consolidate these concepts with its personal study and the resolution of proposed problems in class. The knowledge acquired in the class will later be used in the course project.
Objectives: 5
Contents:
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
4h

Learning about code generation theory and techniques

The student will attend the class to acquire the knowledge on the subject. In addition, it will have to consolidate these concepts with its personal study and the resolution of proposed class problems.
Objectives: 6
Contents:
Theory
4h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
6h

Learning about code optimization theory and techniques

The student will attend the class to acquire the knowledge of the subject. In addition, it will have to consolidate these concepts with its personal study and the resolution of proposed problems in class.
Objectives: 7
Contents:
Theory
4h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
6h

Introduction to the ANTLR tool: Design of an Expression Evaluator.

The student will make a modification of the example proposed by the teacher in the laboratory class. During class, it will use the ANTLR tool, which will be the same as the course project.
Objectives: 3 9
Contents:
Theory
0h
Problems
0h
Laboratory
2h
Guided learning
0h
Autonomous learning
1h

Extending an interpreter from a programming language.

The student will have to perform the modification of the interpreter proposed by the teacher during laboratory and personal study hours. Finally, it will have to build a test game that validates the correctness of the modifications made.
Objectives: 3 9 10 1 2 5
Contents:
Theory
0h
Problems
0h
Laboratory
4h
Guided learning
0h
Autonomous learning
3h

Design of a programming language and its parser.

The activity will consist of designing a simple programming language aimed at a specific type of application. This activity will allow the student himself to propose the language and scope. Otherwise, the student may choose to perform the project proposed by the subject teacher. Some examples of programming languages that could be proposed: (1) a language for creating and displaying simple object animations, (2) a programming language for controlling a Lego-Robot, (3) a language for generating Escher patterns, (4) a language for generating music scores, (5) a language for defining and manipulating mathematical functions, etc. Once the language is chosen, the student will have to perform the lexical and syntactic analyzer using the course tools.
Objectives: 3 9
Contents:
Theory
0h
Problems
0h
Laboratory
4h
Guided learning
0h
Autonomous learning
16h

Design of the interpretation phase of a programming language.

The student will have to build the semantic and language interpreter using course tools during laboratory classes and personal working hours. Finally, you will need to build test games and user-level documentation so that the project can be evaluated.
Objectives: 9 10
Contents:
Theory
0h
Problems
0h
Laboratory
17h
Guided learning
0h
Autonomous learning
16h

Teaching methodology

The theoretical contents of the subject are taught in theory classes. These classes are complemented by practical examples and problems that students have to solve in Autonomous Learning hours. During the theory and sporadically in some laboratory classes some of the most representative exercises of the course will be solved.

In the laboratory sessions, that knowledge that have to support the realization of the project of the subject is imparted. In the first sessions, simple examples will be reviewed in which students will have to make modifications to become familiar with the proposed solutions. After a few introductory sessions, students will focus their efforts on the course project. During the laboratory classes, the teacher will introduce new techniques and will leave an important part of the class for the students to work on their project with the help of the teacher when necessary. In this phase it will be essential to use the Autonomous Learning hours assigned to the project.

The laboratory project will be done in groups of 2 or 3 people, depending on the complexity of the problem. Students are expected to organize their group so that tasks are distributed and synchronized. Each student must have a significant and individual responsibility in the project.

Evaluation methodology

The method aims to evaluate both theoretical and practical knowledge of the student.

The evaluation will consist of three evaluative acts. The first of them (L1) aims to assess practical knowledge of the course and will consist of a laboratory test where the student will have to make small modifications to an existing compiler to add new functionality. This test will evaluate the student's knowledge of the structure of a compiler and their ability to implement new programming language concepts and express them in a grammar. The evaluation will be carried out by validating the implementation with previously prepared test sets.

The second evaluative act (L2) will be based on the development of the semantic analysis and code generation of the compiler proposed in the course. This work will be done in group. The evaluative act will consist of a laboratory test where it will be necessary to execute some sets of tests to validate the compiler and the proposed extensions to the same test.This act will evaluate the student's ability to apply the concepts acquired during the course and the knowledge of the work done in group.

Finally, the third act will consist of a written test where the theoretical knowledge imparted during the course will be evaluated.

The final grade of the course (F) will be calculated with a weighted sum of the two laboratory tests (L1 and L2) and the theoretical knowledge test (T):

Bibliography

Basic:

Complementary:

Previous capacities

To follow the course on Compilers, it is necessary that students have an adequate knowledge of theory of formal languages ​​(regular ​​and context-free languages) and automata (finite and stack). It is also necessary to have knowledge of data structures (lists, trees, graphs) and algorithms on these basic structures (traversal, search, recursion). Finally, a basic knowledge of machine language and assembler is also required. For the reasons mentioned above, the student should have completed the course of Algorithmics, Theory of Computation and Computer Structure.