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

  • Jordi Cortadella Fortuny ( )

Others

  • Jose Miguel Rivero Almeida ( )
  • Lluis Padro Cirera ( )

Weekly hours

Theory
2
Problems
0
Laboratory
2
Guided learning
0.4
Autonomous learning
5.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.
    Objectius de l'anàlisi lèxica. Revisió de la teoria de llenguatges regulars i autòmats finits. Construcció d'analitzadors lèxics a partir d'autòmats indeterministes.Eines d'anàlisi lèxica.
  3. Syntax analysis.
    Objectius de l'anàlisi sintàctica. Revisió de la teoria de llenguatges lliures de contexte i autòmats de pila. Gramàtiques ambigües i recursivitat per la dreta i per l'esquerra. Construcció d'analitzadors sintàctics descendents. Construcció d'analitzadors sintàctics ascendents.
  4. Syntax trees.
    Arbres sintàctics concrets i abstractes. Construcció d'arbres sintàctics. Informació emmagatzemada en els arbres sintàctics.
  5. Semantic Analysis.
    Noms i objectes en un llenguatge de programació. Vida dels objectes. Visibilitat de noms estàtica i dinàmica.Bloc d'activació d'una funció.Taules de símbols.Comprobacions de tipus.
  6. Interpreters and virtual machines.
    Interpretació d'un llenguatge de programació. Concepte de màquina virtual. Tipus d'intèrprets. Fases d'un intèrpret. Representacions internes i intermitges: en arbre, codi de tres direccions, codi per a màquines de piles. Accés a noms locals i no locals. Exemples de màquines virtuals.
  7. Code generation.
    Codi intermig. Generació de codi per a expressions aritmètiques i booleanes. Generació de codi per a instruccions: assignació, instrucció condicional, instrucció iterativa. Funcions: blocs d'activació, pas de paràmetres i retorn de resultats. Accés a estructures de dades.
  8. Code optimization.
    Blocs bàsics i optimitzacions locals. Graf de control de flux. Anàlisi de flux per a optimitzacions globals. Vida i ús/definició de variables.Optimitzacions globals: subexpressions comunes, codi mort, propagació de constants i propagació de còpies. Optimitzacions en bucles: invariants i variables d'inducció.

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: final exam
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
1h
Autonomous learning
2h

Aprenentage de conceptes generals sobre llenguatges, compiladors i intèrprets.

L'activitat bàsica és la de assitir a classe per adquirir els coneixements d'aquest tema i tenir una visió global del curs. L'estudiant podrà consultar llibres especialitzats en el cas que vulgui aprofondir en algun aspecte determinat.
Objectives: 3 7 9
Contents:
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
2h

Aprenentatge sobre la teoria i tècniques d'anàlisi lèxica.

L'estudiant assistirà a les classes teòriques i dedicarà temps a estudiar la teoria sobre anàlisis lèxic i realitzar exercicis proposats pel professor. Una part dels coneixements adquirits hauran de ser aplicats al projecte de l'assignatura.
Objectives: 2
Contents:
Theory
3h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
5h

Theory test


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

Aprenentatge sobre la teoria i tècniques de disseny d'analitzadors sintàctics descendents.

L'alumne assistirà a classe per adquirir els coneixements teòrics. Addicionalement haurà de consolidar aquests conceptes amb el seu estudi personal i amb la resolució dels problemes proposats a classe. Una part dels coneixements adquirits seran utilitzats en el projecte.
Objectives: 3
Contents:
Theory
4h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
6h

Aprenentatge sobre la teoria i tècniques de disseny d'analitzadors sintàctics ascendents.

L'alumne assistirà a classe per adquirir els coneixements teòrics. Addicionalement haurà de consolidar aquests conceptes amb el seu estudi personal i amb la resolució dels problemes proposats a classe.
Objectives: 3
Contents:
Theory
3h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
3h

Aprenentage sobre la construcció d'arbres abstractes de sintaxi.

