9 Geração de Código Intermediário Parte1 - Compiladores CEFET MG

Prévia do material em texto

Compiladores 
Prof.ª Kecia Aline Marques Ferreira 
CEFET-MG 
 
Geração de Código Intermediário 
1 
Geração de Código Intermediário 
 
• Introdução 
• Código de três endereços 
• Leiaute de armazenamento para nomes locais 
• Sequências de declarações 
 
 
 
 
 
 
 
 
2 
Introdução 
• No modelo análise e síntese de um compilador: 
 
– O front-end analisa o programa fonte e cria uma representação 
intermediária 
 
– O back-end utiliza essa representação intermediária para gerar o 
código objeto 
 
• Embora seja possível traduzir diretamente para a linguagem da máquina 
alvo, isso prejudica modularidade 
 
• Suponha que se deseja construir compiladores para N linguagens fonte 
diferentes que deverão gerar código para M máquinas diferentes 
 
3 
Introdução 
• Para isso seria necessário construir N X M compiladores 
 
 
 
 
 
 
 
 
• Uma representação intermediária (RI) é um tipo de linguagem de máquina 
abstrata que pode expressar as operações de uma máquina alvo, porém 
sem conter detalhes específicos da linguagem dessa máquina 
4 
Java 
Pascal 
C 
Máquina 1 
Máquina 2 
Máquina 3 
Introdução 
• Para aumentar modularidade, o compilador primeiro traduz a linguagem 
fonte em uma representação intermediária e então traduz a 
representação intermediária para a linguagem alvo 
 
 
 
 
 
 
 
 
 
• Uma forma de representação intermediária entre o front-end e o back-end 
é o código intermediário 
 
 
5 
Java 
Pascal 
C 
Máquina 1 
Máquina 2 
Máquina 3 
RI 
Código de Três Endereços 
• No código de três endereços, existe no máximo um operador do lado 
direito de uma instrução 
 
– Nenhuma expressão aritmética construída com vários operadores é 
permitida 
 
• Por exemplo, uma expressão na linguagem fonte como x+y*z deve ser 
traduzida para uma sequência de instruções de três endereços 
 
t1 = y * z 
t2 = x + t1 
 
onde t1 e t2 são nomes temporários gerados pelo compilador 
6 
Código de Três Endereços – 
Endereços e Instruções 
• O código de três endereços é construído a partir de dois conceitos: endereços 
e instruções 
 
• Endereço: um endereço pode ser uma das seguintes entidades: 
 
– Um nome: 
 
• Por conveniência, é permitido que os nomes que aparecem no 
programa fonte apareçam também como endereços no código de três 
endereços. 
• Em uma implementação, um nome que aparece no programa fonte é 
substituído por um apontador para a sua entrada na tabela de 
símbolos, na qual estão contidas todas as informações sobre este 
nome 
 
– Uma constante 
– Um temporário gerado pelo compilador 
 7 
Código de Três Endereços – 
Endereços e Instruções 
• Instruções: as instruções mais comuns de três endereços são: 
 
– Atribuição: 
 
• Na forma x = y op z 
 op é um operador binário aritmético ou lógico 
x, y e z são endereços 
 
• Na forma x = op z 
 op é um operador unário 
 
8 
Código de Três Endereços – 
Endereços e Instruções 
– Cópia: 
 
• Na forma x = y 
onde se atribui a x o valor de y. 
 
– Desvio incondicional 
• goto L 
A instrução de três endereços com rótulo L é a próxima a ser 
executada. 
 
 Rótulos simbólicos: 
• Representa o índice de uma instrução de três endereços na 
sequência de instruções 
• São utilizados por instruções que alteram o fluxo de controle 
 
 
9 
Código de Três Endereços – 
Endereços e Instruções 
– Desvio condicionais 
• if x goto L 
Se x for verdadeiro, a instrução de três endereços com rótulo L é a 
próxima a ser executada; caso contrário, a próxima instrução de três 
endereços na sequência de instruções será executada. 
 
• ifFalse x goto L 
Se x for falso, a instrução de três endereços com rótulo L é a próxima a 
ser executada; caso contrário, a próxima instrução de três endereços 
na sequência de instruções será executada. 
 
• if x relop y goto L 
relop é um operador relacional (<, ==, >=, etc.) 
Se x relop y avaliar como verdadeiro, a instrução de três endereços com 
rótulo L é a próxima a ser executada; caso contrário, a próxima 
instrução de três endereços na sequência de instruções será 
executada. 
 
 
 10 
Código de Três Endereços – 
Endereços e Instruções 
– Chamadas de procedimentos/funções e retornos 
 
• param x 
x será passado como parâmetro na chamada a um procedimento 
 
• call p,n 
Efetua a chamada ao procedimento p, que recebe n parâmetros 
 
• y = call p,n 
Efetua a chamada à função p, que recebe n parâmetros. O valor 
retornado pela função é atribuído a y. 
 
• return y 
Efetua o retorno de uma função/procedimento. 
y é o valor a ser retornado pela função (é opcional). 
11 
Código de Três Endereços – 
Endereços e Instruções 
Exemplo: 
param x1 
param x2 
... 
param xn 
call p, n 
 
– Instruções indexadas de cópia: 
 
• x = y[i] 
Atribui a x o valor contido no endereço i unidades de memória além 
do endereço de y 
 
 
12 
Código de Três Endereços – 
Endereços e Instruções 
• x[i] = y 
Atribui o valor de y ao conteúdo do endereço i unidades de memória 
além de x 
 
