Compiladores
(cod. 2819)

Departamento de Informática
Universidade da Beira Interior

Ano lectivo 2003/2004

Table of Contents

1  Novidades



2  Docentes

Simão Melo de Sousa (regente) - Gabinete 4.3.

3  Objectivos

Esta disciplina apresenta as principais fases da construção dum compilador, isto é, um programa que transforma uma sequência de caracteres, representando um programa, numa sequência de instruções máquina que poderão ser executadas com a finalidade de produzir o resultado do programa original.

A construção dum compilador envolve a utilização de vários métodos e ferramentas de análise léxica e sintáctica. A aprendizagem do funcionamento de tais análises constitui uma parte importante desta disciplina. As linguagens de programação modernas de alto nível propõem uma detecção precoce dos erros graças a uma análise semântica, cada vez mais complexa e poderosa, muitas vezes sob a forma dum controlo de tipos. A última fase da compilação é a geração de código que é realizada em várias etapas que correspondem a tradução para várias linguagens intermédias antes de se concluir pela produção de código executável. Estudaremos mais particularmente a organização da memória para a gestão das chamadas de procedimentos. Esta apresentação assenta sobre resultados da teoria das linguagens formais(autómatos finitos, expressões regulares, gramáticas), à qual daremos uma curta introdução.

Através do estudo da compilação, tentaremos mostrar o quão úteis para a informática em geral são as técnicas e as ferramentas oriundas deste estudo assim como procuraremos perceber as características das linguagens de programação. De facto um compilador é um programa de tamanho importante que é necessário bem estruturar. Este deve ser também eficiente e é importante que esteja isento de erro. Ser capaz de escrever um compilador é assim uma competência ``desafio'' para qualquer programador que se quer exímio.

Agradecimentos

O regente da disciplina gostaria de agradecer à Professora Doutora Christine Paulin-Mohring (LRI - Paris Sud, França) por lhe ter facultado a sebenta intitulada ``Cours de Compilation'' de que é autora e permitido um uso intensivo desta última.

4  Programa

  1. Introdução à Compilação
    1. Notações
    2. O que é a Compilação?
    3. As diferentes fases da compilação
    4. Arquitectura dum compilador
  2. Introdução à Teoria das Linguagens Formais
    1. Linguagens Formais
    2. Gramáticas Formais
    3. Expressões Regulares
    4. Autómatos Finitos
  3. Análise Léxica
    1. Bases teóricas
    2. Construção de analisadores léxicos
    3. Tratamento de unidades léxicas
  4. Análise Sintáctica
    1. Generalidades
    2. Gramáticas
    3. Autómatos de pilha
    4. Análise Descendente
    5. Análise ascendente
    6. Gramáticas LL(1)
    7. Gramáticas LR(1)
    8. Análise de Gramáticas Não Contextuais
  5. Análise semântica
    1. Tabela dos símbolos
    2. Tipos
    3. Atributos
  6. Geração de código
    1. Introdução
    2. Tabelas de activação
    3. Código Intermediário
    4. Utilização dos registos
    5. Alocação na heap

5  Critérios de Avaliação

A avaliação será realizada alternativamente: A nota final da frequência e do exame é determinada de acordo com a seguinte fórmula:
NF = se (NPE > 6) então média(NPE,NP) senão Reprovado

 
NF = Nota Final (da frequência ou do exame)
NPE = Nota da Prova Escrita
NP = Nota Prática
 

Em que a nota prática representa a nota atribuída ao mini-projecto realizado durante o semestre lectivo e entregues à equipa docente.

Importante: a condição "nota prática maior do que 5 valores" define o critério de acesso as provas escritas.

6  Datas Importantes

7  Material Pedagógico

Principalmente: apontamentos e acetatos apresentados nas aulas.

Fichas práticas

Ficha prática sobre a construção de um interpretador e de um compilador para uma pequena linguagem aritmética: disponível aqui!(pdf).

Utilizaremos para esse efeito a máquina virtual seguinte (tar.gz) implementada em OCaml.

Algum material adicional pode ser encontrado nos links seguintes:

OCaml, OCamllex e OCamlyacc

Bibliotecas e noções OCaml úteis

OCamllex e OCamlyacc

Consulte os capítulos "OCamllex'' e "OCamlyacc'' do livro Developing Applications With Objective Caml (aqui e aqui) e do manual de referência OCaml (aqui)

Alguns Exemplos

Consulte os exemplos do livro Developing Applications With Objective Caml e os exemplos do manual de referência OCaml

Encontrará também aqui (formato .tgz) alguns dos exemplos descritos nas aulas (formato livre, i.e. sem esforço particular de estruturação).

Autómatos e Linguagens

Um conjunto de ferramentas OCaml verdadeiramente completo e útil sobre autómatos: automatx e graphx. Imprescindível!

Encontrará nesta página do departamento de informática da Universidade do Minho as muito úteis sebentas seguintes:

8  Trabalho Prático

