9 Geração de Código Intermediário Parte2 - 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 
 
• Expressões 
• Expressões Boolianas 
• Comandos 
– Condicional 
– Repetição 
 
 
 
 
 
 
2 
Geração de Código Intermediário 
• Objetivo: traduzir expressões para código de três endereços 
 
 
• addr: 
– atributo que denota o endereço que conterá o valor da expressão 
– Lembrete: endereço, neste contexto, pode ser um nome, uma 
constante ou um temporário gerado pelo compilador 
 
• top: 
– denota a tabela de símbolos corrente 
– top.get: recupera a entrada na tabela de símbolos correspondente a 
id.lexeme 
 
 
 
 
 
3 
Geração de Código Intermediário 
 
• gen: 
– em um esquema de tradução, é uma função que monta a instrução e a 
emite de forma incremental, colocando-a no fluxo de instruções 
geradas. 
– gen(x ‘=’ y + z) representa a instrução de três endereços x = y + z 
 
 
• new Temp(): 
– obtém um novo temporário (t1, t2, t3, etc.) 
 
 
 
 
4 
Expressões 
• Tradução dirigida por sintaxe para geração de código de três 
endereços para expressões 
 
 
 
 
5 
S→ id := E; { gen (top.get(id.lexeme) ‘=’ E.addr) ; } 
E→ E1 + E2 { E.addr = new Temp(); 
 gen (E.addr ‘=’ E1.addr + E2.addr); } 
E→ - E1 
 
{ E.addr = new Temp(); 
 gen (E.addr ‘=’ ‘minus’ E1.addr); } 
E→ ( E1 ) { E.addr = E1.addr; } 
 
E→ id { E.addr = top.get(id.lexeme); } 
 
Fluxo de Controle 
• Considere a tradução de expressões boolianas para o código de três 
endereços no contexto dos comandos como aqueles gerados pela 
gramática a seguir: 
 
S → if (B) S1 
S → if (B) S1 else S2 
S → while (B) S1 
S → {L} 
S → A; 
L → LS | S 
 
 
• Expressões boolianas são definidas segundo a gramática: 
 
B → B || B | B && B | ! B | ( B ) | E rel E | true | false 
 
 
 
6 
Fluxo de Controle 
• A tradução de expressões boolianas e de comandos de fluxo de controle 
como if, if-else e while envolvem o uso de desvios (goto, em código de três 
endereços) 
 
• Por exemplo, o comando 
 
 if (x < 100 || x > 200 && x != y) x = 0; 
 
 Pode ser traduzido para 
 
 if x < 100 goto L2 
 goto L3 
L3: if x > 200 goto L4 
 goto L1 
L4: if x != y goto L2 
 goto L1 
L2: x=0 
L1: 
 
 
7 
Fluxo de Controle 
• Rótulos podem ser representados simbolicamente (L1, L2, ..., Ln) 
 
• Outra possibilidade é utilizar diretamente os endereços das 
instruções nos comandos de desvio 
 
• Exemplo: 
 
100 if x < 100 goto 106 
101 goto 102 
102 if x > 200 goto 104 
103 goto 107 
104 if x != y goto 106 
105 goto 107 
106 x=0 
107 
 
 
8 
Fluxo de Controle 
• Problema: quando se gera código para expressões boolianas e comandos 
de fluxo de controle, como saber o destino do desvio em uma instrução de 
desvio? 
 
• Remendo (Backpatching): é uma abordagem que permite a geração de 
código para expressões boolianas e comandos de fluxo de controle em um 
passo. 
 
– Esta técnica consiste em: 
 
• quando um desvio é gerado, o objeto do desvio fica temporariamente 
sem especificação; 
 
• cada desvio desse tipo é colocado em uma lista de desvios cujos rótulos 
serão preenchidos quando o rótulo apropriado puder ser determinado 
 
• todos os desvios de uma lista possuem o mesmo rótulo de destino. 
 
 
9 
Fluxo de Controle 
• Nos esquemas de tradução mostrados a seguir para geração de código de 
boolianos e comandos de fluxo de controle, são utilizados os seguintes 
atributos: 
 
• truelist: é um atributo do não terminal B. É uma lista de instruções (endereço 
da instrução) de desvio para as quais deverá ser inserido um rótulo para o 
qual o fluxo flui se B for verdadeiro. 
 
