UPE – Caruaru – Sistemas de Informação
Disciplina: Compiladores
Prof.: Paulemir G. Campos
Conceitos Básicos de Compilação
(Parte 2)
11/5/2015
Comp - Prof. Paulemir Campos
1
Roteiro da Aula

As Fases de um Compilador

Referências
11/5/2015
Comp - Prof. Paulemir Campos
2
As Fases de um Compilador
11/5/2015
Comp - Prof. Paulemir Campos
3
Introdução


Conceitualmente, um compilador opera
em fases;
Cada uma dessas fases transforma o
programa fonte de uma representação
para outra.
11/5/2015
Comp - Prof. Paulemir Campos
4
As Fases de Análise
Registra os
identificadores e
respectivas informações
Trata os erros
encontrados em cada fase
do compilador
As Fases de Síntese
Fases de um Compilador
11/5/2015
Comp - Prof. Paulemir Campos
5
Gerenciamento da
Tabela de Símbolos

Uma função essencial de um compilador
é registrar:


11/5/2015
os identificadores usados no programa
fonte;
e, a coleção de informações dos atributos
de cada identificador, como tipo, escopo, e
no caso de nomes de procedimentos,
dados como número e tipos de argumentos
e forma de passagem de parâmetros.
Comp - Prof. Paulemir Campos
6
Gerenciamento da
Tabela de Símbolos


Uma tabela de símbolos é uma
estrutura de dados contendo um
registro para cada identificador com
campos para os respectivos atributos.
Essa estrutura de dados permite que
seja encontrado o registro de cada
identificador rapidamente, bem como,
atualizar seus dados.
11/5/2015
Comp - Prof. Paulemir Campos
7
Gerenciamento da
Tabela de Símbolos


Quando um identificador é detectado no
programa fonte pelo analisador léxico, o
identificador é incluído na tabela de
símbolos.
Por enquanto, apenas o nome do
identificador é registrado na tabela de
símbolos.
11/5/2015
Comp - Prof. Paulemir Campos
8
Gerenciamento da
Tabela de Símbolos

Exemplo: Um declaração em Pascal como
var posicao, inicial, taxa: real;
o tipo “real” não é reconhecido pelo
analisador léxico.
Tabela de Símbolos
11/5/2015
1
posicao
...
2
inicial
...
3
taxa
...
4
...
...
Comp - Prof. Paulemir Campos
9
Gerenciamento da
Tabela de Símbolos

11/5/2015
As fases seguintes se encarregarão de
incluir as outras informações sobre os
identificadores na tabela de símbolos.
Comp - Prof. Paulemir Campos
10
Manipulador de Erros


Cada fase de compilação pode conter
erros.
Porém, após detectar um erro, a
respectiva fase deve tratá-lo de alguma
forma, de modo que a compilação
prossiga, permitindo que mais erros no
programa fonte possam ser
encontrados.
11/5/2015
Comp - Prof. Paulemir Campos
11
Manipulador de Erros


Um compilador que pára quando
encontra o primeiro erro nem é útil e
nem pode ser assim.
As fases de análise sintática e
semântica geralmente manipulam uma
grande parcela dos erros detectados
pelo compilador.
11/5/2015
Comp - Prof. Paulemir Campos
12
Manipulador de Erros


A fase de análise léxica pode detectar
erros quando caracteres restantes na
entrada não forma nenhum símbolo
(token) da linguagem.
Erros quando o símbolo (token) viola as
regras sintáticas da linguagem são
determinados na fase de análise
sintática.
11/5/2015
Comp - Prof. Paulemir Campos
13
Manipulador de Erros

Já na fase de análise semântica o
compilador tenta detectar construções
sintaticamente corretas, porém, sem
passar a idéia de uma operação.

11/5/2015
Ex.: Uma tentativa de adição entre dois
identificadores, sendo que um é nome de
um array e outro nome de um
procedimento.
Comp - Prof. Paulemir Campos
14
As Fases de Análise


Com o progresso da tradução, a
representação interna do programa
fonte pelo compilador modifica-se.
Por exemplo, será ilustrado as
transformações sofridas pela declaração
“posicao := inicial + taxa * 60” ao
longo do processo de compilação.
11/5/2015
Comp - Prof. Paulemir Campos
15
11/5/2015
Comp - Prof. Paulemir Campos
16
As Fases de Análise

O analisador léxico lê os caracteres do
programa fonte e agrupa-os numa
seqüência de símbolos (tokens), como
identificadores, palavras reservadas (if,
while, etc), caracteres de pontuação,
operadores multi-caracteres como “:=“,
etc.
11/5/2015
Comp - Prof. Paulemir Campos
17
As Fases de Análise

Certos símbolos serão referenciados por
um “valor léxico”.

11/5/2015
Ex.: Quando um identificador como taxa é
encontrado, o analisador léxico além de
gerar um rótulo ou símbolo, como id e
código de identificação, também inclui o
identificador “taxa” na tabela de símbolos,
caso já não tenha sido inserido.
Comp - Prof. Paulemir Campos
18
As Fases de Análise