L'alumne assistirà a classe per adquirir els coneixements teòrics. Addicionalement haurà de consolidar aquests conceptes amb el seu estudi personal i la resolució dels problemes proposats a classe.
Objectives: 3 4
Contents:
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
3h

Aprenentatge de teoria i tècniques d'anàlisi semàntica

L'alumne assistirà a classe per adquirir els coneixements teòrics. Addicionalement haurà de consolidar aquests conceptes amb el seu estudi personal i la resolució dels problemes proposats a classe.
Objectives: 4
Contents:
Theory
4h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
3h

Aprenentage sobre el disseny d'intèrprets i màquines virtuals

L'alumne assistirà a classe per adquirir els coneixements sobre el tema. Addicionalement haurà de consolidar aquests conceptes amb el seu estudi personal i la resolució dels problemes proposats a classe. Els coneixements adquirits a classe seran posteriorment utilitzats en el projecte del curs.
Objectives: 5
Contents:
Theory
4h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
4h

Aprenentage sobre la teoria i tècniques de generació de codi

L'alumne assistirà a classe per adquirir els coneixements sobre el tema. Addicionalement haurà de consolidar aquests conceptes amb el seu estudi personal i la resolució dels problemes proposats a classe.
Objectives: 6
Contents:
Theory
4h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
6h

Aprenentatge sobre la teoria i tècniques d'optimització de codi

L'alumne assistirà a classe per adquirir els coneixements del tema. Addicionalement haurà de consolidar aquests conceptes amb el seu estudi personal i la resolució dels problemes proposats a classe.
Objectives: 7
Contents:
Theory
4h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
6h

Introducció a l'eina ANTLR: disseny d'un avaluador d'expressions.

L'alumne realitzarà una modificació de l'exemple proposat pel professor a la classe de laboratori. Durant la classe, utilitzarà l'eina ANTLR, que serà la mateixa amb la que es realitzarà el projecte del curs.
Objectives: 3 9
Contents:
Theory
0h
Problems
0h
Laboratory
2h
Guided learning
0h
Autonomous learning
1h

Ampliació d'un intèrpret d'un lleguatge de programació.

L'alumne haurà de realitzar la modificació de l'intèrpret proposat pel professor durant les hores de laboratori i d'estudi personal. Finalment haurà de construir un jocs de proves que validin la correctesa de les modificacions realitzades.
Objectives: 3 9 10 1 2 5
Contents:
Theory
0h
Problems
0h
Laboratory
4h
Guided learning
0h
Autonomous learning
3h

Disseny d'un llenguatge de programació i el seu analitzador sintàctic.

L'activitat consistirà en dissenyar un llenguatge de programació senzill orientat a un tipus específic d'aplicacions. En aquesta activitat es permetrà que el propi estudiant proposi el llenguatge i l'àmbit d'aplicació. Altrament, l'estudiant podrà optar per realitzar el projecte proposat pel professor de l'assignatura. Alguns exemples de llenguatges de programació que es podrien proposar: (1) un llenguatge per a la creació i visualització d'animacions d'objectes senzills, (2) un llenguatge de programació del control d'un Lego-Robot, (3) un llenguatge per a generar patrons Escher, (4) un llenguatge per a generar partitures de música, (5) un llenguatge per a definir i manipular funcions matemàtiques, etc. Una vegada triat el llenguatge, l'alumne haurà de realitzar l'analitzador lèxic i sintàctic utilitzants les eines del curs.
Objectives: 3 9
Contents:
Theory
0h
Problems
0h
Laboratory
4h
Guided learning
1h
Autonomous learning
16h

Disseny de la fase d'interpretació d'un llenguatge de programació.

L'alumne haurà de construir l'analitzador semàntic i intèrpret del llenguatge utilitzant les eines del curs durant les classes de laboratori i les hores de treball personal. Finalment haurà de construir uns jocs de prova i una documentació a nivell d'usuari per tal que el projecte pugui ser avaluat.
Objectives: 9 10
Contents:
Theory
0h
Problems
0h
Laboratory
17h
Guided learning
1h
Autonomous learning
16h