– Atribuições de endereço e apontador 
 
• x = &y 
Atribui a x o endereço de y 
 
• x = *y 
Atribui a x o conteúdo do endereço dado por y 
 
• *x = y 
Atribui o valor de y ao conteúdo do endereço dado por x 
 
 
 
13 
Código de Três Endereços – 
Endereços e Instruções 
• Exemplo: considere o seguinte comando de um programa fonte: 
do 
 i = i+1; 
while (a[i] < v); 
 
 Supondo que a seja um vetor de elementos, cada um ocupando 8 unidades de 
espaço, esse trecho de código fonte poderia ser traduzido para um dos seguintes 
código de três endereços: 
 
 
 
 
14 
 
 L: t1 = i + 1 
 i = t1 
 t2 = i * 8 
 t3 = a [ t2 ] 
 if t3 < v goto L 
 
 
100: t1 = i + 1 
101: i = t1 
102: t2 = i * 8 
103: t3 = a [ t2 ] 
104: if t3 < v goto 100 
Leiaute de Armazenamento para Nomes Locais 
• A partir do tipo de um nome (identificador), pode-se determinar a 
quantidade de memória necessária para ele durante a execução. 
 
• Em tempo de compilação, essa informação é utilizada para atribuir a cada 
nome um endereço relativo 
 
• O tipo e o endereço relativo são salvos na Tabela de Símbolos na entrada 
para o nome. 
 
• Os dados de tamanho variável (como as strings) ou os dados cujos 
tamanhos não podem ser determinados antes da execução são tratados 
reservando-se uma quantidade fixa e conhecida de memória para um 
apontador para os dados 
 
 
 
 
15 
Leiaute de Armazenamento para Nomes Locais 
• A memória é formada por blocos de bytes contíguos 
 
• Byte é a menor unidade de memória endereçável 
 
• Um byte possui 8 bits 
 
• Um objeto multibyte é armazenado em bytes consecutivos e seu endereço 
é aquele do primeiro byte 
 
• A largura (width) de um tipo é o número de unidades de memória 
necessárias para os objetos desse tipo 
 
 
 
 
16 
Leiaute de Armazenamento para Nomes Locais 
• Exemplo: um esquema de tradução para calcular o tipo e a largura de 
tipos básicos e arranjos. 
– type e width são atributos sintetizados 
 
 
 
 
 
 
 
17 
T → int { T.type = integer; T.width = 4; } 
T → float { T.type = float; T.width = 8; } 
Sequência de Declarações 
• Deve-se armazenar na Tabela de Símbolo o endereço relativo das variáveis 
(offset) 
 
• Endereço relativo: as variáveisdeclaradas dentro de um procedimento 
(por exemplo) são consideradas um grupo. Cada uma delas é armazenada 
em um endereço dentro de uma área destinada ao procedimento. 
 
• O esquema de tradução a seguir trata uma sequência de declarações da 
forma T id , onde T gera um tipo como na gramática mostrada 
anteriormente 
 
• Antes que a primeira declaração seja considerada, offset recebe 0. 
 
• Cada nova declaração é alocada no offset corrente. 
 
• O offset é, então, atualizado a partir da largura do tipo da declaração 
 
 
18 
Sequência de Declarações 
• top representa a tabela de símbolos corrente 
 
• top.put é um método que cria uma entrada na TS para id.lexeme, com 
tipo T.type e endereço relativo offset 
 
• A ação offset = 0; é executada antes da derivação de D 
 
 
 
 
19 
P → 
 D 
 
{ offset = 0;} 
D → T id; 
 
 D1 
{ top.put(id.lexeme, T.type, offset) ; 
 offset = offset + T.width; } 
D→ λ 
Sequência de Declarações 
• O mesmo esquema de tradução pode ser elaborado utilizando-se não-
terminal marcador 
 
• Um não-terminal marcador gera λ e é utilizado para reescrever as produções de 
modo que todas as ações semânticas apareçam nos extremos dos lados direitos 
das produções 
 
• Utilizando-se um marcador M, o esquema de tradução anterior pode ser reescrito: 
 
 
 
 
20 
P → M D 
M→ λ { offset = 0;} 
D → T id; 
 
 D1 
{ top.put(id.lexeme, T.type, offset) ; 
 offset = offset + T.width; } 
D→ λ 
Exercícios 
1. Em um compilador, tipo pode ser implementado como uma classe Type. 
Um dos campos dessa classe é a largura do tipo. 
Para os tipos atômicos, tanto o nome quanto a largura são pré-definidos. 
Para os tipos construídos, a descrição do tipo é representada por uma String e 
a largura é informada no construtor. 
 
Veja uma implementação da classe Type no apêndice A (página 608) do livro 
 
2. Em um compilador, temporário pode ser implementado como uma classe 
Temp. 
O objetivo dessa classe é gerar os nomes dos temporários (t1, t2, ..., tn) a 
serem utilizados na geração de código intermediário. 
 
Veja uma implementação da classe Temp no apêndice A (página 611) do livro 
 21 
Referência Bibliográfica 
Compiladores – Princípios, técnicas e ferramentas. 
Aho, A. V et al. 2ª edição 
Capítulo 6: 6.2 (6.2.1, 6.2.2), 6.3.4, 6.3.5, 6.3.6 
 
Modern Compiler Implementation in Java. Second Edition. 
Andrew W. Appel. 
Capítulo 7. 
 
 
 
 
 
22