• falselist: é um atributo do não terminal B. É uma lista de instruções (endereço 
da instrução) de desvio para as quais deverá ser inserido um rótulo para o 
qual o fluxo flui se B for falso. 
 
À medida que o código é gerado para B, os desvios para as saídas verdadeiro e 
falso são deixados incompletos, com o campo de rótulo não preenchido. 
 
Esses desvios incompletos são inseridos nas listas B.truelist ou B.falselist, como for 
apropriado. 
 
 
 
10 
Fluxo de Controle 
• nextlist: é um atributo do não terminal S. É uma lista de instruções 
(endereço da instrução) com desvio para a instrução imediatamente após 
o código de S. 
 
• Exemplo de código com desvios incompletos: 
 
100 if x < 100 goto _ 
101 goto _ 
102 if x > 200 goto _ 
103 goto _ 
104 if x != y goto _ 
105 goto _ 
106 x=0 
107 
 
 
 
11 
Fluxo de Controle 
• Instruções podem ser geradas diretamente em um arquivo ou 
armazenadas em arranjo de instruções 
 
• Consideraremos, aqui, que as instruções são geradas em um arranjo 
– Os rótulos são os índices desse arranjo 
 
• Para manipulação de uma lista de desvio, são usadas três funções: 
 
– makelist(i): 
 
• cria uma lista contendo apenas i 
• i é um índice para o arranjo de instruções 
• retorna o apontador para a lista recém criada 
 
 
 
12 
Fluxo de Controle 
– merge(p1, p2): 
 
• concatena as listas apontadas por p1 e p2 
• retorna o apontador para a lista concatenada 
 
– backpatch(p, i): 
 
• insere i como rótulo de destino para cada uma das instruções na 
lista apontada por p 
 
• A variável nextinstr contém o índice da instrução seguinte a determinada 
instrução 
 
• A função emit escreve uma instrução no arranjo e atualiza nextinstr 
 
 
13 
Fluxo de Controle 
• A seguir, será mostrada a tradução dirigida por sintaxe para geração de código 
de três endereços para expressões boolianas 
 
• Usamos o atributo rel.op para indicar qual dos operadores relacionais é 
representado por rel 
 
 
 
 
 
 
• Neste caso, não há instrução de desvio condicional a ser gerado. O desvio é 
incondicional. 
• Para a constante true, não há falselist a ser gerada, pois não há caso em que 
resulte em falso. 
• O raciocínio é similar para a constante false 
 
 
 
14 
B → true { B.truelist = makelist(nextinstr); 
 emit (‘goto _’); } 
B → false { B.falselist = makelist(nextinstr); 
 emit (‘goto _’); } 
 
Fluxo de Controle 
• Na expressão de comparação: 
– A primeira instrução a ser gerada é uma de desvio condicional que 
avalia se o resultado é verdadeiro 
– Com isso, B.truelist deve receber o índice desta instrução que será 
gerada (nextinstr), para posterior remendo 
– A segunda é um desvio incondicional para a instrução posterior (ao 
comando if , por exemplo) 
– Com isso, B.falselist deve receber o índice desta instrução que será 
gerada (nextinstr + 1), para posterior remendo 
 
 
 
 
 
 
 
 
15 
B → E1 rel E2 { B.truelist = makelist(nextinstr); 
 B.falselist = makelist(nextinstr + 1); 
 emit(‘if’ E1.adr rel.op E2.addr ‘goto _’); 
 emit (‘goto _’); } 
Fluxo de Controle 
• No caso de B → (B1), deve-se copiar as listas de B1 para B 
 
• No caso de B → !B1 , como o valor avaliado será invertido, deve-se copiar 
as listas de B1 para B, porém invertidas: B1.falselist para B.truelist e 
B1.truelist para B.falselist 
 
 
 
 
 
 
 
 
 
 
 
16 
B → (B1) { B.truelist = B1.truelist; 
 B.falselist = B1.falselist; } 
B → !B1 
 
{ B.truelist = B1.falselist; 
 B.falselist = B1.truelist; } 
