Saltar al contingut Menu
Map
  • Home
  • Information
  • Contact
  • Map

Compilers (CL)

Credits Dept. Type Requirements
9.0 (7.2 ECTS) CS
  • Compulsory for DIE
  • Elective for DCSFW
  • Elective for DCSYS
 ALCC - Prerequisite for DCSFW
EC1 - Prerequisite for DIE , DCSYS , DCSFW
PRED - Prerequisite for DIE , DCSYS
PS - Prerequisite for DCSFW
TC - Prerequisite for DIE , DCSYS

Instructors

Person in charge:  (-)
Others:(-)

General goals

The aim of this subject is to cover the contents specified in the most widely used language processors, and the following specific objectives:

Specific goals

Knowledges

  1. General techniques and tools providing flexible, efficient compilation of programming languages and other applications, such as text formatters (LaTeX, nroff), graphic languages (Post Script, CIF, GIF, JPEG), hardware description languages (VDHL, Verilog), simulation languages (simscript, GPSS), query and command interpreters, and silicon compilers.
  2. An application that uses and consolidate a host of previously acquired concepts: formal languages and automata, structured and recursive programming, abstract data types, etc.

Abilities

  1. Ability to develop practical applications using the techniques and tools studied (e.g. transformation of data, simple interpreters).
  2. Ability to complete a modern modular compiler, and a robust application free of execution errors and proper object code.

Competences

  1. Become a better programmer by improving one"s knowledge of programming languages, and their syntax, semantics, and efficient implementation.

Contents

Estimated time (hours):

T P L Alt Ext. L Stu A. time
Theory Problems Laboratory Other activities External Laboratory Study Additional time

1. Introduction
T      P      L      Alt    Ext. L Stu    A. time Total 
2,0 0 0 0 0 2,0 0 4,0
Compiler structure and stages.
Why study compilers?
The reasons the course is organised the way it is.

2. Lexical analysis
T      P      L      Alt    Ext. L Stu    A. time Total 
3,0 0 2,0 0 2,0 6,0 0 13,0
Problem definition. Review of regular languages and finite automata, various algorithms and associated costs. Error treatment, the PCCTS tool and other applications.
  • Laboratory
    Use of the PCCTS tool and similar applications.
  • Additional laboratory activities:
    Reading, comprehension and analysis of session lab sheets.

3. Syntactic analysis
T      P      L      Alt    Ext. L Stu    A. time Total 
12,0 0 4,0 0 4,0 12,0 0 32,0
Review of context-free grammars and stack automata.
Concrete and abstract syntax trees, ascending and descending parsing techniques, the PCCTS tool, other applications.
  • Laboratory
    Use of the PCCTS tool and similar applications.
  • Additional laboratory activities:
    Reading, comprehension and analysis of session lab sheets.

4. Semantic analysis
T      P      L      Alt    Ext. L Stu    A. time Total 
8,0 0 12,0 0 12,0 8,0 0 40,0
Block-structured languages, passing parameters, type checking, explicit and implicit type conversion. Other programming paradigms.
  • Laboratory
    Implementation of the first part of the practical exercise covers the lexical, syntactic, and semantic analyses stages. Comprehension of the exercise and internal design of the modules in the first part of the exercise.
  • Additional laboratory activities:
    Reading the document that introduces the lab work of the course regarding the lexical, syntactical and semantic analysis. Understanding it and designing the inner modules that will build this first part of the lab work.

5. Interpreters, intermediate representations, and virtual machines.
T      P      L      Alt    Ext. L Stu    A. time Total 
9,0 0 0 0 0 9,0 0 18,0
Interpreters as a useful tool and way of defining the semantics of a language.
Internal and intermediate representations: in tree form, three address code, code for stack machines. Virtual machines: Advantages and disadvantages. The Q-machine. Access to local and non-local names: static chains, and displays.

6. Generating intermediate code
T      P      L      Alt    Ext. L Stu    A. time Total 
14,0 0 10,0 0 10,0 14,0 0 48,0
Coding simple instructions. Compiling boolean expressions, structured types, static and dynamic arrays, procedures and functions as parameters. Adaptation to an object-oriented approach.
  • Laboratory
    Implementing the second part of the assignment (code generation) and its evaluation, especially for this second part.
  • Additional laboratory activities:
    Reading of the document presenting the assignment (code generation). Comprehension of the exercise and internal design of the modules in the second part of the exercise.

