Compiladores
Linguagens Formais e compilação
(cod.2819 & 3073 & 5387)

Departamento de Informática
Universidade da Beira Interior

Ano lectivo 2006/2007

Esta página no formato pdf, no formato ps

1 Novidades

Esta página é a página de apresentação da disciplina de {Compiladores | Linguagens Formais e Compilação}. Esta página é estática.
Queira assim consultar a página de Linguagens Formais e Compilação nos e-conteúdos para informação actualizada sobre esta disciplina.

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, em particular gramaticas livres de contexto, autómatos de pilha, etc …), à qual daremos uma curta introdução. Assim os objectivos genéricos desta disciplina 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:

Introduzir a noção de linguagem e caracterizar o conceito de processamento de linguagens formais, estabelecendo os objectivos, as tarefas dum processador, as exigências que lhe são impostas e as técnicas de desenvolvimento (face às restrições e à complexidade do problema).
Introduzir os conceitos de gramática e de autómato, a sua teoria e a sua aplicação ao desenvolvimento de Processadores de Linguagens.
Introduzir formalismos para especificação da sintaxe e da semântica das linguagens e estudar a implementação dos analisadores que se podem derivar desses formalismos.
Desenvolver capacidades de tradução de textos escritos em linguagens distintas, utilizando métodos de análise e de síntese mais usados pelos compiladores.
Introduzir os processos, ferramentas, algoritmos e estruturas de dados mais utilizados na tradução, na análise e na compilação.

Para quê estudar os Processos de Compilação?

Em primeiro porque é interessante e formador!
Porque as técnicas de processamento de linguagens e de construção de compiladores têm aplicações fortes em muitas áreas da informática, e não só em construção de compiladores.
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 por lhe permitido um uso livre e intensivo desta última.

4 Programa

Currículo Bolonha:

Introdução: o problema, o contexto, o processamento de linguagens na informática, a arquitectura dum compilador.
Processamento de Linguagens
- análise léxica, autómatos finitos, gramáticas e expressões regulares. Processamento de linguagens regulares.
- análise sintáctica: Autómatos de pilha, gramáticas algébricas, análise descendente e análise ascendente.
- analise semântica: gramáticas de atributo, tabelas dos símbolos, inferência e verificação de tipos.
Geração de Código
- geração de código
- analise e optimização de código

Currículo antigo

Introdução à Compilação
1. Notações
2. O que é a Compilação?
3. As diferentes fases da compilação
4. Arquitectura dum compilador
Introdução à Teoria das Linguagens Formais
1. Linguagens Formais
2. Gramáticas Formais
3. Expressões Regulares
4. Autómatos Finitos
Análise Léxica
1. Bases teóricas
2. Construção de analisadores léxicos
3. Tratamento de unidades léxicas
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
Análise semântica
1. Tabela dos símbolos
2. Tipos
3. Atributos
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 tenta qualificar e quantificar a aprendizagem e a aquisição de competência e de conhecimentos do aluno inscrito. Nesta unidade curricular esta avaliação é dividida em duas partes: a avaliação prática e a avaliação teórica. Listamos a seguir as diferentes componentes da avaliação.

5.1 Avaliação da Componente Prática

Esta avaliação mede em termos práticos a aquisição dos conceitos expostos. Como tal é baseada na realização, durante o semestre lectivo, de um trabalho entregue à equipa docente. Este trabalho será dividido em duas partes, dando a última origem a uma defesa. Ambas as partes carecem da entrega dum relatório em L^AT_EX e dum arquivos comprimido com os ficheiros fontes que constituí a implementação realizada assim como de um makefile. 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.

5.1.1 Datas Importantes

Entrega do enunciado do trabalho: primeira semana de aulas
Entrega da primeira parte do trabalho: semana de 23 a 28 de Abril
Entrega da segunda parte do trabalho: na semana de 4 a 9 de Junho
Defesa da segunda parte do trabalho: última semana de aulas.

5.1.2 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.

5.2 Avaliação da Componente Teórica

A avaliação da aquisição de conceitos teóricos é baseado numa prova escrita, nomeadamente uma frequência. Esta avaliação resultará na atribuição da Nota da Componente Teórica (NCT).

5.2.1 Exame

O resultado do exame só irá incidir na NCT.

O aluno admitido a exame mas reprovado por frequência poderá tentar uma nova atribuição da NCT.
O aluno aprovado por frequência poderá melhorar a sua NCT.

5.2.2 Datas importantes

frequência: 21 de Maio de 2007 na aula teórica
exame primeira chamada: 28 de Junho de 2007 às 14h30 (conferir nos académicos)
exame segunda chamada: 5 de Julho de 2007 às 14h30 (conferir nos académicos)
exame época especial: 6 de Setembro de 2007 às 14h30 (conferir nos académicos)

5.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 são:

6 valores (em 20) para a NCP
6 valores (em 20) para a NCT

Uma nota abaixo desses valores implica reprovação à disciplina (Não Admitido a Exame).

5.4 Nota Final

