Compiladores
(cod.2819 & 3073)

Departamento de Informática
Universidade da Beira Interior

Ano lectivo 2005/2006
Esta página no formato pdf, no formato ps

1  Novidades

Contents

2  Equipa Docente

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.
 
Assim os objectivos genéricos da cadeira são a apresentação e estudo de metodologias, técnicas e ferramentas para o desenvolvimento processadores de linguagens e de compiladores.
 
Em particular pretende-se:

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 por lhe ter permitido um uso intensivo desta última.

4  Competências

5  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 Intermédio
    4. Utilização dos registos
    5. Alocação na heap

6  Critérios de Avaliação

A avaliação será realizada por exame e avaliação contínua. Listamos a seguir as diferentes componentes da avaliação.

6.1  Avaliação Contínua

A avaliação contínua mede em termos práticos a acquisição dos conceitos expostos. Como tal é baseada na realização, durante o semestre lectivo, de dois trabalhos entregue à equipa docente, dando o segundo origem a uma defesa.
 
Esta avaliação resultará na atribuição da Nota da Componente Prática (NCP).
 
Esta nota é calculada como a média das notas atribuídas às duas partes do trabalho.

6.1.1  Fraudes

A equipa docente gostaria de realçar que qualquer tipo de fraude em qualquer dos itens desta disciplina implica a reprovação automática do aluno faltoso, podendo ainda vir a ser alvo de processo disciplinar.

6.2  Avaliação por Prova Escrita

A avaliação da acquisição de conceitos teóricos é baseado numa prova escrita, em concreto, uma frequência (e, se esta não for suficiente para a aprovação, um exame). Esta avaliação resultará na atribuição da Nota da Prova Escrita (NPE). Note que a nota de exame virá substituir a nota de frequência caso seja necessário recorrer ao exame para a aprovação à disciplina.

6.3  Notas Mínimas

Será igualmente instaurado um regime de notas mínimas como critério de validação da nota final. Esses mínimos (de aprovação) são: Uma nota abaixo desses valores implica reprovação à disciplina.

6.4  Nota Final

Assim a nota final da disciplina é determinada de acordo com a seguinte fórmula:
NF = ⎧
⎪
⎪
⎨
⎪
⎪
⎩
se (NPE >= 8) e (NCP >= 7)
então
   
NCP + NPE

2
senão Reprovado
onde
 
NF = Nota Final (20 valores)
NPE = Nota da Prova Escrita (exame ou frequência) (20 valores)
NCP = Nota Componente Prática (20 valores)


7  Datas Importantes

8  Material Pedagógico

Acetatos manuscritos.

Fichas práticas

 
Ficha prática sobre a construção de um interpretador e de um compilador para uma pequena linguagem aritmética aqui (pdf)!.
 
Primeira versão da ficha de exercícios (para as aulas TP) aqui (pdf)!.
 
Utilizaremos para esse efeito a máquina virtual seguinte: código fonte (tar.gz) implementada em OCaml. A documentação original (francês) encontra-se aqui. Uma versão traduzida para o português está aqui (pdf) ou aqui (ps).
 
Algum material adicional pode ser encontrado nos links seguintes:

OCaml, OCamllex e OCamlyacc

Bibliotecas e noções OCaml úteis à disciplina

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) Consulte igualmente estes dois tutoriais: OCamllex e OCamlyacc

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:

Exemplos completos de Compiladores em OCaml

MinCaml (um mini caml) em OCaml

9  Trabalhos Práticos - Definição

Os trabalhos são individuais.
 
O primeiro trabalho consiste na implementação em OCaml dos autómatos de estados finitos e dos mecanismos associados. (Enunciado completo disponível no site de avaliação automática). Este Trabalho será realizado durante as aulas práticas.
 
O segundo trabalho prático consiste na elaboração dum pequeno compilador e é definido da seguinte forma. Para cada grupo: Os dois primeiros pontos deverão ser discutidos e definidos com o aval do regente da disciplina. O regente procurará minimizar as ocorrências semelhantes do triplo (linguagem, ferramentas de construção de compiladores, compilador por implementar). Veja secção 7 para mais pormenores e a secção 12 para algumas páginas de ajuda.

10  Horário

Tipo de aula Horário Sala
Teórica Quinta-Feira das 8h00 às 10h00 6.03
Teórica-Prática 1 Quinta-Feira das 16h00 às 17h00 6.06
Prática 1 Quinta-Feira das 17h00 às 19h00 6.14
Teórica-Prática 2 Sexta-Feira das 10h00 às 11h00 6.02
Prática 2 Sexta-Feira das 11h00 às 13h00 6.14

11  Atendimento

Horário
Quinta-Feira das 10h00 às 13h00
Sexta-Feira das 9h00 às 10h00 e das 17h00 às 18h00

12  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 (anti-spam, retire os UUU) : desousaUUU@UUUdi.ubi.pt
This document was translated from LATEX by HEVEA.