Foram utilizados id1, id2 e id3 para
posicao, inicial e taxa,
respectivamente, para enfatizar que a
representação interna de um
identificador é diferente da seqüência
de caracteres que formam o
identificador.
11/5/2015
Comp - Prof. Paulemir Campos
19
As Fases de Análise
Estrutura de dados típica de uma árvore de análise sintática
11/5/2015
Comp - Prof. Paulemir Campos
20
Geração de Código Intermediário


Após as análises sintática e semântica,
alguns compiladores geram uma
representação intermediária explícita do
programa fonte.
Pode-se imaginar da representação
intermediária como um programa para
uma máquina abstrata.
11/5/2015
Comp - Prof. Paulemir Campos
21
Geração de Código Intermediário

Essa representação intermediária pode
ter duas propriedades importantes:


11/5/2015
ser fácil de produzir;
e, fácil de traduzir para o programa alvo.
Comp - Prof. Paulemir Campos
22
Geração de Código Intermediário


A representação intermediária pode ter
uma variedade de formas.
Neste caso, optou-se por uma forma
intermediária chamada “código de três
endereços”, consistindo de uma
seqüência de instruções, cada uma com
no máximo três operandos.
11/5/2015
Comp - Prof. Paulemir Campos
23
Geração de Código Intermediário

Semelhante a linguagem assembly para
uma máquina em que toda posição de
memória pode atuar como um
registrador.
11/5/2015
Comp - Prof. Paulemir Campos
24
Geração de Código Intermediário

Ex.: “Código de três endereços” para o
código fonte posicao := inicial + taxa * 60
temp1 := intToReal(60)
temp2 := id3 * temp1
temp3 := id2 + temp2
id1 := temp3
11/5/2015
Comp - Prof. Paulemir Campos
25
Geração de Código Intermediário

Esta forma intermediária tem várias
propriedades:

11/5/2015
Cada instrução tem no máximo um
operador na atribuição. Assim, o
compilador quando gerar estas instruções
deve decidir a ordem em que as operações
serão feitas ou avaliadas;
Comp - Prof. Paulemir Campos
26
Geração de Código Intermediário

Esta forma intermediária tem várias
propriedades (Cont.):


11/5/2015
O compilador deve gerar um identificador
temporário para guardar o valor
computado por cada instrução;
E, algumas instruções tem menos que três
operandos, como a primeira e última
instruções.
Comp - Prof. Paulemir Campos
27
Otimização do
Código Intermediário


Nesta fase tenta-se melhorar o código
intermediário, almejando a obtenção de
um código de máquina que execute
mais rápido.
Algumas otimizações são triviais.
11/5/2015
Comp - Prof. Paulemir Campos
28
Otimização do
Código Intermediário

Por exemplo, um algoritmo gerou o
código intermediário para a atribuição
“posicao := inicial + taxa * 60”, usando
uma instrução para cada operador na
representação em árvore após a análise
semântica, ainda que há um melhor
caminho para efetuar este mesmo
cálculo usando duas instruções.
11/5/2015
Comp - Prof. Paulemir Campos
29
Otimização do
Código Intermediário


Não há nada errado com este algoritmo
simples, uma vez que o problema pode
ser resolvido durante a fase de
otimização de código.
Assim, o compilador pode deduzir que a
conversão de 60 de inteiro para real
pode ser feita imediatamente em tempo
de compilação.
11/5/2015
Comp - Prof. Paulemir Campos
30
Otimização do
Código Intermediário

Além disso, temp3 é usado apenas
para transferir o seu conteúdo para
id1. Logo, obtém-se o código
intermediário otimizado:
temp1 := id3 * 60.0
id1 := id2 + temp1
11/5/2015
Comp - Prof. Paulemir Campos
31
Geração do Código Alvo

Esta é a fase final do compilador.

O código alvo em geral consiste de:


11/5/2015
código de máquina realocável;
ou, código assembly.
Comp - Prof. Paulemir Campos
32
Geração do Código Alvo


Posições de memória são selecionadas
para cada variável usada pelo
programa.
Assim, instruções intermediárias são
traduzidas numa seqüência de
instruções de máquina equivalentes.
11/5/2015
Comp - Prof. Paulemir Campos
33
Geração do Código Alvo


Um aspecto crucial é a atribuição de
variáveis para registradores.
Por exemplo, usando os registradores 1
e 2, podemos obter:
MOV R2, id3
MULT R2, #60.0
MOV R1, id2
11/5/2015
ADD R1, R2
MOV id1, R1
Comp - Prof. Paulemir Campos
34
Geração do Código Alvo



Os primeiro e segundo operandos de
cada instrução especifica um destino e
origem de dados, respectivamente.
O símbolo ‘#’ indica que o número 60
pode ser tratado como uma constante.
O resultado de cada operação é
armazenado no primeiro operando.
11/5/2015
Comp - Prof. Paulemir Campos
35
Referências

Aho, A. V.; Sethi, R. e Ullman, J. D.
Compilers: Principles, Techniques,
and Tools. Addison Wesley Longman,
1985. (Capítulo 1, seção 1.3).
11/5/2015
Comp - Prof. Paulemir Campos
36