LRM Prof. Mantovani ← Aulas da disciplina
Semana 10 · Aula 10 de 14

Representação intermediária

A ponte entre front-end e back-end: por que uma RI existe, o código de três endereços e a tradução dirigida pela sintaxe que o gera a partir da árvore.

📚 Compiladores🧪 1 simulador(es)📝 mini-quiz ao final
Objetivos da aula

O que você vai aprender

1

Justificar o uso de uma representação intermediária no compilador.

2

Ler, escrever e gerar código de três endereços (TAC).

3

Conhecer formas de implementar a RI (quádruplas, triplas) e tipos de RI.

4

Conectar a geração de RI à árvore sintática via SDT.

1 · Motivação

Por que não ir direto ao assembly?

Seria possível traduzir a árvore sintática diretamente para o assembly de cada máquina. Mas com m linguagens e n máquinas isso exigiria m×n tradutores. A representação intermediária (RI) quebra esse produto em uma soma.

Ao gerar primeiro uma forma neutra, independente de máquina, reaproveitamos otimizações e back-ends. É exatamente a estratégia do LLVM e a razão de a RI ser a peça central do compilador.

💡
Com uma RI comum: m front-ends + n back-ends = m+n módulos, em vez de m×n.
2 · Mapa

O meio do caminho

A RI fica entre a análise (front-end) e a síntese (back-end):

Árvore sintática→RI
3 endereços→Otimização→Código-alvo

Tudo o que vem antes depende da linguagem; tudo o que vem depois depende da máquina. A RI é o ponto de encontro neutro.

3 · Conceito

O que é o código de três endereços

Código de três endereços (TAC). Sequência de instruções da forma x = y op z, com no máximo um operador por instrução e até três operandos (dois de origem, um de destino). Resultados parciais ficam em variáveis temporárias (t1, t2, …).

O nome vem dos três "endereços" envolvidos: dois operandos e um destino. É uma linguagem-assembly idealizada, sem as restrições de uma máquina real.

4 · Explicação

Por que decompor em passos mínimos

Cada instrução TAC faz uma operação só. Uma expressão complexa vira uma sequência linear de operações simples, com temporários ligando uma à outra.

  • Facilita a otimização: operações isoladas são fáceis de reordenar, eliminar ou combinar.
  • Facilita a geração de código: cada instrução TAC mapeia para poucas instruções de máquina.
  • É independente de máquina: não assume número de registradores nem conjunto de instruções.
5 · Exemplo

Traduzindo uma expressão

A expressão a + b * c respeita a precedência: multiplica antes de somar.

// a + b * c em três endereços t1 = b * c t2 = a + t1

E (a + b) * c, com parênteses, inverte a ordem:

// (a + b) * c t1 = a + b t2 = t1 * c
6 · Interativo

Gere TAC passo a passo

Passo 1
O parser monta a árvore respeitando precedência: * liga mais forte que + e -.
Passo 2
Visita o nó b * c primeiro (mais profundo): emite t1 = b * c.
Passo 3
Sobe ao nó a + (b*c): emite t2 = a + t1.
Passo 4
Sobe ao nó (...) - d: emite t3 = t2 - d.
Passo 5
O atributo "lugar" da raiz é t3: o resultado final da expressão.
7 · Conceito

A RI como atributo na SDT

Geração via SDT. Gerar TAC é uma tradução dirigida pela sintaxe em que cada nó sintetiza dois atributos: lugar (a variável/temporário que guarda seu valor) e cod (a sequência de instruções que o calcula).
// regra para soma; novoTemp() cria t novo E → E1 + T { E.lugar = novoTemp(); E.cod = E1.cod || T.cod || gerar(E.lugar '=' E1.lugar '+' T.lugar) }
8 · Explicação

Os atributos lugar e cod

A geração de código intermediário é exatamente a gramática de atributos da aula 8 aplicada com um propósito concreto:

  • lugar é sintetizado: o nome do temporário onde o valor do nó ficou.
  • cod é sintetizado: a concatenação do código dos filhos mais a instrução do próprio nó.
  • novoTemp() gera nomes frescos (t1, t2, …) para evitar colisões.
💡
Repare: o código dos filhos vem antes da instrução do pai, pois os valores parciais precisam existir primeiro.
9 · Analogia

A receita decomposta

🍳 Analogia
Uma expressão é um prato; o TAC é a receita escrita em passos atômicos: "bata os ovos (t1)", "adicione farinha a t1 (t2)", "asse t2 (t3)". Cada linha faz uma coisa só, na ordem em que precisa acontecer. Os temporários são as tigelas intermediárias onde você guarda cada etapa antes de combiná-las.
10 · Comparação

Quádruplas × triplas

O TAC pode ser representado internamente de formas diferentes:

QuádruplaTripla
Camposop, arg1, arg2, resultadoop, arg1, arg2 (sem resultado nomeado)
TemporáriosNomeados explicitamente (t1, t2)Referência ao número da tripla
Reordenar códigoFácilDifícil (referências por posição)
MemóriaMaiorMenor
💡
Há ainda as triplas indiretas, que usam uma lista de ponteiros para as triplas, recuperando a facilidade de reordenação.
11 · Fluxo

Da árvore à sequência linear

Árvore→Percurso
pós-ordem→Emite TAC
por nó→Sequência
linear

