11 GeracaoCodigo - Compiladores CEFET MG

Prévia do material em texto

Compiladores 
Prof.ª Kecia Aline Marques Ferreira 
CEFET-MG 
 
Geração de Código 
1 
Geração de Código 
 
• Introdução 
• Uma Máquina Virtual 
– Visão Geral 
– Organização da Máquina 
– Conjunto de Instruções 
– Exemplos de programas para a máquina virtual 
 
 
 
 
 
 
2 
Introdução 
• A última fase do compilador é a geração de código 
 
• O gerador de código tem como entrada: 
 
– As informações coletadas durante a análise e registradas na tabela de 
símbolos 
 
– A representação intermediária do código 
 
• O gerador de código tem como saída um código na linguagem alvo 
equivalente ao código fonte 
 
• Este material apresenta as características de uma máquina virtual para a 
qual será gerado código no trabalho prático realizado no curso 
 
 
 
3 
Máquina Virtual 
• VM : máquina virtual utilizada por universidades francesas e portuguesas. 
 
– É uma máquina de pilha (em oposição a máquina de registradores) 
 
– Todas as operações são realizadas com dados que estão na pilha 
Ex. ADD é uma instrução da máquina que desempilha dois inteiros da pilha, soma 
esses valores e empilha o resultado da soma 
 
– A máquina permite a manipulação fácil de dados do tipo inteiro, real e string 
 
– Em consequência, permite a manipulação de caractere e boolianos 
 
 
 
 
 
 
 
4 
Máquina Virtual 
• Link para baixar VM: 
http://www.lri.fr/~mandel/enseignement/projet-compilation/ 
No final da página 
 
O arquivo está disponível também no Moodle 
 
• Documentação em português de VM: 
http://epl.di.uminho.pt/~gepl/LP/vmdocpt.pdf 
 
A documentação será disponibilizada também no Moodle 
 
• Para executar VM: 
vm nome_do_arquivo_com_codigo_assembly 
 
 
 
 
5 
Organização da Máquina 
• A máquina possui: 
– Uma pilha de execução: na pilha são armazenados os valores que são 
processados ao longo da execução do programa. 
 Os valores podem ser inteiros, reais ou endereços. 
 
– Uma pilha de chamadas: a máquina mantém uma pilha de chamadas para 
controlar chamadas e retornos de procedimentos e funções 
 
– Uma área de código: é a área na qual é armazenado o programa a ser 
executado 
 
– Dois heaps: 
• Um contém cadeias de caracteres (strings) 
• O outro destina-se a armazenar blocos estruturados (registros) 
 
 
 
 
6 
Organização da Máquina 
– Quatro registradores: 
• sp (stack pointer): aponta para o topo corrente da pilha (próxima célula 
vazia da pilha) 
 
• fp (frame pointer): aponta para o endereço base das variáveis locais de 
um procedimento/função 
 
• gp (global pointer): aponta para o endereço de base da variáveis globais 
 
• pc (program counter): apontador para a instrução corrente 
 
 
 
 
7 
Organização da Máquina 
 
 
 
8 
Instruções 
pc 
Chamadas 
Pilha 
Heap de blocos 
 Olá 
Heap de strings 
sp 
fp 
gp 
Instruções 
• As instruções de VM são designadas por um nome e podem aceitar 
um ou dois parâmetros que podem ser: 
 
– Constantes inteiras 
– Constantes reais 
– Cadeias de caracteres delimitadas por aspas 
– Um rótulo simbólico (que corresponde a uma área de código) 
 
Exemplos: 
PUSHI 8 
PUSHS “Ola!” 
JUMP X 
 
 
 
 
 
9 
Convenções 
• A operação empilhar um valor x significa: 
– Colocar o valor x na célula Pilha[sp] 
– Incrementar o sp (sp = sp + 1) 
 
• A operação empilhar n vezes um valor x significa: 
– Repetir n vezes a operação anterior 
 
• Desempilhar n vezes significa 
– Decrementar de n o valor de sp (sp = sp - n) 
 
• O topo da pilha corresponde ao último elemento empilhado: 
– Pilha[sp-1] 
 
 
 
 
10 
Instruções de VM 
• Operações sobre inteiros: 
 Exemplos: 
 ADD, SUB, MUL 
 
• Operações sobre reais: 
 Exemplos: 
 FADD, FSUB, FMUL 
 
• Operação sobre endereço: 
PADD : desempilha n (que deve ser um inteiro) e a (que deve ser um endereço) e 
empilha o endereço a + n 
 
