Description
The main objective of the subject is teaching the process of the compilation of high-level programming languages. The different phases of a compiler and their corresponding implementation techniques are studied. In the practice a simple one-pass compiler is implemented for an imperative language. The technique of syntax-directed translation is studied in the theory.
Type Subject
Optativa
Semester
Second
Credits
5.00
Previous Knowledge

Data and information structure , imperative programming and object-oriented programming.
Design of Programming Languages.

Objectives

The formalisms of the theory of the compilation can be applied to other fields and areas of the computer science. The study of the process of the compilation requires a deep knowledge of the elements that constitute a programming language. Therefore, this subject helps the student to reinforce its knowledge and to acquire new approaches for the programming, design, implementation and evaluation of programming languages.

The students that study the subject acquire the knowledge and they develop the abilities that are indicated next:

1. Basic general knowledge in the theory of the compilation
2. Analysis and synthesis capacity
3. Organization capacity and planning of the work to do among the different members of the group of practical as well as of each student's individual work.
4. Improvement of the communication written in the language used by the students in the different presented exams and in the realization of the reports of the different phases of the practice.
5. Knowledge of computer tools.
6. Capacity of resolution of problems.
7. Ability to work in team.
8. Ability to work in team using telematic ways.
9. Development of interpersonal abilities when defending own arguments against the group partners.
10. Capacity of application of the acquired knowledge of the theory of the compilation in the realization of the practice.
11. Capacity to generate new ideas starting from the theoretical concepts studied in class.
12. Work ability in telematic environments.
13. Use of texts in English in the basic bibliography.
14. Self-regulated learning capacity.
15. Taking of decisions to continue advancing in the development of the practice.
16. Design and projects management.

Contents

1 Semantic analysis
1.1 The semantic analyzer
1.2 Identifiers, attributes and verifications
1.3 The symbol table
1.4 Semantic analysis of types
1.5 Semantic analysis in declarations
1.6 Semantic analysis of expressions
1.7 Semantic analysis of statements
1.8 Other semantic Analyses

2 Code generation
2.1 Introduction
2.2 Organization of the memory
2.3 Data representation and storage
2.4 Generating code for expressions
2.5 Generating code for simple statements
2.6 Generating code for conditional statements and loops
2.7 Generating code for functions and procedures
2.8 Access to local and non-local variables

3 Optimization
3.1 Introduction
3.2 Structure of optimizing compilers
3.3 Intermediate languages
3.4 The MIR language
3.5 From Babel to MIR
3.6 An example
3.7 Code types and order of optimizations
3.8 Stages of the optimization
3.9 Early optimizations
3.10 Transformations preserving functionality
3.11 Loops optimizations
3.12 Counting operations
3.13 Cases of study

Methodology

This subject can be studied in two formats, according to the student's preference, present and semi-presential. The main difference among the two modalities is based on the different physical attendance from the students to the classrooms.

During the course they combine different ways to impart the subject:

1. Masterful classes.

In the present modality, the professor imparts during the course the theoretical concepts of the subject by means of masterful classes. In these classes the professor also solves exercises of direct application of the explained concepts. In the semi-presential modality , the student assumes a more active paper in his learning. It has the contents of the course in the virtual campus where there is a guide of study that: it explains the concepts of the subject, it gives references to the bibliography to be able to enlarge these concepts, it contains enunciated of problems and it contains self-evaluated questions where the student can have an indication of his learning degree. In this format, they do three present encounters at least in a year where the students and the professors meet to carry out masterful classes, problems, practical or debates.

2. Hours of class dedicated to solve theoretical exercises, individually or in groups.

During some hours of class the professor outlines theoretical exercises so that they are solved by the students in that moment. These exercises can be resolved individually or in group.

3. Exercises to solve at home.

Apart of the exercises solved in class, the student must solve others at home. The purpose of these exercises is to secure the theoretical ideas. The students have a problem book with exercises. Some of the exercises are resolved.

4. Work in group in hours of class.

At the end of the subject 4 hours of class are dedicated to the study of a programming language using their technical documentation. The objective is to evaluate its complexity when implementing it.

5. Practice

Along the course the students implement a programming language (Babel) defined by the professor of the subject with academic finalities. The theoretical classes are imparted in the necessary order to be able to make the different phases of the practice inside the established dates.

The practice is done in groups of 2. The delivery is carried out in phases. Each phase is corrected and the student is informed of the results making them suggestions to improve it. In the phase 2 an interview personalized is done to each member of the group so that they defend their work vocally.

Next, the phases are given in those that it is divided the practice and the main objective of each one of them:

Phase 1. Semantic Analysis of the language BABEL
A semantic analyzer's implementation with the attributes grammars.

Phase 2. Code Generation of the language BABEL
To generate code in language assembler (MIPS) by means of the technique of syntax-directed translation.

Evaluation

The subject is divided in two clearly differentiated parts: a theoretical part (40%) and a practical part (60%). Each one of these parts is evaluated for separate and they must be passed for separate to be able to pass the subject.

If the two parts are passed, the final note of the subject is the arithmetic sum of the theory note and of the practice note.