7. Independent optimisations of the architecture
T      P      L      Alt    Ext. L Stu    A. time Total 
6,0 0 0 0 0 6,0 0 12,0
Basic blocks, flow control diagrams, life of variables, use and definition of variables, optimisation examples (common sub-expressions, dead code, constant propagation, induced constants and variables in loops).


Total per kind T      P      L      Alt    Ext. L Stu    A. time Total 
54,0 0 28,0 0 28,0 57,0 0 167,0
Avaluation additional hours 3,0
Total work hours for student 170,0

Docent Methodolgy

The objectives pursued stimulate students in their personal work.



. The lab classes enable students to carry out their practical work and to ask questions and discuss about it.



There is a lab sheet providing explanations and setting out the exercises to be performed for the first practical exercises with the PCCTS tool



. With regard to other exercises, there is plenty of material available for producing the compiler.







No distinction is made between theory classes and problem classes, given that the latter are concentrated in just a few periods during the course. A rigid distinction between theory and problems would prove to inflexible for weekly scheduling purposes.



















There are various lists of problems and students will know beforehand which ones they will be required to solve in class.



. Students should attempt to solve the problems on their own before dealing with them in class. In addition, there is abundant material available on the course Web site : notes, slides, modules, practical problems, questions from past exam exams (solved and unsolved), lists of frequent questions, etc.







The course material lets students monitor their progress both in class and outside it. Students can therefore plan their studies in a way that takes other obligations and restrictions into account.

Evaluation Methodgy

There will be a written exam on theory (T), with exercises and short questions. The grade for practical work (P) is based on two practical exercises P1 and P2. Both will consist on modifications of the practical work done by the own student, in order to determine his mastery of the work. P1 will be set at about half of the course and P2 on the last weeks of the course.

The grade P will be obtained as

P= max(P2, ((P1+P2)/2) )

If, because of technical reasons, it were impossible to do the tests, the grade would be obtained from a written exam of the practical work.

The final grade (Fin) will be based on T and P such as to strike a balance between theory and practice.

Fin := 0.6*T + 0.4*P

Basic Bibliography

  • Reinhard Wilhelm, Dieter Maurer Compiler design;, Addison-Wesley, 1995.
  • Andrew W. Appel, with Maia Ginsburg Modern compiler implementation in C, Cambridge University press, 1998.
  • Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman Compilers : principles, techniques, and tools, Addison-Wesley, 1986.
  • Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman; Compiladores : principios, técnicas y herramientas, Addison-Wesley Iberoamericana [etc.], 1990.
  • V. Paxson Flex - fast lexical analyzer generator, ftp://ftp.ee.lbl.gov/flex-2.5.3.tar.gz, 1995.
  • Charles Donnelly and Richard Stallman Bison : the YACC-compatible parser generator : september 2003 Bison version 1.875, GNU, 2003.
  • Richard M. Stallman Using and porting GNU CC : last updated 26 november 1995 for version 2.7.2, Free Software Foundation, 1996.
  • T.J. Parr, the designer and author of PCCTS Language Translation Using PCCTS and C, ISBN:0-9627488-5-4 , disponible en http://www.polhode.com/pccts.html, .

Complementary Bibliography

  • N. Wirth Compiler Construction, Addison-Wesley, 1996.
  • Steven S. Muchnick Advanced compiler design implementation, Morgan Kaufmann, 1997.
  • C.N. Fischer and R.J. LeBlanc Crafting a Compiler, Benjamin/Cummings, 1988.
  • A.W. Appel Modern Compiler Implementation in ML, Cambridge University Press, 1998.
  • A.W. Appel Modern Compiler Implementation in Java, Cambridge University Press, 1998.
  • Alfred V. Aho, Jeffrey D. Ullman The Theory of parsing translation and compiling, Prentice-Hall, 1972.

Web links

  1. http://www.lsi.upc.es/~rivero/CL


Previous capacities

Knowledge of structured programming, and data and algorithm structures; languages, automata and formal grammars; computer structure.


Compartir
Share

 
logo FIB © Barcelona school of informatics - Contact - RSS
This website uses cookies to offer you the best experience and service. If you continue browsing, it is understood that you accept our cookies policy.
Classic version Mobile version