• Operação sobre endereço: 
CONCAT : desempilha n, depois desempilha m (que devem ser endereços de cadeias 
de caracteres ) e empilha o endereço de uma cadeia de caracteres resultante da 
concatenação da string endereçada por n com a string endereçada por m 
 
 
11 
Instruções de VM 
• Igualdade: 
EQUAL: desempilha n e m, que devem ser do mesmo tipo, e empilha o resultado de 
n==m 
 
• Empilhar: 
Exemplos: 
 
PUSHI n : empilha o valor inteiro n 
PUSHN n : empilha n vezes o valor 0 
PUSHF n : empilha o valor real n 
PUSHS s : armazena s no heap de strings e empilha o endereço de s 
PUSHL n : empilha o valor armazenado em fp[n] 
PUSHFP : empilha o valor de fp 
LOAD n : desempilha um endereço a e empilha o valor de a[n] 
 
 
 
 
12 
Instruções de VM 
• Desempilhar: 
 
POP n : desempilha n valores 
POPN : desempilha um inteiro n e desempilha n valores 
 
• Armazenar: 
STOREL n : desempilha um valor e armazena em fp[n] 
STORE n : desempilha um valor v e um endereço a. Armazena v em a[n] . 
 
• Entrada e saída: 
WRITEI : desempilha um inteiro e imprime seu valor 
READ: lê uma string do teclado, armazena-a no heap e empilha seu endereço 
 
 
 
 
 
13 
Instruções de VM 
• Controle: 
 
JUMP label 
PUSHA label: empilha o endereço de programa correspondente ao label 
CALL : 
 - desempilha um endereço de programa a 
 - salva pc e fp na pilha de chamadas 
 - atribui a fp o valor corrente de sp 
 - atribui a pc o valor de a 
 
RETURN: 
 - atribui a sp o valor corrente de fp 
 - restaura, a partir da pilha de chamadas, os valores de fp e pc 
 - incrementa pc de 1 (para continuar a execução) 
 
 
 
14 
Exemplos de programas para VM 
• Exibição de string: 
 
START 
PUSHS "Ola, mundo!" 
WRITES 
STOP 
 
• Concatenação de string: 
 
START 
PUSHS "Ferreira" 
PUSHS "Marques " 
PUSHS "Aline " 
PUSHS "Kecia " 
CONCAT 
CONCAT 
CONCAT 
WRITES 
STOP 
 
 
 
15 
Exemplos de programas para VM 
• Soma: 
 
START 
PUSHI 5 
PUSHI 10 
ADD 
WRITEI 
STOP 
 
• Entrada e saída: 
 
START 
PUSHS "A: " 
WRITES 
READ 
ATOI 
PUSHS "Valor informado: " 
WRITES 
WRITEI 
STOP 
 
 
 
16 
Exemplos de programas para VM 
• Procedimento 1: sem passagem de parâmetro 
 
program teste; 
 
var a,b: integer; 
 
procedure A; 
var x, y: integer; 
begin 
 x := 10; 
 y := x * 3; 
 write(y); 
end 
 
begin 
 A; 
end. 
 
 
 17 
Exemplos de programas para VM 
Um programa para VM 
 
//Variaveis globais 
START 
PUSHN 2 //reserva área de memória para 2 inteiros (a e b) e inicia com zero 
JUMP INICIO //vai para programa principal 
 
//Procedimento A 
A: PUSHN 2 //inicializa o valor de x e y, com zero 
 
 PUSHI 10 
 STOREL 0 //atribui 10 a x, cujo offset e 0 
 
 PUSHI 3 //empilha o valor 3 
 PUSHL 0 //empilha o valor de x, cujo offset é 0 
 MUL //faz x*3 e empilha o valor resultante 
 STOREL 1 // atribui o resultado a y, cujo offset e 1 
 
 PUSHL 1 //empilha o valor de y 
 WRITEI //imprime o valor de y 
 RETURN 
 
 
INICIO: PUSHA A 
 CALL //chama procedimento A 
 STOP 
 
 
18 
Exemplos de programas para VM 
• Procedimento 2: com passagem de parâmetro 
 
program teste; 
 
var a,b: integer; 
 
procedure A(i: integer, j:integer); 
var x, y: integer;begin 
 
 x := i + j; 
 y := x * 10; 
 write(y); 
 
end 
 
begin 
 a := 5; 
 b := 3; 
 A (a,b); 
 b := b * a; 
 write(b); 
end. 
19 
Exemplos de programas para VM 
Um programa para VM 
 
//Variaveis globais 
START 
PUSHN 2 //reserva área de memória para 2 inteiros (a e b) e inicia com 
 //zero 
JUMP INICIO //vai para programa principal 
 
