Procesamento de Linguagens
(cod. 11567)

---

Figure 1: Don’t make your compiler complain

---

1  Novidades

• 18/01/2016 Notas Exame: afixadas no lab. Release (6.25).
• 13/01/2016 Notas: afixadas no lab. Release (6.25).
• 04/01/2016 Frequência: 18:00-20:00 sala 6.26.
• 09/12/2015 Notas da Frequência: afixadas no lab. Release (6.25).
• 26/10/2015 Frequência marcada no momento da aula teórica, das 9h00 às 11h00, salas 6.26 e 6.05.
• 16/10/2015 Exemplos de programas FIXE: Aqui.
• 16/10/2015 Enunciado do trabalho: Aqui.
• Relembra-se a secção Fraude (ver 7.1.1) a todos os alunos...
• Inscrição em turmas práticas: via site dos serviços académicos.
• Como colocar uma dúvida ao regente da Unidade Curricular?
  1. Comparecer nas aulas e colocá-la directamente ao regente
  2. Comparecer no horário de atendimento do regente e colocá-la directamente
  3. enviar um email ao regente (desousaUUU@UUUdi.ubi.pt, (retire os UUU) ) com o assunto "PL: XXXX" em que XXX é o título da dúvida em questão. Qualquer outro formato no assunto arrisca condenar o email ao esquecimento.

Contents

• 1  Novidades
• 2  Equipa Docente
• 3  Objectivos
• 4  Competências por Adquirir
• 5  Programa
• 6  Metodologia de Ensino
• 7  Critérios de Avaliação
  • 7.1  Avaliação da Componente Prática
    • 7.1.1  Fraudes
  • 7.2  Avaliação da Componente Teórica
  • 7.3  Concessão de Frequência e Avaliação Contínua
    • 7.3.1  Exame
  • 7.4  Nota Final
    • 7.4.1  Datas importantes
• 8  Material Pedagógico
  • 8.1  Teóricas
  • 8.2  Práticas
    • 8.2.1  Algumas soluções
• 9  Resultados da avaliação
• 10  Referências Bibliográficas
• 11  Horário
• 12  Atendimento

2  Equipa Docente

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

3  Objectivos

Esta disciplina apresenta as fases iniciais 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 fases de analises léxica, sintáctica e semântica. 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:

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

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:

• Conceber, planear, desenhar e implementar em software processadores de linguagens artificiais e de informação especificada textualmente segundo determinadas regras lexicais e sintácticas;
• Conceber e implementar em software as várias etapas relacionadas com compiladores, nomeadamente:
  • expressões regulares e autómatos finitos;
  • analisadores sintácticos;
  • analisadores semânticos.

5  Programa

1. Introdução: o problema, o contexto, o processamento de linguagens na informática, a arquitectura dum compilador.
2. 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.

6  Metodologia de Ensino

As aulas presenciais são divididas em duas categorias

• Aulas Teóricas onde são expostos os conceitos teóricos, os algoritmos mas também as tecnologias capacitativas, próprios à construção (do front-end) de um compilador.
• Aulas Práticas com aplicação das técnicas de compilação na construção (de front-ends) de compiladores para linguagens de programação simples.

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. A entrega do trabalho estará organizado em metas intermédias. Cada meta intermédia dará lugar a uma reunião com a equipa docente. Este trabalho dará origem a uma defesa no acto da entrega final. Este trabalho carece 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 permitindo a compilação completa.

Esta avaliação resultará na atribuição da Nota da Componente Prática (NCP).

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) como a média das duas frequências realizadas.

7.3  Concessão de Frequência e Avaliação Contínua

O parâmetro de "Frequência" atribuído no final desta unidade curricular traduz, no contexto da avaliação contínua, a "avaliação mínima" do estudante ao longo do processo de ensino-aprendizagem no final das actividades de contacto.

Considera-se que o estudante demonstrou ter adquirido o grau de conhecimentos mínimos (durante o processo de aprendizagem ao longo das actividades lectivas) quando este demonstrou as mínimas competências em cada componente avaliada.

É assim concedido Frequência ao aluno que obteve os mínimos (6) em vigor na Universidade da Beira Interior em ambas as componentes (NCP e NCT). Ou seja:

Notas Mínimas

De forma detalhada, é 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).

Avaliação Contínua

No caso da concessão de Frequência (i.e. (NCT ≥ 6) e (NCP ≥ 6) ), a avaliação quantitativa, designada aqui de Nota da Avaliação Contínua (NAC), é determinada da seguinte forma:

onde

Se a avaliação quantitativa resultar numa nota maior ou igual a 10 então o aluno é dispensado de exame (Frequência com dispensa de exame) senão o aluno obtem a Frequência sem dispensa de exame.

7.3.1  Exame

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

• O aluno admitido a exame mas reprovado na avaliação contínua poderá tentar uma nova atribuição da NCT.
• O aluno aprovado na avaliação contínua (Frequência com dispensa de exame) poderá melhorar a sua NCT.

7.4  Nota Final

Assim a nota final da disciplina é determinada de acordo coma seguinte fórmula:

onde

7.4.1  Datas importantes

• Frequência 1: 2 de Novembro de 2015.
• Frequência 2: 4 de Janeiro de 2016.
• Entrega do enunciado do trabalho: 19 de Outubro.
• Entrega do trabalho: 5 de Janeiro de 2016.
• Defesa do trabalho: Aula prática da última semana de aulas.
• exame primeira chamada: (conferir nos académicos)
• exame segunda chamada: (conferir nos académicos)
• exame época especial: (conferir nos académicos)

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

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 léxica

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

Trabalhos Práticos

Aqui.

9  Resultados da avaliação

Nada por enquanto.

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

11  Horário

12  Atendimento

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 L^AT_EX by H^EV^EA.