A árvore (hierárquica) vira uma lista (sequencial) de instruções. O percurso pós-ordem garante que os operandos de cada instrução já foram calculados quando ela é emitida.

12 · Aprofundamento

Outros estilos de RI

O TAC linear não é a única RI possível. As principais famílias:

  • RI gráfica: a própria árvore sintática abstrata (AST) ou o DAG (que compartilha subexpressões repetidas).
  • RI linear: código de três endereços, bytecode de pilha (como o da JVM).
  • SSA (Static Single Assignment): cada variável recebe valor uma única vez; facilita muitas otimizações modernas.
💡
Um compilador real costuma usar várias RIs em níveis diferentes: alta (perto do fonte) e baixa (perto da máquina).
13 · Interativo

Verifique seu entendimento

Quantos operadores no máximo aparecem em uma instrução de três endereços?

A forma x = y op z tem exatamente um operador; expressões maiores são quebradas em várias instruções com temporários.
14 · Caso prático

Uma atribuição completa

Veja como x = a + b * 2 vira TAC, incluindo a atribuição final:

// x = a + b * 2 t1 = b * 2 t2 = a + t1 x = t2

A última instrução copia o resultado para a variável de destino. Em uma versão otimizada, t2 poderia ser eliminado e escreveríamos x = a + t1 diretamente.

15 · Erros comuns

Tropeços ao gerar TAC

⚠️
Ignorar a precedência. Gerar t1 = a + b antes de b * c em "a + b * c" produz código com o significado errado.

Reusar temporários cedo demais. Sobrescrever um temporário ainda necessário corrompe o cálculo. Use novoTemp() para nomes frescos.

Emitir a instrução do pai antes da dos filhos. O operando precisa existir antes de ser usado.

Achar que t1, t2 são registradores. São temporários lógicos; a alocação real vem só na geração de código.
16 · Dicas

Gerando TAC com segurança

✅
Deixe a árvore resolver a precedência: gere TAC percorrendo-a em pós-ordem e a ordem sairá correta de graça.

Use um contador global para novoTemp(): nomes sempre frescos, sem colisão.

Concatene o cod dos filhos antes da instrução do pai.

Mantenha o TAC independente de máquina: nada de supor número de registradores nesta fase.
17 · Interativo

Pense antes de revelar

Por que a multiplicação aparece antes da soma no TAC de "a + b * c", se a soma está mais à esquerda no texto?
Porque o TAC reflete a estrutura da árvore sintática, não a ordem do texto. A precedência faz com que b * c seja um filho mais profundo (subárvore do termo), enquanto a soma fica na raiz. O percurso pós-ordem visita os nós mais profundos primeiro, então b * c é avaliado e emitido (t1 = b * c) antes da soma (t2 = a + t1). A posição no texto não determina a ordem de avaliação; a árvore determina.
18 · Flashcards

Revise os termos

TACvirar
Código de três endereços: instruções x = y op z, um operador cada, com temporários.
Temporáriovirar
Variável t1, t2… criada pelo compilador para guardar resultados parciais.
Quádruplavirar
Representação do TAC com 4 campos: op, arg1, arg2, resultado. Fácil de reordenar.
SSAvirar
Static Single Assignment: cada variável recebe valor uma única vez; facilita otimizações.
19 · Conexões

Como esta aula se liga ao curso

  • Usa a aula 5 (GLC): a precedência codificada na gramática determina a ordem das instruções geradas.
  • Usa a aula 8 (atributos): gerar TAC é uma SDT com atributos lugar e cod.
  • Usa a aula 2 (front/back-end): a RI é justamente o que desacopla as duas pontas.
  • Prepara a aula 12 (código): o TAC é a entrada da geração de código de máquina.
20 · Síntese

O essencial da aula

🔑
A RI desacopla front-end e back-end (m+n em vez de m×n) e habilita otimização reaproveitável. O código de três endereços usa instruções x = y op z com temporários, gerado por uma SDT que sintetiza os atributos lugar e cod percorrendo a árvore. A precedência da gramática define a ordem das instruções.
Mão na massa · colaborativo

Atividade em grupo · Tradutores humanos

Em trios, gerem TAC à mão e comparem com o simulador.

⏱️ 25 min👥 trios🧩 laboratório

Roteiro

  1. Escolham 3 expressões de complexidade crescente (ex.: a*b+c, (a+b)*(c-d), a+b*c-d/e).
  2. Gerem o código de três endereços à mão, respeitando precedência.
  3. Confiram no simulador da aula.
  4. Discutam onde surgiram os temporários e por quê.
Geradorproduz o TAC à mão
Conferentevalida no simulador
Analistaexplica os temporários
📤 Entrega: TAC manual das 3 expressões + comparação com o simulador.
Teste seu conhecimento

Mini-quiz · Aula 10

20 questões sobre esta aula. Escolha e veja a explicação na hora.

0/20

📌 Resumo — leve isto para a prova

  • A RI desacopla front-end e back-end (m+n em vez de m×n) e habilita otimização reaproveitável.
  • TAC: instruções x = y op z, um operador cada, com temporários.
  • A geração de RI é uma SDT que sintetiza os atributos lugar e cod.
  • Quádruplas, triplas, DAG e SSA são formas distintas de representar a RI.
  • A precedência da gramática (via árvore) determina a ordem das instruções geradas.