//Procedimento A 
A: PUSHN 2 //inicializa o valor de x e y, com zero 
 
 PUSHL -2 
 PUSHL -1 
 ADD // i + j 
 STOREL 0 //atribui i + j a x, cujo offset e 0 
 
 PUSHI 10 //empilha o valor 10 
 PUSHL 0 //empilha o valor de x, cujo offset é 0 
 MUL //faz x*10 e empilha o valor resultante 
 STOREL 1 // atribui o resultado a y, cujo offset e 1 
 
 PUSHL 1 //empilha o valor de y 
 WRITEI //write(y) 
 RETURN 
 20 
Exemplos de programas para VM 
 
INICIO: PUSHI 5 
 STOREG 0 // a:=5 
 PUSHI 3 
 STOREG 1 // b:=3 
 PUSHG 0 //empilha o valor de a 
 PUSHG 1 //empilha o valor de b 
 PUSHA A 
 CALL 
 POP 2 //desempilha os valores a e b passados como parâmetro 
 PUSHG 1 //empilha o valor de b 
 PUSHG 0 //empilha o valor de a 
 MUL //b*a 
 STOREG 1 //b := b*a 
 PUSHG 1 
 WRITEI //write(b) 
 STOP 
21 
Exemplos de programas para VM 
• Procedimento 3: com passagem de parâmetro e aninhado 
 
22 
program teste; 
 
var a,b: integer; 
 
procedure A(i: integer, j:integer); 
var x, y, z: integer; 
begin 
 
 procedure B(k:integer) 
 var m:integer; 
 begin 
 m := k + 1; 
 write(m); 
 z := m +2; //variável z do procedimento A! 
 write(z); 
 end 
 x := i + j; 
 y := x * 10; 
 write(y); 
 B(2); 
 write(z); 
 
end 
 
begin 
 a := 5; 
 b := 3; 
 A (a,b); 
 b := b * a; 
 write(b); 
end. 
Exemplos de programas para VM 
Um programa para VM 
//Variaveis globais 
START 
PUSHN 2 //reserva área de memória para 2 inteiros (a e b) e inicia 
com zero 
JUMP INICIO //vai para programa principal 
 
//Procedimento A 
A: PUSHN 3 //inicializa o valor de x,y e z, com zero 
 JUMP INICIOA 
 
B: PUSHN 1 //reserva area para m 
 PUSHL -2 //obtém o parâmetro 
 PUSHI 1 
 ADD // k + 1 
 STOREL 0 // m:=k+1 
 PUSHL 0 
 WRITEI 
 //Acesso a variável em outro ambiente 
 PUSHL -1 //empilha o link de acesso a A 
 PUSHI 2 //empilha o offset de z em seu ambiente, que é 2 
 
 
23 
Exemplos de programas para VM 
 PUSHL 0 
 PUSHI 2 
 ADD // m+2 
 
 STOREN // z:= m+2 (Desempilha o valor, o offset e o link de acesso) 
 // armazena o valor em a[n] 
 PUSHL -1 //empilha o link de acesso a A 
 PUSHI 2 //empilha o offset de z em seu ambiente, que é 2 
 LOADN 
 WRITEI 
 
 RETURN 
 
INICIOA: PUSHL -2 
 PUSHL -1 
 ADD // i + j 
 STOREL 0 //atribui i + j a x, cujo offset e 0 
 
24 
Exemplos de programas para VM 
 
 PUSHI 10 //empilha o valor 10 
 PUSHL 0 //empilha o valor de x, cujo offset é 0 
 MUL //faz x*10 e empilha o valor resultante 
 STOREL 1 // atribui o resultado a y, cujo offset e 1 
 
 PUSHL 1 //empilha o valor de y 
 WRITEI //write(y) 
 PUSHI 2 //empilha o parâmetro 2 
 PUSHFP //empilha o valor do link de acesso 
 PUSHA B 
 CALL 
 POP 2 //desempilha parâmetro e link de acesso 
 
 PUSHL 2 
 WRITEI //write(z) 
 
 RETURN 
 
25 
Exemplos de programas para VM 
 
 INICIO: PUSHI 5 
 STOREG 0 // a:=5 
 PUSHI 3 
 STOREG 1 // b:=3 
 PUSHG 0 //empilha o valor de a 
 PUSHG 1 //empilha o valor de b 
 PUSHA A 
 CALL 
 POP 2 //desempilha os valores a e b passados como parâmetro 
 PUSHG 0 
 PUSHG 1 
 MUL //b*a 
 STOREG 1 //b := b*a 
 PUSHG 1 
 WRITEI //write(b) 
 STOP 
26 
Referência Bibliográfica 
Compiladores – Princípios, técnicas e ferramentas. 
Aho, A. V et al. 2ª edição 
Capítulo 8: até seção 7.3 (inclusive) 
 
Máquina Virtual 
http://epl.di.uminho.pt/~gepl/LP/vmdocpt.pdf 
 
 
 
 
 
 
 
 
 
27