Linguagens Formais e Compilação
(cod. 5387)

Departamento de Informática
Universidade da Beira Interior

Ano lectivo 2012/2013


Figure 1: Don’t make your compiler complain

Esta página no formato pdf

1  Novidades

Contents

2  Equipa Docente

Simão Melo de Sousa (regente) - Gabinete 3.17 - Laboratório 6.10 - Bloco VI.

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 gramáticas 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:

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

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.

O regente gostaria de agradecer igualmente o Professor Doutor Jean-Christophe Filliâtre (LRI - Paris Sud / CNRS, França) pelo apoio prestado na componente prática desta UC.

4  Competências por Adquirir

Os estudantes deverão adquirir as seguintes competências:

5  Programa

  1. Introdução: o problema, o contexto, o processamento de linguagens na informática, a arquitectura dum compilador.
  2. Processamento de Linguagens
  3. Geração de Código

6  Metodologia de Ensino

As aulas presenciais são divididas em duas categorias

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

7.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 realizado em grupo e entregue à equipa docente. Este trabalho será dividido em duas partes, dando ambas origem a uma defesa. Ambas as partes carecem da entrega dum relatório em LATEX e dum arquivos comprimido com os ficheiros fontes que constituí a implementação realizada assim como de um makefile permitindo a compilação completa.

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.

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

7.2  Avaliação da Componente Teórica

A avaliação da aquisição de conceitos teóricos é baseado em provas escritas, nomeadamente aqui duas frequências. Esta avaliação resultará na atribuição da Nota da Componente Teórica (NCT) e será calculada como a média das notas atribuídas às duas frequências.

7.2.1  Exame

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

7.2.2  Datas importantes

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

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

7.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 coma seguinte fórmula:

NF = 
se  (NCT ≥ 6)  e (NCP ≥ 6) 
então
    
NCP + NCT
2
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)
 

8  Material Pedagógico

Acetatos e sebenta distribuídos nas aulas.

8.1  Teóricas

Capítulo: Introdução

Capítulo: Analises sintácticas descendentes

Capítulo: Analises sintácticas ascendentes

Capítulo: Árvores de sintaxe abstracta

Capítulo: Analise semântica

Capítulo: Analise semântica - Complementar

Capítulo: Sistemas de tipos - Complementar

Capítulo: Geração de código

Capítulo: Tutorial MIPS

Capítulo: Geração de código (versão antiga - compilação para uma stack based virtual machine) - Complementar

Capítulo: Geração de código - um exemple de uma stack based virtual machine - Complementar

8.2  Práticas

Para quem necessitar uma actualização em programação OCaml, encontrará aqui uma introdução à programação funcional em OCaml.

Ficha : Introdução à analise sintáctica com yacc/menhir

Ficha teórico-prática - Aplicação das linguagens formais à construção de analisadores, análises descendentes, ascendentes, análises semânticas, sistemas de tipo.

Ficha prática - Introdução à analise léxica , construção de lexer, parser com lex/yacc/menhir, analisadores de tipos, analisadores semânticos.

Ficha: Introdução à construção de compiladores - a linguagem artih

8.2.1  Algumas soluções

solução de alguns exercícios de analise léxica em ocaml (parte 1)

solução de alguns exercícios de analise léxica em ocaml (parte 2)

Exemplo de uma pequena calculadora feita de raíz com base em processamento de listas.

um “htmlizer” para Caml feito em ocamllex

Resolução completa: sistema de gestão de notas

compilador e interpretador completo da linguagem arith com target a máquina virtual “VM”

Uma frequência resolvida

Resolução de exercício sobre analises LL(1)

Arquivo com provas de anos anteriores (contém algumas resoluções).

ZIP com exemplos de programas MIPS

ZIP com o código do compilador arith para MIPS *por completar*

ZIP com o código do compilador arith para MIPS *completo*

ZIP com o código do compilador arith para MIPS *completo* alternativo (com typechecking)

8.3  Material Suplementar

Enunciado do trabalho.

9  Referências Bibliográficas

As referências principais são: [4, 6, 1]

As restantes referências listadas em fim de documento são de consulta alternativa ou ocasional.

10  Horário

Tipo de aulaHorárioSala
TeóricaSegunda-Feira das 9h00 às 11h006.02
Práticas Laboratoriais 1Quinta-Feira das 11h00 às 13h006.13
Práticas Laboratoriais 2Quint-Feira das 9h00 às 11h006.13

11  Atendimento

Horário
Sexta-Feira das 9h00 às 11h00

References

[1]
A. V. Aho, R. Sethi, 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]
C. J.H. Jacobs, K. G. Langendoen, D. Grune, and H. E. Bal. Modern Compiler Design. Wiley, 2000.
[9]
X. Leroy and P. Weis. Le Language Caml. iia, Inter Edition, 1993.
[10]
X. Leroy and P. Weis. Manuel de Référence du Language Caml. iia, Inter Edition, 1993.
[11]
J. R. Levine, T. Masson, and D. Brown. Lex & Yacc. Unix Programming Tool. O’Reilly, 1995.
[12]
J. Mitchell. Foundation for Programming Languages. Foundations of Computing, MIT Press, 1996.
[13]
S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kauffman, 1997.
[14]
F. Nielson, H. R. Nielson, and C. L. Hankin. Principles of Program Analysis. Springer-Verlag, 1999.
[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 LATEX by HEVEA.