Enunciado da primeira parte do trabalho prático: formato ps formato pdf

Data de Entrega: Quarta Feira 28 de Abril

Data de Entrega da segunda parte do trabalho: Segunda Feira 28 de Junho às 10h00

9  Horário

Tipo de aula Horário Sala
Teórica Terça-Feira das 8h00 às 10h00 6.02
Teórica-Prática Segunda-Feira das 15h00 às 16h00 6.02
Prática Quarta-Feira das 8h00 às 10h00 6.14

10  Atendimento

Horário
Segunda-Feira das 16h00 às 18h00
Quarta-Feira das 10h00 às 12h00

11  Alunos de Engenharia Informática inscritos

Número Nome
11200 VICTOR JOSÉ ALVES GONÇALVES
11762 LUÍS DE ALMEIDA FAZENDEIRO
12279 NUNO ANDRÉ CAETANO BARREIROS
12320 NUNO RAFAEL DE CAMPOS SANTOS
13340 HUGO DANIEL RODRIGUES COSTA
13458 LUÍS MIGUEL CARVALHO CORREIA PEDRO
13462 PEDRO DANIEL NABAIS USSMANE
13585 DANIELA PATRÍCIA COUTINHO DA COSTA
13586 SANDRA MÓNICA DOS SANTOS PEREIRA
13933 JOSÉ MANUEL BOAVIDA GREGÓRIO
14082 DANIEL FILIPE ALVES MARTINS
14085 FILIPE CRUZ GOMES SOARES
14627 JOÃO VASCO PAULO GOMES
16967 AGNIESZKA GöRNIAK
17222 KARINA SACHPAZIDU
1

12  Grupos

Grupo 1
11200 VICTOR JOSÉ ALVES GONÇALVES
12320 NUNO RAFAEL DE CAMPOS SANTOS
13933 JOSÉ MANUEL BOAVIDA GREGÓRIO


Grupo 2
11762 LUÍS DE ALMEIDA FAZENDEIRO
12279 NUNO ANDRÉ CAETANO BARREIROS
14627 JOÃO VASCO PAULO GOMES


Grupo 3
13462 PEDRO DANIEL NABAIS USSMANE
14082 DANIEL FILIPE ALVES MARTINS
14085 FILIPE CRUZ GOMES SOARES


Grupo 4
13458 LUÍS MIGUEL CARVALHO CORREIA PEDRO
13585 DANIELA PATRÍCIA COUTINHO DA COSTA
13586 SANDRA MÓNICA DOS SANTOS PEREIRA


Grupo 5
16967 AGNIESZKA GöRNIAK
17222 KARINA SACHPAZIDU

13  Links úteis

References

[1]
R. Sethi A. V. Aho and J. D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1985.

[2]
A. W. Appel. Modern Compiler Implementation in C. Cambridge University Press, 1998.

[3]
A. W. Appel. Modern Compiler Implementation in Java. Cambridge University Press, Cambridge, 1998.

[4]
A. W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998.

[5]
D. Bagley. The great computer language shootout. http://www.bagley.org/~doug/shootout

[6]
E. Chailloux, P. Manoury, and B. Pagano. Developing applications with objective caml. http://caml.inria.fr/oreilly-book, 2003.

[7]
G. Cousineau and M. Mauny. The functional approach to programming. Cambridge University Press, 1998.

[8]
H. R. Nielson F. Nielson and C. L. Hankin. Principles of Program Analysis. Springer-Verlag, 1999.

[9]
C. J.H. Jacobs, K. G. Langendoen, D. Grune, and H. E. Bal. Modern Compiler Design. Wiley, 2000.

[10]
X. Leroy and P. Weis. Le Language Caml. iia, Inter Edition, 1993.

[11]
X. Leroy and P. Weis. Manuel de Référence du Language Caml. iia, Inter Edition, 1993.

[12]
J. R. Levine, T. Masson, and D. Brown. Lex & Yacc. Unix Programming Tool. O'Reilly, 1995.

[13]
J. Mitchell. Foundation for Programming Languages. Foundations of Computing, MIT Press, 1996.

[14]
S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kauffman, 1997.

[15]
H. R. Nielson and F. Nielson. Semantics with Applications. John Wiley & Sons, Chichester, 1993. http://www.daimi.au.dk/~bra8130/Wiley_book/wiley.html

[16]
OCaml Development Team. The Objective Caml system:Documentation and user's manual, 2002. http://caml.inria.fr/ocaml/htmlman/index.html

[17]
R. Wilhelm and D. Maurer. Compiler Design. Addison Wesley, 1995.

[18]
G. Winskel. The Formal Semantics of Programming Languages: An Introduction. Foundations of Computing series. MIT Press, Cambridge, Massachusetts, February 1993.



Enviar comentários e dúvidas para (retire os UUU) : desousaUUU@UUUdi.ubi.pt

1
As duas últimas estudantes são estudantes Erasmus.
This document was translated from LATEX by HEVEA.