Interpretação e Compilação de Linguagens
Objetivos
Saber
1.Conhecer a arquitetura e técnicas usadas no desenho e implementação de interpretadores, compiladores e sistemas de tipos
2.Conhecer os elementos base das linguagens de programação e a sua semântica
3.Definir linguagens de programação por composição de elementos fundamentais
Saber Fazer
4.Representar e manipular a sintaxe abstracta de uma linguagem como dados de um programa transformador
5.Descrever a semântica de linguagens através de interpretadores, compiladores e verificadores de tipos
6.Conceber e implementar compiladores para código máquina (assembly)
Competências complementares
7.Raciocinar sobre sistemas complexos a vários níveis de abstração
8.Propor e concretizar soluções gerais com base em princípios
Caracterização geral
Código
8152
Créditos
6.0
Professor responsável
Carla Maria Gonçalves Ferreira, Mário José Parreira Pereira
Horas
Semanais - 4
Totais - 60
Idioma de ensino
Português
Pré-requisitos
Conhecimentos de programação avançada. estruturas de dados e algoritmos
Bibliografia
“Concepts in Programming Languages”, John C. Mitchell, Cambridge University Press. ISBN 0 521 78098 5
“Essentials of Programming Languages”, Daniel Friedman, Mitchell Wand, Christopher Haynes, MIT Press.
“Modern Compiler Implementation in Java” Andrew W. Appel, Cambridge University Press
“Modern Compiler Implementation in ML” Andrew W. Appel, Cambridge University Press
“The Study of Programming Languages”, Ryan Stansifer, Prentice Hall International Edition.
"Compilers: Principles, Techniques, and Tools", Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, Pearson Education, Inc
"Types and Programming Languages", Benjamin Pierce, MIT Press
Método de ensino
As aulas teóricas introduzem os vários tópicos centrais na unidade curricular como interpretação, técnicas de compilação de linguagens, representações intermédias, geração de parsers e lexers, análises semânticas.
As aulas de laboratório consistem na implementação de interpretadores e compiladores para pequenas linguagens, de forma incremental, culminando num projeto de maior dimensão.
Método de avaliação
Componentes da Avaliação
A avaliação é constituída por duas componentes: a componente laboratorial e a componente teórico-prática.
Componente Laboratorial e Frequência
A componente laboratorial é composta por um projeto de desenvolvimento e um peso de 30% da nota final. Este projeto consiste no desenho e implementação de um compilador de uma mini-linguagem de programação, produzindo código máquina (assembly). Este projeto deve ser realizados em grupo de dois alunos, estando as notas sujeitas a eventuais discussões.
Para obter frequência, é necessário que CompL >= 9.5.
Utilização de ferramentas de IA
É permitido o uso livre de ferramentas de Inteligência Artificial. É, no entanto, obrigatório reportar o seu uso; caso contrário, o aluno será excluído do elemento de avaliação em questão.
Componente Teórico-Prática
A componente teórico-prática consiste na realização de dois testes (período das aulas) ou de um exame (na época de recurso). Todas as provas são escritas, individuais, presenciais e com consulta de qualquer material impresso. Esta componente representa um peso de 70% da nota final.
A nota da componente teórico-prática (CompTP) é a média das notas dos testes (T1 e T2) ou a nota do exame (Ex):
CompTP = (T1 + T2) / 2 ou CompTP = Ex.
Para obter aprovação, é necessário que CompTP >= 9.5 .
Nota Final
A nota final (F) dos alunos com frequência é:
- F = CompTP, se CompTP < 9.5;
- F = 0.3 CompL + 0.7 CompTP, se CompTP >= 9.5 .
Todas as notas (T1, T2, Ex, CompL e CompTP) são arredondadas às décimas, exceto a nota final (F) que é arredondada às unidades.
Fraude -- Utilização Dispositivos Electrónicos
Durante uma prova de avaliação, um estudante não pode ter junto a si dispositivos electrónicos com capacidade de acesso à internet ou ligação bluetooth (e.g. smartphones, smartwatches, smartglasses, tablets, laptops, etc), ainda que desligados. A violação desta regra implica a reprovação liminar na unidade curricular por exclusão e será comunicada à Comissão Científica do respectivo Curso.
Conteúdo
1. Princípios
Introdução à arquitectura de um compilador: frontend e backend. Ferramentas e linguagens para construção de um compilador.
2. Semântica operacional de linguagens
Noção de semântica formal de um programa. Semântica operacional big-step e small-step. Regras de inferência para definição de relações de avaliação. Semântica operacional big-step de uma linguagem While. Interpretadores em Java e OCaml.
3. Frontend de um compilador
Análise léxica. Expressões regulares e autómatos finitos. Ferramentas geradoras de analisadores léxicos: as ferramentas da família lex. Apresentação de jflex e ocamllex.
Análise sintática. Análise descendente. Análise ascendente. Ferramentas geradores de analisadores sintáticos: as ferramentas da família yacc. Apresentação de cup e menhir.
Análise de tipos. Sistemas de tipos e verificadores de boa tipificação. Propriedades e garantias de analisadores de tipos. Implementação de um sistema de tipos para a linguagem While.
4. Backend de um compilador
Código assembly x86_64. Geração de código. Compilador optimizante. Modos de passagem. Compilação de linguagens funcionais e orientadas a objectos.