Os mínimos são os mínimos afixados por regulamento e são válidas individualmente para cada parte (NCT e NCP). Assim a nota final da disciplina é determinada de acordo com a seguinte fórmula:

NF =

se (NCT > 6) e (NCP > 6)

então

NCP +NCT

senão Reprovado

onde


NF	=	Nota Final (20 valores)
NCT	=	Nota da Componente Teórica (20 valores)
NCP	=	Nota da Componente Prática (20 valores)

6 Material Pedagógico

Acetatos e sebenta distribuídos nas aulas. Algum material adicional pode ser encontrado nos links seguintes:

OCaml, OCamllex e OCamlyacc

Bibliotecas e noções OCaml úteis à disciplina

Biblioteca Arg: parsing of command line arguments
Biblioteca Filename: operations on file names
Biblioteca Format: pretty printing
Biblioteca Genlex: a generic lexical analyzer
Biblioteca Lexing: the run-time library for lexers generated by ocamllex
Biblioteca Parsing: the run-time library for parsers generated by ocamlyacc
Biblioteca Printexc: facilities for printing exceptions
Biblioteca Printf: formatting printing functions
Biblioteca Scanf: formatted input functions
Biblioteca Stream: streams and parsers. Consulte igualmente este texto e mais este.
Biblioteca Str: regular expressions and string processing.
Biblioteca Sys: system interface

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:

L.S. Barbosa Elementos da Teoria dos Autómatos DI/UM versão ps.gz 1996
João Saraiva Especificação e Processamento de Linguagens DI/UM 1ª Edição versão ps.gz e versão html 1995

Exemplos completos de Compiladores em OCaml

MinCaml (um mini caml) em OCaml

7 Trabalho Prático - Definição

Requisitos Obrigatórios

O trabalho prático é implementado em OCaml e constituído por duas partes. Cada uma delas dá lugar a entrega dum relatório formatado com o L^AT_EXe dum arquivo comprimido contendo o projecto completo, incluindo um makefile. O uso de ferramentas como o CVS ou o subversion é valorizada. O makefile entregue deverá permitir a compilação completa do trabalho alternativamente pelos comandos:

make
make all

O trabalho prático é definido da seguinte forma:

7.1 Primeira Parte

Constituir um grupo (consultar o regente para as regras de constituição de grupo).
Definir o léxico e uma gramática para uma pequena linguagem de programação a escolher com o regente.
implementar a análise léxica, a análise sintáctica e um pretty printer para o formato html.
Escrever e entregar o relatório.
Entregar a primeira parte do trabalho sob o formato dum arquivo comprimido.

Os dois primeiros pontos deverão ser discutidos e definidos com o aval do regente da disciplina.

7.2 Segunda Parte

Estudar a máquina virtual alvo.
implementar a analise semântica e finalizar a implementação do compilador, usando a base definida na primeira parte do trabalho, para a máquina virtual alvo.
Preparar um relatório sobre o trabalho realizado.
Entregar a segunda parte do trabalho sob o formato dum arquivo comprimido.
Apresentar e defender o trabalho realizado.

8 Horário

Tipo de aula	Horário	Sala
Teórica	Segunda-Feira das 9h00 às 11h00	6.26
Práticas Laboratoriais 1	Segunda-Feira das 11h00 às 13h00	6.25
Práticas Laboratoriais 2	Segunda-Feira das 16h00 às 18h00	6.25
Práticas Laboratoriais 3	Quarta-Feira das 9h00 às 11h00	6.25
Práticas Laboratoriais 4	Quinta-Feira das 9h00 às 11h00	6.25
Práticas Laboratoriais 5	Quinta-Feira das 11h00 às 13h00	6.14
Teórica-Prática	Segunda-Feira das 15h00 às 16h00	Gabinete

9 Atendimento

Horário

Segunda-Feira das 14h00 às 16h00

10 Links úteis

Ocaml
- Site OCaml
- Performance Ocaml:The great computer language shootout
- OCamlMakefile: Makefile genérico para OCaml
- Tuareg: Emacs Mode para Ocaml
- Livro: Developing Applications With Objective Caml
- Manual de Referência Ocaml
- Sebentas diversas sobre Ocaml
- Hump: Repositório de aplicações/bibliotecas/”material” OCaml
Compiladores
- Modern Compiler Implementation (Tiger) Aqui
- Sebentas sobre Compiladores em OCaml
- Um pequeno exemplo de compilador em OCaml: MinCaml (um mini caml)
- Aula on-line sobre Compiladores
- Páginas sobre ferramentas para a construção de compiladores:
- Uma página sobre gramáticas de linguagens de programação : Free Grammars for Programming Languages
Emacs
- Site Emacs - XEmacs
- Documentação Emacs - XEmacs
- Comandos principais para Emacs 21
Um site sobre Ciências da Computação (contem vários livros online)
- Site Programming language theory texts online

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

This document was translated from L^AT_EX by H^EV^EA.

Compiladores Linguagens Formais e compilação (cod.2819 & 3073 & 5387)

Departamento de Informática Universidade da Beira Interior