Síntese: geração de código intermédio

Código de triplo endereço

O padrão para expressões é um exemplo duma representação muito utilizada para geração de código baixo nível (em geral, intermédio, e não final), designada por codificação de triplo endereço (TAC).

Esta designação tem origem nas instruções com a forma: x = y op z.

No entanto, para além desta operação típica de expressões binárias, esta codificação contém outras instruções (ex: operações unárias e de controlo de fluxo).

No máximo, cada instrução tem três operandos (i.e. três variáveis ou endereços de memória).

Tipicamente, cada instrução TAC realiza uma operação elementar (e já com alguma proximidade com as linguagens de baixo nível dos sistemas computacionais).

TAC: Exemplo de expressões binárias

Por exemplo a expressão a + b ∗ (c + d) pode ser transformada na sequência TAC:

Esta sequência – embora fazendo uso desregrado no número de registos (o que, num compilador gerador de código máquina, é resolvido numa fase posterior de optimização) – é codificável em linguagens de baixo nível.

TAC: Endereços e instruções

Nesta codificação, um endereço pode ser:

• Um nome do código fonte (variável, ou endereço de memória);

• Uma constante (i.e. um valor literal);

• Um nome temporário (variável , ou endereço de memória), criado na decomposição TAC.

As instruções típicas do TAC são:

1. Atribuições de valor de operação binária: x = y op z;

2. Atribuições de valor de operação unária: x = op y;

3. Instruções de cópia: x = y;

4. Saltos incondicionais e etiquetas: goto L e label L;

5. Saltos condicionais: if x goto L ou ifFalse x goto L;

6. Saltos condicionais com operador relacional: if x relop y goto L (o operador pode ser de igualdade ou ordem);

7. Invocações de procedimentos (param x 1 · · · param x n ; call p, n ; y = call p, n ; return y);

8. Instruções com arrays (i.e. o operador é os parêntesis rectos, e um dos operandos é o índice inteiro).

9. Instruções com ponteiros para memória (como em C)

Controlo de fluxo

As instruções de controlo de fluxo são as instruções condicionais e os ciclos.

Em linguagens de baixo nível muitas vezes estas instruções não existem.

O que existe em alternativa é a possibilidade de dar “saltos” dentro do código recorrendo a endereços (labels) e a instruções de salto (goto, . . . ).

De forma similar podemos gerar código para ciclos:

Funções

A geração de código para funções pode ser feita recorrendo a uma estratégia tipo “macro” (i.e. na invocação da funções é colocado o código que implementa a função), ou implementando módulos algorítmicos separados.

Neste último caso (que, entre outras coisas, permite a recursividade), é necessária a definição de um bloco algorítmico separado, assim como implementar a passagem de argumentos/resultado para/de a função.

A passagem de argumentos pode seguir diferentes estratégias: passagem por valor, passagem por referência de variáveis, passagem por referência de objectos/registos.

Para termos implementações recursivas é necessário que se definam novas variáveis em cada invocação da função.

A estrutura de dados que nos permite fazer isso de uma forma muito eficiente e simples é a pilha de execução.

Esta pilha armazena os argumentos, variáveis locais à função e o resultado da função (permitindo ao código que invoca a função não só passar os argumentos à função como ir buscar o seu resultado).

Geralmente as arquitecturas de linguagens de baixo nível (CPU’s) têm instruções específicas para lidar com esta estrutura de dados.