Codigo Intermediario

Prévia do material em texto

Prof. Sergio da Costa FerreiraProf. Sergio da Costa Ferreira
sergiodcf@anhanguera.comsergiodcf@anhanguera.com
CompiladoresCompiladores
Geração de código intermediárioGeração de código intermediário
Compiladores
Introdução
 No modelo de análise e síntese de um compilador, 
os módulos de vanguarda traduzem o programa-
fonte numa representação intermediária, a partir da 
qual os módulos da retaguarda geram o código-
alvo.
ANALISADOR
LÉXICO
ANALISADOR
SINTÁTICO
ANALISADOR
SEMÂNTICO
GERADOR
CÓDIGO
INTERMEDIÁRIO
GERADOR
CÓDIGO
VANGUARDA RETAGUARDA
Compiladores
Introdução
 Apesar de se poder traduzir o programa-fonte 
diretamente para a linguagem-alvo, alguns 
benefícios em se usar uma forma intermediária 
independente da máquina são:
Um compilador para uma máquina diferente pode 
ser criado atrelando-se à vanguarda existente a 
uma retaguarda para a nova máquina.
Um otimizador de código independente da 
máquina pode ser aplicado à representação 
intermediária.
Compiladores
Linguagens Intermediárias
 As duas formas mais usuais de representação 
intermediária são:
Código de três endereços
Notação pós-fixa
Compiladores
Código de três endereços
 O código de três endereços é uma sequência de 
enunciados da forma geral:
 x := y op z
 Onde x, y e z são nomes, constantes ou objetos 
de dados temporários, op é qualquer operador.
 Não são permitidas expressões aritméticas 
construídas, na medida em que só há um operador 
no lado direito do enunciado. Então, uma 
expressão do tipo x+y*z seria traduzida assim:
 t1 := y * z
 t2 := x + t1
Compiladores
Código de três endereços
 O código nessa linguagem intermediária tem uma 
estrutura próxima daquela dos programas em 
linguagens simbólicas, cujas instruções 
representam as operações elementares do 
processador. Por esse motivo, um programa em 
linguagem intermediária pode ser facilmente 
convertido para uma linguagem-alvo.
 Uma especificação de uma linguagem de três 
endereços envolve quatro tipos básicos de 
instruções: (i) atribuição, (ii) desvios, (iii) invocação 
de rotinas e (iv) endereçamento.
Compiladores
Código de três endereços
 (i) Instruções de atribuição
Possui três formas básicas:
 Cópia de valor de uma variável para outra.
 le := ld
 Armazenar o resultado de uma operação.
 le := ld1 op ld2
 Aplicação de um operador unário.
 le := op ld
Compiladores
Código de três endereços
 (i) Instruções de atribuição
Expressões mais complexas demandam a 
utilização de variáveis intermediárias.
Ex.: a = b + c * d
Uma árvore sintática para essa expressão pode 
ser representada como
ld1
expr
op ld2:=le
b +=a op ld2.2ld2.1
* dc
Compiladores
Código de três endereços
 (i) Instruções de atribuição
Para a geração de código, uma estrutura de 
árvore simplificada é adotada.
Nessa representação, os operadores são 
representados nos nós internos.
=
+a
*b
dc
Compiladores
Código de três endereços
 (i) Instruções de atribuição
No nó * é utilizada outra operação, então na 
geração de código intermediário, esse nó é 
associado a uma variável temporária.
A expressão ficaria assim:
 t1 := c * d
 a := b + t1
Compiladores
Código de três endereços
 (ii) Desvios
Possuem duas formas básicas:
 Desvio incondicional
 goto L
L é o rótulo que identifica a linha do código
 Desvio condicional
 if x opr y goto L
opr é um operador relacional de 
comparação.
Compiladores
Código de três endereços
 (ii) Desvios
 Interação
 while (i++ <= k)
 x [ i ] = 0;
 x [ 0 ] = 0;
Tradução para código intermediário
 L1: if i > k goto L2
 i := i + 1
 x[i] := 0
 goto L1
 L2: x[0] := 0
Compiladores
Código de três endereços
 (iii) Invocação de rotinas
A invocação de rotina é normalmente realizada 
por uma instrução que altera o ponto de 
execução para outra região da memória ao 
mesmo tempo que preserva o ponto de execução 
atual, para retomá-lo quando a rotina for 
concluída.
Na linguagem de código intermediário, a 
instrução call realiza a chamada de rotina.
O retorno ao ponto de execução, após a 
conclusão da rotina, é realizada pela instrução 
return. 
Compiladores
Código de três endereços
 (iii) Invocação de rotinas
Também é usada a instrução param, que 
prepara cada um dos argumentos a serem 
consumidos pela rotina.
Rotina: x = f ( a, b, c )
 Tradução para código intermediário
 param a
 param b
 param c
 x := call f, 3
3 é o número de parâmetros da rotina.
Compiladores
Código de três endereços
 (iii) Invocação de rotinas
Outra rotina: a = g ( b, h(c) )
 Tradução para código intermediário
 param b
 param c
 t1 := call h, 1
 param t1
 a := call g, 2
 A rotina h consome o último argumento passado pela 
