Geração de código

1
 Fases de um compilador

Código C
Programa fonte if(a >= b+1){
a *= 2;
}
Análise Lexical

Front-end
Análise Sintática
Análise

Análise Semântica

Geração Rep. Intermédia

Código 3 Endereços
Representação _t1 = b + 1
Intermédia _t2 = a < _t1
if _t2 goto L0
Optimização RI
Back-end
Síntese ou
geração Geração de código

Optimização de código

Código Assembly
Programa ld [%fp-16], %10
destino add %10, 1, %10
2
 Simplificação

•Vamos saltar da fase da Análise Semântica

directamente para a fase de Geração de Código

•Não vamos ter uma representação intermédia (RI) de

baixo nível. Temos apenas uma RI de alto nível: a
árvore sintática

•Também não vamos ver a parte da Otimização

 Simplificação

•NOTA: Num compilador real estas fases que estamos

a ignorar deveriam existir, porque permitem que o
código gerado seja mais eficiente

4
 Geração de código

•A geração de código pode ser feita percorrendo a

árvore sintática de forma sistemática, gerando o
código apropriado para cada tipo de regra da
gramática

•Podemos descrever esse processo através de code

templates
- uma espécie de ”receita” em como gerar o código

5
 Geração de código

•A geração de código é relativamente simples, com

excepção para as instruções de controlo de fluxo

•O código gerado pode ser guardado num array de

“instruções” que ao final são gravados num ficheiro
em forma de bytecodes

•Em tudo semelhante ao modo como está a ser feito

para o vosso trabalho prático 1

6
 Geração de código

•O array de “instruções” vai sendo preenchido

sequencialmente
- Temos uma variável ip (instruction pointer) que aponta para
a próxima posição do array a ser preenchida

•O método emit(...) guarda uma instrução (e

eventuais argumentos) na posição ip do array.

7
 Code templates

•Imaginemos uma linguagem que diz que um programa válido

consiste numa sequência de declarações de variáveis, seguido
de uma sequência de instruções.
•Seja ‘prog’ o símbolo inicial da gramática. Temos:

prog --> varDeclarations statements

•Podemos fazer um code template que nos diz como gerar

código para ‘prog’

8
 Code template: programa

prog --> varDeclarations statements

GenCode( prog ):
GenCode( varDeclarations )
GenCode( statements )
emit( HALT )

9
 Code template: varDeclarations

varDeclarations --> declaration*

GenCode( varDeclarations ):
for each declaration d
GenCode( d )

E assim sucessivamente até chegarmos a casos base

em que usamos o método emit(...) directamente

10
 Code template: expressão unária

•A geração de código é muitas vezes descrita/implementada

de forma recursiva.

•Exemplo: para uma expressão unária

expr --> op expr1

•Código gerado:
GenCode( expr ):
GenCode( expr1 )
GenCode( op )
11
 Code template: expressão binária

•Para uma expressão binária

expr --> expr1 op expr2

•Código gerado:
GenCode( expr ):
GenCode( expr1 )
GenCode( expr2 )
GenCode( op )

12
 Observação

•Os exemplos ilustrados anteriomente para código de

expressões aplicam-se quando se gera código para
uma máquina de stack

•Para uma máquina de registos seria diferente

13
 Code template: print statement

stmt --> ‘print’ expr

GenCode( stmt ):
GenCode( expr )
switch( [Link] ) {
case INT: emit( IPRINT ); break;
case REAL: emit( DPRINT ); break;
case BOOL: emit( BPRINT ); break;
case STRING: emit( SPRINT ); break;
}

14
 Code template: assign statement

stmt --> ID = expr

GenCode( stmt ):
GenCode( expr )
emit( STORE, addr )

- addr denota o endereço onde está localizado a variável

associada ao token ID. Este endereço pode e deve ser guardado
na tabela de símbolos.

- STORE faz pop() do runtime stack, e guarda esse valor na

posição de memória especificada por ‘addr’
15
 Endereços de variáveis globais

•Há que fazer distinção entre variáveis globais e locais.

Deixaremos o tratamento de variáveis locais para
mais tarde.

•Para as variáveis globais, podemos atribuir endereços

às variáveis sequencialmente à medida que
processamos as declarações.

•Guarda-se o endereço como um atributo do

respectivo símbolo, na tabela de símbolos.

16
 Endereços de variáveis globais

•No caso geral, o número de posições de memória

varia consoante o tipo de dados.

•No caso do nosso trabalho, simplificamos e usamos

apenas 1 posição de memória para cada valor.
- A nossa VM usa as funcionalidades do Java e a memória
global é simulada com um array de objectos.

17
 Instruções de controlo de fluxo

Estes casos são mais delicados

•while

•if

18
 Code template: while statement

while_stmt --> ‘while’ expr ‘do’ stmt

GenCode( while_stat ):
beginWhile: GenCode( expr )
emit( JUMPF, endWhile )
GenCode( stmt )
emit( JUMP, beginWhile )
endWhile:

- JUMP efectua um salto para a linha de código especificada

- JUMPF efectua um salto condicional: faz pop() do stack e se o valor for

‘false’ salta para a linha de código especificada
19
 Argumentos dos JUMPs

•Problema: ao gerar o código podemos não saber qual

a linha de código que devemos especificar como
argumento do JUMP/JUMPF

•No exemplo anterior, quando emitimos JUMPF não

temos maneira de saber qual a linha de código
correspondente ao ”endWhile”
- só sabemos isso após gerar o código correspondente ao
corpo do while

20
 Back-patching

•Podemos resolver este problema usando uma técnica

chamada back-patching

•A ideia é colocar um endereço “fictício” e mais tarde

quando soubermos o verdadeiro valor, alteramos
esse valor fictício com o valor correcto

21
 Back-patching

•No exemplo anterior, emitiriamos “JUMPF -1” e

guardamos algures o endereço desta instrução
-1 é o nosso valor “fictício”

•Após terminar a geração de código do corpo do

while, emitimos o “JUMP beginWhile” que salta para
o início do ciclo (Esta posição também tem de ser
guardada.)

22
 Back-patching

•Nesse momento sabemos qual é a posição

imediatamente após o código do while: é a posição
imediatamente a seguir à do “JUMP beginWhile”

23
 Em pseudocódigo

while_stmt --> ‘while’ expr ‘do’ stmt

GenCode( while_stat ): ip() retorna o valor do

instruction pointer
ip_beginWhile = ip()
GenCode( expr )
ip_JUMPF = ip()
emit( JUMPF, -1 ) backpatch(p,v) vai à
linha p do array de
GenCode( stmt ) instruções e substitui o
valor do argumento que
emit( JUMP, ip_beginWhile ) lá está por v

backpatch( ip_JUMPF, ip() )

24
•A instrução if e todas as instruções de controlo de
fluxo usam a mesma técnica.

25
 Code template: if (sem else)

if_stmt --> ‘if’ expr ‘then’ stmt

GenCode( if_stmt ):
GenCode( expr )
emit( JUMPF, endIf )
GenCode( stmt )
endIf:

26
 Code template: if-else

if_else_stmt --> ‘if’ expr ‘then’ stmt1 ‘else’ stmt2

GenCode( stmt ):
GenCode( expr )
emit( JUMPF, elseL )
GenCode( stmt1 )
emit( JUMP, endIf )
elseL: GenCode( stmt2)
endIf:

27