Compiladores (CC3001) — Aula 1: ApresentaçãoPedro Vasconcelos
Conteúdos e objetivos
1. Princípios de conceção e construção de compiladores I análise
léxical
I análise sintática
I tabelas de símbolos
I geração de código intermédio
I alocação de registos e geração de código máquina
2. Trabalho laboratorial: implementação de um compilador simples
para um subconjunto da linguagem C
Funcionamento
Aulas teóricas I Remotas por video-conferência (Zoom) I Exposição
de conceitos e exemplos
Aulas laboratoriais I Presenciais nos laboratórios (sem registo de
presenças) I Resolução de exercícios I Acompanhamento dos trabalhos
I GitHub Classroom para exercícios e trabalhos
Ferramentas
I Recomendado sistema operativo GNU/Linux I Windows: instale uma VM
com Linux I haskell-platform: GHC, alex, happy, bibliotecas padrão
I Pode também usar Java ou C (mas recomendo Haskell) I O seu editor
de texto/IDE predileto I Git (linha de comando)
Avaliação
Exame nal: 60%
I Os exercícios de aulas são individuais I Trabalho prático:
I componente obrigatória I realizado em grupo de 2 estudantes I
entregas e apresentações: 1ª fase em novembro, 2ª fase em
dezembro
I Classicação mínima no exame nal: 40% (8 valores em 20)
Bibliograa recomendada
1. Modern Compiler construction in ML, Andrew W. Appel, Cambridge
University Press (existem também variantes que usam C ou
Java.)
2. Introduction to Compiler Design, Torben Aegidus Mogensen,
Springer.
O que é um compilador?
I Tradutor de programas numa linguagem de programação para outra I
Usualmente: traduz uma linguagem de alto nível numa de baixo
nível
I Principal técnica para implementação de linguagens
Alguns compiladores
linguagem fonte linguagem destino
GCC C/C++/. . . código máquina1
Clang C/C++/. . . código máquina Fpc Pascal código máquina GHC
Haskell código máquina Rustc Rust código máquina Javac Java código
JVM2
Scalac Scala código JVM tsc TypeScript JavaScript
1E.g. X86, ARM, . . . 2 Java Virtual Machine
Fases de um compilador
Decomposição em fases
I As fases de frontend lidam com linguagem fonte I As fases de
backend lidam com a geração de código máquina I A fase intermédia é
independente da linguagem fonte e do código máquina I Esta
decomposição torna o compilador mais simples I Permite
re-utilização de componentes
I o backend do GCC é usado para compilar C, C++ ou Objective-C I o
backend LLVM é usado pelo Clang, Swift, Rustc e (opcionalmente)
GHC
I Extras: optimizações em código intermédio e/ou no backend
Compiladores vs. interpretadores
Em vez de um compilador, podemos implementar um
interpretador:
I efetua a análise lexical e sintática da linguagem fonte (tal como
um compilador);
I executa diretamente o programa usando a árvore sintática
I em alternativa: pode gerar e executar um código intermédio
Compiladores vs. interpretadores (cont.)
I Mais fácil suportar diferentes arquiteturas de computadores
I Suporta desenvolvimento interativo (read-eval-print-loop)
Vantagens da compilação:
I Executáveis podem ser distribuidos separamente do
compilador
Algumas implementações combinam compiladores e interpretadores
(e.g. GHC, OCaml).
Porquê estudar compiladores?
A maioria dos programadores não vai escrever o seu próprio
compilador.
Porquê então estudar compiladores?
Porquê estudar compiladores? (cont.)
Porquê estudar compiladores? (cont.)
I Compreender a ligação entre linguagens de alto e baixo nível I A
construção de um compilador combina várias competências:
I linguagens formais, autómatos, gramáticas I estruturas de dados e
algoritmos I arquitetura de computadores I semântica de programas,
tipos, lógica
I Conceitos e técnicas são úteis em outras aplicações
I É possível que tenha de implementar um compilador ou
interpretador para uma linguagem especíca de domínio
Como implementar compiladores?
I São programas complexos, logo é preferível usar uma linguagem de
alto-nível
I Linguagens funcionais fortemente tipadas são boas escolhas
Como implementar compiladores? (cont.)
I No entanto: poucos compiladores reais são escritos em linguagens
funcionais!
I As razões podem ser técnicas e sociológicas. . .
I É muito mais comum o compilador ser escrito na mesma linguagem
que ele traduz (self-hosting):
GCC é escrito em C Javac é escrito em Java GHC é escrito em
Haskell
Ocamlc é escrito em OCaml Rustc é escrito em Rust
Porquê self-hosting?
I Prova da maturidade da linguagem e ferramentas (eat your own dog
food) I Facilita comunicação entre developers (uma só
linguagem)
Diculdades do self-hosting
Bootstrapping
Exemplo histórico: a linguagem C.
I O primeiro compilador de C (1973) foi baseado no compilador de B
(uma linguagem anterior)
I O primeiro compilador de B foi implementado numa outra linguagem
de alto nível (TMG) do sistema Multics
I O compilador foi re-escrito em B por estágios até ser capaz de
compilar a si próprio. . .
Fonte: The Development of the C language, Dennis Ritchie;
https://www.bell-labs.com/usr/dmr/www/chist.html.
Segundo exemplo: o compilador de Rust.
2006-2010: primeiros compilador escrito em OCaml
2010: inicio de re-escrita do compilador em Rust (ainda compilado
pelo compilador em OCaml)
Desde 2011: o compilador é desenvolvido em Rust e self-hosted
Fonte: Wikipedia
I Compiler explorer: https://godbolt.org/ I Várias linguagens,
compiladores e arquiteturas I Permite também comparar efeitos de
otimizações I Vídeo tutorial: https://youtu.be/4_HL3PH4wDg