instrução param (c). Já a rotina g consome os dois 
argumentos que ainda não haviam sido consumidos 
por outras rotinas (b e t1).
Compiladores
Código de três endereços
 (iv) Endereçamento
Modo direto
 x := y
Modo indireto
 Está associado a manipulação de variáveis 
que contêm endereços.
 x := &y, atribuição do endereço da variável y 
à variável x.
 w := *x, atribuição do valor armazenado no 
endereço x à variável w.
 *x := z, atribuição do valor da variável z à 
posição endereçada por x.
Compiladores
Código de três endereços
 (iv) Endereçamento
 Expressão: *p1 = a + *p2++
 Tradução para código intermediário
 t1 := *p2
 p2 := p2 + 4
 t2 := a + t1
 *p1 := t2
O conteúdo do endereço indicado por *p2 é 
somado ao valor de a e o resultado é atribuído ao 
endereço indicado por *p1. A variável *p2 está 
sendo incrementada de uma posição, se o valor 
inteiro (1) foi definido como de 4 bytes, então *p2 
deve ser incrementado em 4.
Compiladores
Código de três endereços
 (iv) Endereçamento
Modo indexado
 x := y[i]
 Atribui à variável x o conteúdo do endereço 
indicado pela soma da variável y com o valor 
de i.
 Na linguagem intermediária, z[5] leva à 
posição que está 20 bytes adiante da posição 
de z, caso z seja um vetor de inteiros de 4 
bytes.
Compiladores
Código de três endereços
 (iv) Endereçamento
 Expressão: 
for (i=0; i<10; i++)
s[ i ] = a[ i ] + b[ i ]
 Tradução para código 
intermediário
 i := 0
L1: if i >= 10 goto L2
 t1 := 4*i
 t2 := a[t1]
 t3 := 4*i
 t4 := b[t3]
 t5 := t2 + t4
 t6 := 4*i
 s[t6] := t5
 i := i+1
 goto L1
L2: ...
Compiladores
Código de três endereços
 Representação interna
É feita dentro de uma estrutura de tabelas.
O armazenamento de instruções utiliza 
quádruplas, que são tabelas com quatro colunas.
Cada instrução é uma linha com a especificação 
de quatro elementos:
1º: operador
2º: primeiro argumento
3º: segundo argumento (se existir)
4º: resultado (se existir)
Compiladores
 Representação interna
 Expressão:
 a = b + c * d 
 z = f ( a )
 Código intermediário
 t1 := c*d
 a := b + t1
 param a
 z := call f, 1
operador arg1 arg2 resultado
1 * c d t1
2 + b t1 a
3 param a
4 call f 1 z
Tabela
Código de três endereços
Compiladores
Notação pós-fixa
 A notação tradicional para expressões aritméticas, que 
representa uma operação binária na forma x+y, ou 
seja, como operador entre seus dois operandos, é 
conhecida como notação infixa.
 Uma notação alternativa para esse tipo de expressão é 
a notação pós-fixa, na qual o operador é expresso após 
seus operandos.
 A vantagem desta notação é que ela dispensa o uso de 
parênteses ao adotar a noção de pilha para 
representação das expressões.
 Assim, quando um operador binário aparece na 
sequência, ele é aplicado aos dois últimos elementos e 
o resultado está disponível como um novo elemento.
Compiladores
Notação pós-fixa
 Exemplo
 Infixa: a + b
 Pós-fixa: a b +
 Ambos representam a mesma expressão, cuja árvore 
sintática é: +
ba
Compiladores
Notação pós-fixa
 Exemplo
 Infixa: a * b + c
 Pós-fixa: a b * c +
 Árvore sintática:
+
c*
ba
Compiladores
Notação pós-fixa
 Exemplo
 Infixa: a * ( b + c )
 Pós-fixa: a b c + *
 Árvore sintática:
*
+a
cb
Compiladores
Exercícios
 Escreva as expressões abaixo em código de três 
endereços
 x = (a + b + c) * (b + c) - d
 r = a * b + pow(c, 2)
 b[i] = a[i] + a[i-1]
Compiladores
Exercícios
 Escreva as expressões abaixo em notação pós-fixa
 a - (b - a * (c + b / d))
 (a + b) - (a - (c – d) * (e – f))
Compiladores
Exercícios
 Apresente o código intermediário de três endereços 
para o fragmento de código abaixo:
 
 i = 0;
 while (i < 10){
 a[i] = 0;
 i = i + 1;
 }
 x=i;
Compiladores
Exercícios
 Apresente o código intermediário de três endereços 
para o fragmento de código abaixo:
 
 if(i>10){
 a=i*b;
 b++;
 }else{
 b=a*i;
 a--;
 }
Compiladores
Exercícios
 Apresente o código intermediário de três endereços 
para o fragmento de código abaixo:
 
 if(a<b){
 x++;
 }else{
 if(c<d)
 y++;
 }
Compiladores
Bibliografia
 AHO, A.; ULLMANN, J.; REVI, S.. 
Compiladores: princípios, técnicas e 
ferramentas. 3ª ed. Rio de Janeiro: LTC – Livros 
Técnicos e Científicos, 2006.
 RICARTE, IVAN. Introdução à compilação. Rio 
de Janeiro: Elsevier: 2008.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 30
	Slide 33
	Slide 35
	Slide 37
	Slide 39