Teaching methodology

Els continguts teòrics de l'assignatura s'imparteixen a les classes de teoria. Aquestes classes es complementen amb exemples pràctics i problemes que els estudiants han de resoldre en les hores d'Aprenentatge Autònom. Durant les classes de teoria i esporàdicament en algunes classes de laboratori es resoldran alguns dels exercicis mes representatius del curs.

En les sessions de laboratori s'imparteixen aquells coneixements que han de donar suport a la realització del projecte de l'assignatura. En les primeres sessions es revisaran exemples senzills en els que els estudiants hauran de fer modificacions per familiaritzar-se amb les solucions proposades. Després d'unes sessions introductòries, els estudiants centraran els seus esforços en el projecte del curs. Durant les classes de laboratori, el professor anirà introduint noves tècniques i deixarà una part important de la classe per tal que els estudiants treballin amb el seu projecte amb l'ajut del professor quan sigui necessari.En aquesta fase serà imprescindible la utilització de les hores d'Aprenentatge Autònom assignades al projecte.

El projecte de laboratori es farà en grups de 2 o 3 persones, depenent de la complexitat del problema. S'espera que els estudiants organitzin el seu grup de manera que les tasques siguin distribuïdes i sincronitzades. Cada estudiant haurà de tenir una responsabilitat important i individual en el projecte.

Evaluation methodology

El mètode té com a objectiu avaluar els coneixements tant teòrics com pràctics de l'estudiant.

L'avaluació consistirà en tres actes avaluatius. El primer d'ells (L1) té com a objectiu avaluar coneixements pràctics del curs i consistirà en una prova de laboratori on l'estudiant haurà de fer petites modificacions a un compilador existent per afegir-hi nova funcionalitat. Amb aquesta prova s'avaluarà el coneixement que l'estudiant té de l'estructura d'un compilador i la seva capacitat d'implementar nous conceptes de llenguatges de programació i expressar-los en una gramàtica. L'avaluació es realitzarà mitjançant la validació de la implementació amb jocs de proves prèviament preparats.

El segon acte avaluatiu (L2) es basarà en el desenvolupament de l'anàlisi semàntica i generació de codi del compilador proposat a l'assignatura. Aquest treball es farà en grup. L'acte avaluatiu consistirà en una prova de laboratori on caldrà executar uns jocs de proves per validar el compilador i les extensions proposades a la mateixa prova. En aquest acte s'avaluarà la capacitat de l'estudiant per aplicar els conceptes adquirits durant el curs i el coneixement del treball realitzat en grup.

Finalment, el tercer acte consistirà en una prova escrita on s'avaluaran els coneixements teòrics impartits durant el curs.

La nota final del curs (F) es calcularà amb una suma ponderada de les dues proves de laboratori (L1 i L2) i la prova de coneixements teòrics (T):

F = 0.2 L1 + 0.35 L2 + 0.45 T

Amb el projecte de laboratori també s'avaluarà la capacitat de treball en grup. El projecte haurà de ser realitzat per grups de dos estudiants. Per a cada estudiant, s'avaluarà la seva implicació en el grup, el repartiment de responsabilitats, el compliment dels acords d'implementació establerts al principi del projecte, la gestió dels conflictes entre els membres del grup, el coneixement global del projecte i la presentació dels resultats.

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.

Addendum

Contents

No hi ha modificacions.

Teaching methodology

No hi ha modificacions.

Evaluation methodology

No hi ha modificacions.

Contingency plan

En cas de semi-presencialitat, les classes de teoria es faran remotament, combinant vídeos i classes on-line. En cas que la situació sanitària ho demani, les classes de pràctiques també seran realitzades on-line, utilitzant els mateixos recursos informàtics que s'utilitzen en les classes convencionals.