Fluxo de Controle 
• No caso de B → B1|| B2:– Se B1 for verdadeiro, então B também é verdadeiro, de modo que os desvios em 
B1.truelist tornam-se parte de B.truelist 
– Se B1 for falso, é preciso avaliar B2: 
• Os destinos para os desvios B1.falselist deve ser o início do código gerado para B2 
• Para encontrar esse endereço, é incluído um não terminal auxiliar M, ao qual é 
associada a ação semântica que define esse endereço 
• Esse endereço é usado para remendar B1.falselist 
• Se B2 for verdadeiro, então B é verdadeiro, de modo que os desvios em B2.truelist 
tornam-se parte de B.truelist 
• Se B2 for falso, então B é falso, de modo que os desvios em B2.falselist tornam-se 
parte de B.falselist 
 
 
 
 
 
 
 
 
17 
B → B1|| M B2 { backpatch(B1.falselist, M.instr); 
 B.truelist = merge(B1.truelist, B2.truelist) ; 
 B.falselist = B2.falselist; } 
M → λ 
 
{ M.instr = nextinstr; } 
Fluxo de Controle 
• No caso de B → B1&& B2: 
– Se B1 for falso, então B também é falso, de modo que os desvios em B1.falselist tornam-
se parte de B.falselist 
– Se B1 for verdadeiro, é preciso avaliar B2: 
• Os destinos para os desvios B1.truelist deve ser o início do código gerado para B2 
• Para encontrar esse endereço, é incluído um não terminal auxiliar M, ao qual é 
associado a ação semântica que define esse endereço 
• Esse endereço é usado para remendar B1.truelist 
• Se B2 for falso, então B é falso, de modo que os desvios em B2.falselist tornam-se 
parte de B.falselist 
• Se B2 for verdadeiro, então B é verdadeiro, de modo que os desvios em B2.truelist 
tornam-se parte de B.truelist 
 
 
 
 
 
 
 
 
18 
B → B1 && M B2 { backpatch(B1.truelist, M.instr); 
 B.truelist = B2.truelist; 
 B.falselist = merge(B1.falselist, B2.falselist) ; } 
Fluxo de Controle 
• Exemplo: considere a expressão x<100 || x>200 && x!=y 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
19 
B 
B B M || 
E rel E 
x 100 
B && M B 
E rel E 
x 200 
E rel E 
x y 
100 if x<100 goto _ 
101 goto 102 
102 if x>200 goto 104 
103 goto _ 
104 if x!= y goto _ 
105 goto _ 
B.t = {100} 
B.f = {101} 
M.instr = 102 
B.t = {102} 
B.f = {103} 
M.instr = 104 
B.t = {104} 
B.f = {105} 
backpatch(B1.truelist, M.instr); 
B.t = {104} 
B.f = {105,103} 
backpatch(B1.falselist, M.instr); 
B.t = {100,104} 
B.f = {105,103} 
Fluxo de Controle 
• A seguir, será mostrada a tradução dirigida por sintaxe para geração de 
código de três endereços para comandos de fluxo de controle 
 
• A gramática considerada é : 
S → if (B) S1 
S → if (B) S1 else S2 
S → while (B) S1 
S → {L} 
S → A; 
L → LS | S 
 
 
 
 
 
 
20 
Fluxo de Controle 
• No comando S → if (B) S1 : 
– Se B for avaliado como verdadeiro, deverá haver um desvio para a primeira instrução de 
S1 
– S.nextlist é a lista de instruções com rótulos não preenchidos em S, que devem ser 
preenchidos. 
– B.falselist deverá compor a S.nextlist 
– S.nextlist contém todos os desvios, condicionais e incondicionais, para a instrução após 
o código do comando S 
– S1.nextlist também deve compor a S.nextlist 
 
 
 
 
 
 
 
 
 
21 
S → if (B) M S1 { backpatch(B.truelist, M.instr); 
 S.nextlist = merge(B.falselist, S1.nextlist) ; } 