With the purpose of evaluating if the student had reached in an appropriate degree the objectives of the subject different tests are made:

A. Exams
During the course the exams are made.

B. Oral Exams
A present oral exam is done at the end of the phase 2 of the practice made by the students.

F. Reports corresponding to the practices made in group.
To evaluate each report of each one of the phases of the practice the professor uses a form where he has marked and quantified the different aspects that must be considered.

G. Practical works with computer
The implementation of the practice is made in Java language. For each phase the professor has a form for his exhaustive evaluation.

J. Participation in class or in the virtual campus.
The professor of the present modality has a list of possible observations where he writes down the different behaviors and attitudes presented by the students during the class. In the semi-presential system , these attitudes are reflected in the performance and the participation of the students in the forums and in the meetings through the virtual classroom.

Evaluation Criteria

Objective 1: Basic general knowledge of the theory of the compilation.
The student must demonstrate that he has acquired an appropriate knowledge of the concepts studied during the course. [A, B, C, F].

Objective 2: Analysis and synthesis capacity.
The student must be able to analyze the problems with which he faces and must demonstrate synthesis capacity in the generation of solutions. [TO, B, G, J].

Objective 3: Organization capacity and planning of the work to do among the different members of the group of practical as well as of each student's individual work.
The student must plan and to organize his individual work as well as the work to do in group. [G]

Objective 4: improvement of the written communication in the language used by the students in the different presented exams and in the realization of the reports of the different phases of the practice.
The student must present the exams and reports without spelling lacks and with the style and the appropriate order according to the given specifications. [A,F]

Objective 5: Knowledge of computer tools.
The student must demonstrate that he has acquired the necessary knowledge of Java and JavaCC for the implementation of the practice. [F,G]

Objective 6: Capacity of resolution of problems.
The student must demonstrate that he knows how to propose appropriate solutions for the theoretical exercises and for the implementation of the different phases of the practice. [A,B,F,G]

Objective 7: Ability to work in team.
The student must be able to work with the group partners and to propose solutions to the different presented problems. [F,G]

Objective 8: Ability to work in team using telematic means.
Especially semi-presential students , and in smaller degree, the present ones, they must be able to form a work group in a virtual environment using the forums, working with documents of different versions and to dominate the tools of remote synchronous communication. [G,J]

Objective 9: Development of interpersonal abilities when defending own arguments against the group partners.
The student must maintain a flowing communication with his partners of practice group. [F,G]

Objective 10: Capacity of application of the acquired knowledge of the theory of the compilation in the realization of the practice.
The student must identify the formalisms and the appropriate techniques of the theory to implement the different phases of the practice with the professor's orientation and the help of his group partners [F,G]

Objective 11: Capacity to generate new ideas starting from the theoretical concepts studied in class.
The student must demonstrate that he is able to apply in different contexts the techniques of the construction of compilers that he has learned in the theory. Particularly in the realization of the practice. [A,B,F,G]

Objective 12: Work ability in telematic environments.
All the semi-presential students base their study on different tools inside a virtual campus. These competitions are evaluated implicitly. [A,B,C,G]

Objective 13: Use of texts in English in the basic bibliography.
Some of the concepts of the subject are indexed directly in English. These concepts are also evaluated. [A,G]

Objective 14: Self-regulated learning capacity.
The student must demonstrate that he is able to acquire knowledge for himself. [A,C]

Objective 15: Taking of decisions to continue advancing in the development of the practice.
The student must demonstrate that he is able to decide when he has reached the basic objectives of each phase of the practice. [F,G]

Objective 16: Design and projects management.
The student must demonstrate that he is able to make a modular design of the practice and to work it appropriately to be able to finish it with guarantees and inside the requested data. [F,G]

Basic Bibliography

- Aho, Afred V.; Sethi, Ravi; Ullman, Jefrey D. Compilers. Principles, Techniques and Tools. Addison-Wesley Publishing Company, 1985

- Muchnick, Steven S. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, 1997

- Elder, John. Compiler Construction. A Recursive Descent Model. Prentice Hall, 1994

- Mozota i Coloma, Maria Antònia. Problemes i Solucions. Departament d´informàtica. Escola d´enginyeria i arquitectura La Salle. Barcelona, 2007

- Taula de símbols per Babel. Departament d´informàtica. Escola d´enginyeria i arquitectura La Salle. Barcelona, 2007

- Mozota i Coloma, Maria Antònia. BABEL 2007: Part II. Especificació de la pràctica. Departament d´informàtica. Escola d´enginyeria i arquitectura La Salle. Barcelona, 2007

- Larus, R. James. Assemblers, Linkers and the SPIM Simulator. Morgan Kaufmann Publishers. Computer Science Departament, University of Wisconsin-Madison, 1998

- Larus, R. James. SPIM S20: A MIPS R2000 SIMULATOR. Computer Science Departament, University of Wisconsin-Madison, 1997

Additional Material

- Pratt, Terrence W.; Zelkowitz, Marvin V.. Lenguajes de Programación. Diseño e Implementación. Prentice Hall, 1998

- Java. Una introducció. Departament d´informàtica. Escola d´enginyeria i arquitectura La Salle. Barcelona, 1999