Compiladores
Introdução à Compilação
Prof. Edson Alves
Faculdade UnB Gama
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Sumário
1. Introdução
2. Análise do programa fonte
3. Fases de um compilador
4. Agrupamento de fases
5. Ferramentas
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Histórico
I Os primeiros compiladores surgiram na década de 50
I Não há registros precisos de qual foi o primeiro compilador
I Os primeiros compiladores lidavam com a tradução de fórmulas aritméticas
(FORTRAN – Formula Translator )
I Os compiladores eram considerados programas difíceis de se escrever
I O primeiro compilador Fortran levou 18 homens-ano para ser escrito (1
homen-ano ≈ 2.080 horas)
I Embora continue não sendo uma tarefa não trivial, a escrita de compiladores se
beneficiou dos avanços da área desde então
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Definição
Definição de compilador (informal)
Um compilador é um programa que lê um programa escrito em uma linguagem
(linguagem fonte) e o traduz para uma outra linguagem (linguagem alvo).
programa programa
compilador
fonte alvo
mensagens
de erro
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Características dos compiladores
I O processo de compilação deve identificar e relatar possíveis erros no programa
fonte
I Em geral, as linguagens fonte são linguagens de programação tradicionais
(C/C++, Java, Python, etc)
I As linguagens alvo podem ser tanto linguagens tradicionais quanto linguagens de
máquina
I Os compiladores podem ser classificados de diversas formas, dependendo de seu
objetivo ou como foi construído (de uma passagem, múltiplas passagens,
depuradores, etc)
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Criação do programa executável
I Além do compilador, outros programas podem ser usados na criação do programa
executável
I Antes de ser passado para o compilador, o programa alvo pode ser pré-processado
(por exemplo, o pré-processador da linguagem C processa as diretivas como
#include e #define)
I Após a compilação, o programa alvo pode demandar processamento adicional
para a construção do executável (novamente no caso da linguagem C, temos o
montador e o linkeditor )
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Exemplo de fluxo de geração de um programa executável
esqueleto do
pré-processador programa fonte
programa fonte
programa alvo
montador em linguagem compilador
de montagem
bibliotecas
código de
carregador arquivos
máquina relocável
objetos relocáveis
programa executável
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Análise e síntese
I A compilação é composta por duas partes: análise e síntese
I A análise divide o programa fonte em partes constituintes e as organiza em uma
representação intermediária
I Em geral, a representação intermediária consiste em uma árvore sintática, onde
cada nó representa uma operação e cada filho representa um operando
I A síntese constrói o programa alvo a partir desta representação intermediária
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Exemplo de árvore sintática
=
imc ÷
m ×
h h
Figura: Árvore sintática da fórmula imc = m/h2 .
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Análise do programa fonte
A análise é composta por três fases:
1. análise linear : o fluxo de caracteres que compõem o programa alvo é lido, da
esquerda para direita, e agrupado em tokens (sequência de caracteres com
significado coletivo)
2. análise hierárquica: os tokens são ordenados hierarquicamente em coleções
aninhadas com significado coletivo
3. análise semântica: verificação que garante que os componentes do programa se
combinam de forma significativa
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Análise léxica
Em um compilador, a análise linear também é denominada análise léxica ou
esquadrinhamento. Por exemplo, no enunciado
F = 1.8 * C + 32
a análise léxica identificaria os seguintes tokens:
1. o identificador F
2. o símbolo de atribuição =
3. a constante em ponto flutuante 1.8
4. o símbolo de multiplicação *
5. o identificador C
6. o símbolo de adição +
7. a constante inteira 32
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Análise sintática
A análise hierárquica também é denominada análise sintática ou gramatical. Ela
agrupa os tokens hierarquicamente, em geral em uma árvore gramatical
A estrutura hierárquica pode ser definida por meio de regras recursivas. Por exemplo,
considere as seguintes regras:
1. qualquer identificador é uma expressão
2. qualquer número é uma expressão
3. se E1 e E2 são expressões, também são expressões E1 + E2 e E1 ∗ E2
4. se I é um identificador e E uma expressão, então I = E é um enunciado
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Exemplo de árvore gramatical
enunciado de
atribuição
identificador = expressão
F expressão + expressão
expressão * expressão número
número identificador 32
1.8 C
Figura: Árvore gramatical do enunciado F = 1.8 * C + 32
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Análise semântica
I A análise semântica verifica potenciais erros semânticos no programa alvo
I Ela usa a árvore da análise sintática para identificar operadores e operandos das
expressões e enunicados
I Ela também faz a verificação de tipos
I Caso os tipos dos operandos não sejam compatíveis com os tipos esperados pelos
operadores, esta análise ou retorna um erro ou adiciona uma promoção (ou
conversão) de tipo, a depender da linguagem alvo
I Por exemplo, na expressão à direita do enunciado F = 1.8 * C + 32, o
operando à esquerda da soma tem tipo ponto flutuante e o da direita tipo inteiro:
o valor 32 deve ser promovido para ponto flutuante ou deve ser sinalizado um erro
de tipo
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
As fases de um compilador
I Conceitualmente, o compilador opera em fases
I Cada fase manipula o programa fonte e entrega o resultado para a próxima fase
I Na prática, algumas fases podem ser agrupadas, e a representação intermediária
entre elas pode ser não se construída explicitamente
I As primeiras fases estão relacionadas à análise do programa fonte, as últimas
estão relacionadas à síntese (construção do programa alvo)
I Duas atividades interagem com todas as fases: a gerência da tabela de símbolos e
o tratamento de erros
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Representação típica das fases de um compilador
programa fonte programa alvo
analisador gerador de
léxico código
gerência da
tabela de símbolos
analisador otimizador de
sintático código
tratamemto de
erros
analisador gerador de código
semântico intermediário
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Gerenciamento da tabela de símbolos
I Esta atividade registra os identificadores do programa alvo e identifica seus
diversos atributos
I Exemplos de possíveis atributos de um identificador: nome, tipo, memória e
escopo
I Caso o identificador se refira a um procedimento, dentre seus atributos devem
constar a quantidade de seus parâmetros e respectivos tipos, modo de passagem
(cópia ou referência) e o tipo do retorno, se houver
I Os identificadores e seus respectivos atributos são armazenados em uma estrutura
denominada tabela de símbolos
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Tratamento de erros
I A cada fase da compilação podem acontecer um ou mais erros
I Após a identificação do erro, o compilador deve tratá-lo de alguma maneira e, se
possível, continuar o processo em busca de outros erros
I Abortar a compilação logo no primeiro erro pode diminuir a utilidade do
compilador (por exemplo, o prosseguimento da compilação após um erro léxico
pode ajudar na geração de uma sugestão de correção para o erro)
I As análises sintática e semântica podem identificar uma parcela considerável dos
erros no programa fonte
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Exemplo da parte da análise do programa fonte
fahrenheit = 1.8 * celsius + 32
analisador
léxico
id1 = 1.8 * id2 + 32
Figura: Análise léxica do enunciado fahrenheit = 1.8 * celsius + 32
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Exemplo da parte da análise do programa fonte
id1 = 1.8 * id2 + 32
analisador
sintático
id1 +
* 32
1.8 id2
Figura: Análise sintática
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Exemplo da parte da análise do programa fonte
= =
id1 + id1 +
analisador
semântico
* 32 * intToFloat
1.8 id2 1.8 id2 32
Figura: Análise semântica
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Geração de código intermédiario
I A árvore resultante da análise semântica é transformada pelo compilador em um
código intermediário
I Esta representação pode ser entendida como um código para uma máquina
abstrata
I O código intermediário deve ter duas qualidades fundamentais:
1. deve ser fácil de gerar
2. deve ser fácil de traduzir para o programa alvo
I Uma representação possível é o código de três endereços
I Além de computar expressões, esta representação também precisa tratar dos
fluxos de controle e das chamadas de procedimentos
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Exemplo de geração de código intermediário
=
temp1 = intToFloat(32)
id1 + temp2 = 1.8 * id2
gerador de
código intermediário
* intToFloat temp3 = temp1 + temp2
id1 = temp3
1.8 id2 32
Figura: Representação por código de três endereços
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Otimização do código
I Esta fase procura formas de melhorar o código intermediário, com o intuito de
melhorar a performance do código de máquina do programa alvo
I Algumas otimizações são triviais, outras demandam algoritmos sofisticados,
impactando no tempo de compilação
I As otimizações não devem alterar a semântica do código intermediário
I As otimizações podem melhorar, além do tempo de execução, o uso de memória
do programa alvo
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Exemplo de otimização do código intermediário
temp1 = intToFloat(32)
temp2 = 1.8 * id2 temp1 = 1.8 * id2
otimizador de
código
temp3 = temp1 + temp2 id1 = temp1 + 32.0
id1 = temp3
Figura: Otimização
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Geração de código
I A geração de código é a última etapa da compilação
I Ela produz o programa alvo, em geral em linguagem de máquina relocável ou
código de montagem
I Nesta etapa devem ser atribuídas localizações de memória para as variáveis e
também feita a atribuição das variáveis aos registradores
LDR r2, [id2]
temp1 = 1.8 * id2 MUL r2, #1.8
gerador de
MOV r1, #32.0
código
id1 = temp1 + 32.0 ADD r1, r2
STR r1, [id1]
Figura: Geração de código em pseudo assembly
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Interface de vanguarda
I Na práticas, as fases de um compilador são agrupadas em duas interfaces:
vanguarda e retaguarda
I A interface de vanguarda contém as fases que dependem primariamente do
programa fonte e que independem da máquina alvo
I Em geral, ela inclui as fases de análise, a criação da tabela de símbolos e a
geração de código intermediário
I Ela também inclui o tratamento de erros associados a estas fases
I Embora a otimização faça parte primariamente da interface de retaguarda, é
possível aplicar algum nível de otimização na interface de vanguarda
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Interface de retaguarda
I A interface de retaguarda contém as fases que dependem primariamente da
máquina alvo, e independem do programa alvo
I O ponto de partida é o código intermediário
I Assim, esta interface contém, em geral, as fases de otimização e geração de código
I Ela também manipula a tabela de símbolos e trata dos erros associados à estas
últimas duas fases
I No cenário ideal, ambas interfaces são independentes, o que permite fixar uma
delas e alterar a outra para obter diferentes compiladores com diferentes objetivos
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Compiladores de uma mesma linguagem para múltiplas máquinas
interface de máquina
retaguarda 1 alvo 1
interface de máquina
retaguarda 2 alvo 2
linguagem interface de
fonte vanguarda
...
interface de máquina
retaguarda N alvo N
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Compiladores de múltiplas linguagens para uma mesma máquina
linguagem interface de
fonte 1 vanguarda 1
linguagem interface de
fonte 2 vanguarda 2
interface de máquina
retaguarda alvo
...
linguagem interface de
fonte N vanguarda N
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Ferramentas para a construção de compiladores
I Sendo o compilador um software, todas as ferramentas úteis no desenvolvimento
de um software também serão úteis na construção de um compilador (editor de
texto, depuradores, gerenciadores de versão, etc)
I Existem, entretanto, ferramentas especializadas nas diferentes fases da
compilação, as quais podem ser usadas na construção de novos compiladores
I Os geradores de analisadores gramaticas produzem analisadores sintáticos a partir
de uma entrada baseada em uma gramática livre de contexto (Yacc, Bison, etc)
I Os geradores de analisadores léxicos geram os mesmos a partir de especificações
baseadas em expressões regulares (Lex, Flex, etc)
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Ferramentas para a construção de compiladores
I Os dispositivos de tradução dirigidos pela sintaxe produzem uma coleção de
rotinas que percorrem uma árvore gramatical, gerando código intermediário a
partir dela
I Os geradores automáticos de código estipulam regras que traduzem cada
operação da linguagem intermediária para a linguagem de máquina alvo
I Os dispositivos de fluxo de dados atuam na fase de otimização a partir da
observação do fluxo de dados entre as diferentes partes de um programa
Prof. Edson Alves Compiladores
Introdução Análise do programa fonte Fases de um compilador Agrupamento de fases Ferramentas
Referências
1. AHO, Alfred V, SETHI, Ravi, ULLMAN, Jeffrey D. Compiladores: Princípios,
Técnicas e Ferramentas, LTC Editora, 1995.
2. [Link]. GNU Bison, acesso em 23/05/2022.
3. Wikipédia. Flex (lexical analyser generator), acesso em 23/05/2022.
Prof. Edson Alves Compiladores