M → λ { M.instr = nextinstr; } 
Fluxo de Controle 
• Exemplo: considere o comando if (x<100 || x>200 && x!=y) x=10 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
22 
B 
100 if x<100 goto 106 
101 goto 102 
102 if x>200 goto 104 
103 goto _ 
104 if x!= y goto 106 
105 goto _ 
106 x=10 
107 
backpatch(B1.falselist, M.instr); 
B.t = {100,104} 
B.f = {105,103} 
S 
if ( M ) S 
A 
M.instr = 106 
Gera código para atribuição 
S.nextlist = null 
backpatch(B.truelist, M.instr); 
S.nextlist = {105,103} 
Em um ponto seguinte, deverá ser realizado um remendo 
nas instruções de S.nextlist para o endereço 107 (que segue 
o fim do comando condicional) 
Fluxo de Controle 
• No comando S → if (B) S1 else S2: 
– Remendamos os desvios, quando B é verdadeiro (B.truelist), com o valor do endereço 
da primeira instrução de S1 
– Para encontrar esse endereço, utilizamos o marcador M1 
– Como, neste caso, o código gerado para S2 não deverá ser executado, haverá uma 
instrução de desvio. Utilizaremos o marcado N para gerar essa instrução. 
– Remendamos os desvios, quando B é falso (B.falselist), com o valor do endereço da 
primeira instrução de S2 
– Para encontrar esse endereço, utilizamos o marcador M2 
– S.nextlist deverá conter os desvios contidos nas nextlist de S1, N e S2 
 
 
 
 
 
 
 
 
 
23 
S → if (B) M1 S1 N else M2 S2 { backpatch(B.truelist, M1.instr); 
 backpatch(B.falselist, M2.instr); 
 temp = merge(S1.nextlist, N.nextlist); 
 S.nextlist = merge(temp, S2.nextlist) ; } 
N → λ { N.nextlist = makelist(nextinstr); 
 emit(‘goto _’); } 
Fluxo de Controle 
• No comando S → while (B) S1: 
– Quando B é verdadeiro, deverá haver um desvio para a primeira instrução de S1 
– Remendamos os desvios, quando B é verdadeiro (B.truelist), com o valor do endereço 
da primeira instrução de S1 
– Para encontrar esse endereço, utilizamos o marcador M2 
– No final das instruções do comando while, deverá haver um desvio para a primeira 
instrução desse comando 
– Para encontrar esse endereço, utilizamos o marcador M1 
– S1.nextlist deve ser remendado com o endereço da instrução encontrado em M1 
– S.nextlist conterá B.falselist 
 
 
 
 
 
 
 
 
 
24 
S → while M1 (B) M2S1 { backpatch(S1.nextlist, M1.instr); 
 backpatch(B.truelist, M2.instr); 
 S.nextlist = B.falselist; 
 emit (‘goto’ M1.instr); } 
Fluxo de Controle 
• Demais regras da gramática 
– S → {L} : deve-se fazer S.nextlist receber L.nextlist 
 
– L → L1 M S: 
• Os desvios em L1.nextlist devem ser remendados com o endereço da primeira 
instrução de S. Encontramos esse endereço como visto anteriormente, utilizando 
um marcador M. 
• Deve-se fazer L.nextlist receber S.nextlist 
 
– L → S : deve-se fazer L.nextlist receber S.nextlist 
 
 
 
 
 
 
 
 
 
 
25 
S → { L } { S.nextlist = L.nextlist; } 
L → L1 M S { backpatch(L1.nextlist, M.instr); 
 L.nextlist = S.nextlist; } 
L → S { L.nextlist = S.nextlist; } 
Exercícios 
1. O que é e para que serve código de três endereços? 
 
2. No processo de geração de código, armazenamos informações sobre 
largura e offset de variáveis: 
 
1. O que o atributo offset representa? 
2. Como estes dois dados são coletados? Explique somente o mecanismo 
que permite a coleta dessas informações e com base em quê isso é 
realizado. 
3. Onde esse dados são armazenados? 
 
 
 
 
 
 
 
 
26 
Exercícios 
 
3. Explique o que é e para que serve backpatching. 
 
4. Mostre uma árvore de derivação anotada (como aquela do slide 19) e o 
código de três endereços para if (b < 30) c=1; 
 
 
 
 
 
 
 
 
 
 
 
 
 
27 
Referência Bibliográfica 
Compiladores – Princípios, técnicas e ferramentas. 
Aho, A. V et al. 2ª edição 
Capítulo 6: 6.4, 6.7 (até 6.7.3, inclusive) 
 
 
 
 
 
 
 
 
28