Aprenda a Matéria

Compiladores · Prova 2 · Tradução, Análise Semântica, Tipagem, Runtime e Geração de Código · leitura de ~60 minutos

1. O mapa da prova 3 min

A Prova 1 terminou na árvore sintática: o programa está bem escrito. A Prova 2 responde ao que vem depois: o programa faz sentido? E como ele vira instruções de máquina que rodam de verdade?

São duas metades:

1. Entender o programa (front-end, fase semântica): atributos na árvore (TDS), escopo e tabela de símbolos, regras de tipo. Pergunta típica: "compila? por quê?", "escreva a regra", "complete a tabela".
2. Produzir o código (back-end): como a memória fica organizada em execução (pilha, heap, registros de ativação, objetos) e como cada construção vira MIPS. Pergunta típica: "desenhe a pilha", "gere o MIPS do caller e do callee", "qual o layout do objeto".

2. Atributos e TDS 8 min

A ideia

A gramática diz só a forma. Para calcular algo enquanto se percorre a árvore (um valor, um tipo, um pedaço de código), cada símbolo ganha atributos e cada produção ganha regras semânticas que os calculam. Isso é a Tradução Dirigida por Sintaxe (TDS).

• Sintetizado: o atributo do pai (lado esquerdo da produção) é calculado a partir dos filhos. Sobe na árvore.
• Herdado: o atributo de um filho (lado direito) é calculado a partir do pai e/ou dos irmãos. Desce ou vai para o lado. Nas gramáticas L-atribuídas (todas as da disciplina), só dos irmãos à esquerda.

Método: escrever as regras

1. Descubra o que o atributo representa (valor decimal, tipo, lista de exceções).
2. Para cada produção, escreva o atributo da cabeça em função do corpo.
3. Recursão à esquerda que acrescenta um dígito: valor antigo × base + dígito.
4. Escreva o caso base. Teste com uma string curta, na mão.

B → B1 0   { B.valorDecimal = 2 · B1.valorDecimal }
B → B1 1   { B.valorDecimal = 2 · B1.valorDecimal + 1 }
B → 1      { B.valorDecimal = 1 }

Método: mostrar a ordem de avaliação

1. Desenhe a árvore de derivação (não terminais nos nós internos, tokens nas folhas). Numa questão de TDS é essa a "AST" esperada, porque os atributos ficam nos não terminais.
2. Percorra em profundidade, da esquerda para a direita.
3. Ao descer para um filho, calcule os herdados dele.
4. Ao voltar de todos os filhos, calcule os sintetizados do nó.
5. Numere as regras na ordem e mostre o valor de cada uma.

Esse percurso vale para gramática L-atribuída (herdados só usam herdados do pai e atributos dos irmãos à esquerda), que é o caso de todos os exemplos da disciplina. No caso geral, avalia-se numa ordenação topológica do grafo de dependências.

Outros moldes que já caíram

• Declarações D → T L {L.her = T.tipo}; L → L1 , id {L1.her = L.her; addTipo(id, L.her)}; L → id {addTipo(id, L.her)}. Em int a, b, c: inteiro desce por L, L1, L2 e cada id recebe addTipo.
• Exceções como "tipo" (Lista 3): S → throw id {S.exc = {id}}; S → S1 catch id ⇒ S2 {se id ∉ S1.exc: erro (catch supérfluo); S.exc = (S1.exc − {id}) ∪ S2.exc}; S → S1 or S2 {S.exc = S1.exc ∪ S2.exc}; S → e {S.exc = ∅}.
• Construir a AST: E → E1 + T {E.node = new Node('+', E1.node, T.node)}.

3. Erros, escopo e tabela de símbolos 7 min

Classificar um erro

1. Algum caractere ou literal não forma token (@ em C, string sem fechar, 3.4.5)? → léxico.
2. Os tokens existem, mas a ordem é impossível pela gramática (falta ;, (*f)..h, e.2[h], palavra-chave no lugar de expressão)? → sintático.
3. A frase está bem formada, mas não faz sentido com as declarações e tipos (tipo incompatível, nome não declarado ou duplicado, &(c.a + 1), campo inexistente, número de argumentos)? → semântico.
4. Compila, mas falha ao rodar com certos valores (índice fora do vetor, divisão por zero, ponteiro nulo, downcast inválido)? → execução.

Escopo

• Estático (léxico): decidido pelo texto. Regra: a declaração aninhada mais próxima do uso. C, Java, Go, Python.
• Dinâmico: decidido pela execução. Regra: a última declaração ativa na pilha de chamadas. Bash, LaTeX, LISP original, Emacs Lisp.
• Escopo × vida: escopo é onde o nome é visível no texto (estático); vida é quando a variável existe na execução (dinâmico).

Tabela de símbolos

É uma pilha de escopos: enter_scope() ao abrir bloco, add_symbol(x) na declaração, check_scope(x) para detectar declaração duplicada no mesmo escopo, find_symbol(x) procura do topo para o fundo, exit_scope() descarta o escopo. O ambiente de tipos O das regras de tipo é a formalização dela.

Método: completar a tabela num ponto do programa

1. Marque a linha pedida.
2. Liste os escopos abertos naquele ponto, do mais externo ao mais interno.
3. Em cada escopo aberto, liste o que foi declarado até ali: variáveis, parâmetros e nomes de procedimentos internos.
4. Escopos já encerrados somem; o nome do procedimento encerrado continua no escopo pai.
5. Tamanho: tipo básico = 1 palavra (4 B, salvo se o enunciado disser outra coisa); vetor [l..u] = (u − l + 1) × tamanho do elemento; procedimento = sem tamanho.
6. Resolva os nomes da linha pelo aninhado mais próximo.

Espaços de nomes (Java)

Tipos, métodos, variáveis e rótulos vivem em espaços separados; o contexto sintático decide qual consultar: seguido de ( → método; antes de um identificador declarado ou depois de class → tipo; seguido de : no início do comando, ou depois de break → rótulo; resto → variável. Nome antes de . → variável se existir uma com esse nome; senão tipo (a variável obscurece o tipo).

4. Regras de tipo e checagem 10 min

Os quatro eixos (independentes)

• Quando checa: estática (C, Java: em compilação; barra alguns programas corretos) × dinâmica (Python, JS: quase toda a checagem em execução).
• Equivalência: nominal (mesmo nome; herança pela árvore de nomes; Java, C++, COOL) × estrutural (mesma estrutura; Go interfaces, TypeScript, duck typing). Ambas permitem polimorfismo. Risco da estrutural: equivalência acidental (Ponto{x,y} ≡ Tamanho{x,y}).
• Segurança: fraca (converte implicitamente com perda, aceita casts arbitrários; C) × forte (rejeita sem conversão explícita). É um espectro, e forte não proíbe coerção (Java converte int → double).
• Declaração: explícita (int a = 7) × implícita (a = 7, tipo inferido).

let v = 42
if (v > 0) { v = "positivo" } else { v = 0 }
print(v + "!")

Ler e escrever uma regra de inferência

O ⊢ e : T lê-se "no ambiente O (que dá o tipo de cada variável), prova-se que e tem tipo T". Hipóteses ficam em cima do traço, a conclusão embaixo. Tipos sobem (dos filhos para o pai) e o ambiente desce. Nas regras abaixo, T1 ≤ T0 lê-se "T1 é subtipo de T0" e lub(T1, T2) é o menor ancestral comum dos dois (detalhes em Subtipos, lub e despacho).

Método: escrever a regra de uma construção nova

1. Uma hipótese O ⊢ ei : Ti para cada subexpressão.
2. Condições sobre os tipos (igualdade, ≤, BOOL na condição).
3. Se a construção declara variável, o corpo é checado em O[T/x].
4. Conclusão: a expressão inteira com o tipo resultante (lub se há ramos).

Árvore de prova

A prova tem a forma da AST: escolha a regra pelo nó raiz e suba até as folhas ([INT], [Var]).

Ordem de aplicação: APP, FUN, ADD, VAR, INT (3), INT (5). Regras: [Fun] O[T/x] ⊢ e : S ⇒ O ⊢ fun (x:T) → e : T → S; [App] O ⊢ e1 : T → S, O ⊢ e2 : T ⇒ O ⊢ e1 e2 : S.

Subtipos, lub e despacho

• X ≤ Y: reflexiva, vem da herança, transitiva. Um valor de X pode ser usado onde se espera Y.
• Despacho e0.f(e1, …, en): o compilador procura f no tipo estático T0 de e0 (M(T0, f)). Cada argumento real precisa ser subtipo do parâmetro formal (Ti ≤ Ti'). O resultado é o tipo de retorno de M.
• Se f não existe no tipo estático, é erro de compilação, mesmo que o objeto real tenha f.

Soundness, SELF_TYPE e ANY

• Sound: em toda execução, tipo_dinâmico(e) ≤ tipo_estático(e). Sem subtipos, são iguais.
• SELF_TYPE resolve Count* inc() { return this; } com Stock* a; a = a->inc(); (erro, pois Count ≰ Stock). Com SELF_TYPE inc(), o resultado tem o tipo estático do receptor: a.inc() é Stock. Regras: SELF_TYPE_C ≤ T se C ≤ T; T ≤ SELF_TYPE_C é sempre falso.
• Recuperação de erro: dar Object à expressão errada espalha erros em cascata; dar ANY (subtipo de todos, ⊥) faz nenhuma regra reclamar de novo.

Implementar uma função de checagem

ChecaTipo([O,M,C], e1 OP e2) =
  T1 = ChecaTipo([O,M,C], e1)
  T2 = ChecaTipo([O,M,C], e2)
  se condição(T1, T2): retorna tipo_resultado
  senão: erro   (linguagem fraca: tenta coerção antes)

• Soma estrita: condição T1 == T2 == INT, retorna INT.
• Atribuição x = e: T0 = O(x); T1 = ChecaTipo(O, e); se T1 ≤ T0 retorna T1; senão erro.
• Nullish e1 ?? e2, versão dinâmica: se T1 é null/undefined, retorna ChecaTipo(O, e2); senão T1. Versão estática: lub(T1 sem null/undefined, T2).
• Equivalência estrutural (struct, Lista 3): recursão nas duas árvores de tipo ao mesmo tempo. Básicos: iguais; array(n1, s) × array(n2, t): n1 = n2 e s ≡ t; ptr(s) × ptr(t): s ≡ t; struct: mesmo número de campos e cada par equivalente.
• Montar as árvores (Lista 3, Q11a): int *a → ptr(int); int b[10] → array(10, int); char *d[10] → array(10, ptr(char)); struct → struct(c: …, d: …). Em e1 = e2, a raiz já difere (struct × ptr) → erro. Flexibilizar: desreferenciar (*e2), promover char → int. Limite: int[10] e char[5] não se convertem sem inventar dados; a estrutural tem equivalência acidental.

Coerção em C (Lista 3)

• float f = 9 + 5.3: o checador acha o tipo comum no reticulado (char → int → float → double) e insere a conversão: 9 vira 9.0 (double, porque 5.3 é double), e o resultado 14.3 é convertido para float na inicialização de f.
• int n = 'c' + 1: char já é inteiro (99) → 100.
• char d = 5.4 + '?': '?' = 63 → 68.4 → truncado para 68 = 'D'. Compila (no máximo warning). C é "fraca": aceita conversão com perda.

5. Memória, registros de ativação e links 7 min

Onde cada variável fica

• Global (com ou sem const) e static local → área estática (endereço fixo; existe o programa inteiro).
• Local e parâmetro (com ou sem const) → pilha (vive enquanto a chamada está ativa).
• Bloco de malloc/new → heap; o ponteiro que guarda o endereço, se local, fica na pilha.
• const não muda o lugar; inicializar com rand() também não.

O registro de ativação (AR)

Cada chamada ativa tem um AR na pilha, com tudo o que é preciso para terminar a função e voltar para quem chamou. No modelo MIPS da disciplina, de cima (endereços maiores) para baixo:

1. $fp antigo (o link de controle) — empilhado pelo caller;
2. argumentos xn … x1 (ordem reversa, x1 fica mais perto do $fp) — caller;
3. endereço de retorno ($ra) — callee; $fp aponta aqui;
4. locais e temporários — callee.

Por isso x1 está em 4($fp), x2 em 8($fp), o $fp antigo em 4(n+1)($fp), e os locais em −4($fp), −8($fp)…

Método: desenhar a pilha

1. Escreva a sequência de chamadas até o ponto pedido (main → f(3) → f(2)).
2. Um bloco por ativação, da mais antiga (em cima) para a mais recente (embaixo).
3. Dentro do bloco: $fp antigo, argumentos com valores, endereço de retorno (diga para qual linha volta), locais (valor ou "?"), temporários salvos.
4. Marque $fp no endereço de retorno do bloco mais recente e $sp logo abaixo do último item.
5. Globais ficam fora (área estática). Função inline não cria AR. Objeto local C++ fica inteiro dentro do AR.

Links de controle e de acesso

• Controle (dinâmico): aponta para o AR de quem chamou; serve para restaurar o $fp no retorno. É o "$fp antigo".
• Acesso (estático): aponta para o AR da função que envolve no texto; serve para ler variáveis não locais quando há funções aninhadas. Para uma variável k níveis acima: seguir k links e somar o offset.
• Os dois diferem quando quem chama não é quem envolve. Compilação sabe o número de níveis e os offsets; execução sabe os endereços.

Certo ou Incorreto que já caiu

• "Desempilhar limpa a memória" (não caiu, mas é a base dos outros) → I: o valor continua lá até ser sobrescrito. No projeto inicial do slide 08, o callee grava o resultado no próprio AR e o caller o lê depois do pop; no modelo MIPS da disciplina, o resultado volta em $a0.
• "Alocação dinâmica só no heap" → I: alloca e vetores de tamanho variável alocam na pilha.
• "O AR garante integridade e segurança" → I: não há checagem de limites (estouro de buffer sobrescreve o retorno).
• "$sp e $fp são referências fixas" → I: só o $fp é fixo durante a ativação; $sp muda a cada push/pop.
• "Padding economiza memória" → I: gasta memória para alinhar ("hello\0", 6 bytes, ocupa 8).

6. Máquina de pilha e moldes cgen 8 min

O modelo

Uma máquina de pilha com um registrador acumulador, emulada em MIPS: o resultado de toda expressão fica em $a0; valores intermediários vão para a pilha na memória. A pilha cresce para endereços menores; $sp aponta para a próxima posição livre e o topo está em 4($sp).

push $a0:   sw $a0 0($sp)
            addiu $sp $sp -4
topo → $t1: lw $t1 4($sp)
pop:        addiu $sp $sp 4

C/I que caiu duas vezes (Lista 4 Q5, 2025/1): "a máquina de pilha é preferida por ser mais eficiente / usar menos instruções" → I (é mais simples de gerar, mas usa mais instruções e acessos à memória); "a máquina de registradores tem melhor desempenho" → C.

Os moldes

Comparações e desvios

Depois do pop: $t1 = e1, $a0 = e2. O desvio vai para o senão (ou para o fim do laço) quando a condição é falsa:

if, while, for, break

# if (cond) e3 else e4          # while (cond) corpo
  código da cond → desvia SENAO_k    INICIO_k:
  cgen(e3)                             código da cond → desvia FIM_k
  b FIM_k                              cgen(corpo)
SENAO_k:                               b INICIO_k
  cgen(e4)                           FIM_k:
FIM_k:

# for (init; cond; passo) corpo
  cgen(init)
TESTE_k:  código da cond → desvia FIM_k
  cgen(corpo)
PASSO_k:  cgen(passo)      # continue salta para cá
  b TESTE_k
FIM_k:                     # break salta para cá

• break = b FIM_k do laço mais interno. O gerador precisa receber o rótulo de saída (uma pilha de rótulos de laços) e, se houver valores empilhados, restaurar $sp.
• Ternário x := c ? e1 : e2: igual ao if; no FIM_k o valor está em $a0; depois sw $a0 off_x($fp).
• Cada uso gera rótulos novos (sufixo k), senão os saltos se confundem.

Chamada e definição de função

# caller: cgen(f(e1, …, en))     # callee: f(x1, …, xn) com k locais
sw $fp 0($sp)                   F_ENTRADA:
addiu $sp $sp -4                  move $fp $sp
cgen(en) / push                   sw $ra 0($sp)
…                                 addiu $sp $sp -4
cgen(e1) / push                   addiu $sp $sp -4k     # locais
jal F_ENTRADA                     cgen(corpo)           # → $a0
# resultado em $a0             F_SAIDA:
                                  addiu $sp $sp 4k      # libera locais
                                  lw $ra 4($sp)
                                  addiu $sp $sp z       # z = 4n + 8
                                  lw $fp 0($sp)
                                  jr $ra

• Caller empilha o $fp antigo e os argumentos: só ele sabe quantos e quais argumentos passa.
• Callee empilha o $ra: só ele sabe se chama outras funções e qual é o tamanho do seu AR; o código de salvar $ra aparece uma vez (na função), não em cada chamada.
• z = 4n + 8 desempilha os n argumentos, o $ra e o $fp antigo. Os locais são liberados antes do lw $ra 4($sp); se somar 4k no z sem liberar antes, o lw $ra lê um local e a função não volta.
• return e: cgen(e) / b F_SAIDA.

Temporários com posição fixa (NT)

Em vez de push/pop, os valores intermediários podem ficar em posições fixas do AR, reservadas na entrada. NT(e1 + e2) = max(NT(e1), 1 + NT(e2)); NT(int) = NT(id) = 0; NT(f(e1..en)) = max(NT(ei)). Com nt começando em 4: cgen(e1 + e2, nt) = cgen(e1, nt) / sw $a0 −nt($fp) / cgen(e2, nt+4) / lw $t1 −nt($fp) / add $a0 $t1 $a0. Isso vale sem locais; com k locais, nt começa em 4k + 4. Na entrada, reserve addiu $sp $sp −4·NT(e) logo depois de salvar o $ra; na saída, libere 4·NT(e) antes do lw $ra 4($sp) (z continua 4n + 8). Ex.: fib(x−1) + fib(x−2) → NT = 2.

li $a0 3
sw $a0 0($sp)
addiu $sp $sp -4
li $a0 7
sw $a0 0($sp)
addiu $sp $sp -4
li $a0 5
lw $t1 4($sp)
add $a0 $t1 $a0      # 12
addiu $sp $sp 4
lw $t1 4($sp)
add $a0 $t1 $a0      # 15
addiu $sp $sp 4

7. MIPS de função, passo a passo 10 min

Receita

1. Convenções primeiro, por escrito: parâmetros em 4($fp), 8($fp)…; locais em −4($fp), −8($fp)…; n = número de parâmetros; z = 4n + 8; k = número de locais.
2. Caller: push $fp, push dos argumentos do último para o primeiro, jal.
3. Entrada do callee: move $fp $sp, push $ra, addiu $sp $sp −4k.
4. Corpo: traduza comando a comando com os moldes da seção 6, criando rótulos únicos. Todo return deixa o valor em $a0 e vai para a saída.
5. Saída: addiu $sp $sp 4k, lw $ra 4($sp), addiu $sp $sp z, lw $fp 0($sp), jr $ra.
6. Confira o saldo: chame de S o $sp antes da chamada (no caller). Na entrada do callee, $sp = S − 4(n + 1). Antes do lw $ra 4($sp), $sp tem de ser S − 4(n + 2) (só o $ra abaixo dos argumentos). Depois do addiu z, $sp = S, apontando para o $fp antigo. Ao voltar, $sp é o mesmo de antes da chamada.

Exemplo completo (2026/1)

Convenções: a em 4($fp), b em 8($fp), i em −4($fp); n = 2, z = 16; k = 1.

# caller: f(10, 15)
sw $fp 0($sp)
addiu $sp $sp -4
li $a0 15             # b (o último argumento vai primeiro)
sw $a0 0($sp)
addiu $sp $sp -4
li $a0 10             # a
sw $a0 0($sp)
addiu $sp $sp -4
jal F_ENTRADA         # resultado em $a0

# callee
F_ENTRADA:
move $fp $sp
sw $ra 0($sp)
addiu $sp $sp -4
addiu $sp $sp -4      # espaço de i
lw $a0 4($fp)         # a
lw $t1 8($fp)         # b
beq $a0 $t1 VERDADEIRO_1
li $a0 0
b FIM_1
VERDADEIRO_1:
li $a0 5
FIM_1:
sw $a0 -4($fp)        # i = …
lw $a0 -4($fp)
addiu $a0 $a0 1       # i + 1
addiu $sp $sp 4       # libera i
lw $ra 4($sp)
addiu $sp $sp 16      # z = 4·2 + 8
lw $fp 0($sp)
jr $ra

Duas simplificações em relação aos moldes da seção 6: como a e b são variáveis, vão direto para $a0 e $t1, sem push/pop; e o desvio vai para o ramo verdadeiro (forma do slide 09), com o falso logo abaixo. A forma da tabela também vale: bne $a0 $t1 SENAO_1 / li $a0 5 / b FIM_1 / SENAO_1: li $a0 0 / FIM_1:.

Como 10 ≠ 15, i = 0 e f devolve 1. A pilha em cada momento (deslize para o lado):

Gerado executando o código acima num simulador MIPS: S é o $sp antes da chamada. Linhas em destaque estão empilhadas (acima de $sp); em cinza, valores que ficaram na memória depois de desempilhar (desempilhar não limpa).

Outras variações já cobradas

Laço com return no meio (2025/2)

int f() { int i = 0; while (i < 10) { int j = i + 1; for (; j < i − 1; j++) { if (j == 0) return −10; } i++; } return i; } — i em −4, j em −8; sem parâmetros, z = 8.

F_INICIO:
move $fp $sp
sw $ra 0($sp)
addiu $sp $sp -4
addiu $sp $sp -8          # i, j
sw $zero -4($fp)          # i = 0
WHILE_INICIO:
lw $a0 -4($fp)
slti $t1 $a0 10
beq $t1 $zero WHILE_FIM
lw $a0 -4($fp)
addiu $a0 $a0 1
sw $a0 -8($fp)            # j = i + 1
FOR_TESTE:
lw $a0 -8($fp)
lw $t1 -4($fp)
addiu $t1 $t1 -1
slt $t2 $a0 $t1           # j < i − 1 ?
beq $t2 $zero FOR_FIM
lw $a0 -8($fp)
bne $a0 $zero IF_FIM
li $a0 -10
b RETORNO                 # return −10
IF_FIM:
lw $a0 -8($fp)
addiu $a0 $a0 1
sw $a0 -8($fp)            # j++
b FOR_TESTE
FOR_FIM:
lw $a0 -4($fp)
addiu $a0 $a0 1
sw $a0 -4($fp)            # i++
b WHILE_INICIO
WHILE_FIM:
lw $a0 -4($fp)            # return i
RETORNO:
addiu $sp $sp 8
lw $ra 4($sp)
addiu $sp $sp 8
lw $fp 0($sp)
jr $ra

Como j = i + 1 > i − 1, o for nunca executa e f devolve 10. O código mantém a estrutura, que é o que a questão pede.

Global em endereço fixo (2025/1)

int b[10] em 0x600000: b[6] fica em 0x600000 + 24. lui $t1 0x0060 põe 0x00600000 em $t1; lw $a0 24($t1) lê b[6]. Em g(y, 5) + b[6] + b[7]: chama g (resultado em $a0), push, carrega b[6], lw $t1 4($sp), add, pop; repete para b[7].

# caller: f(2)
sw $fp 0($sp)
addiu $sp $sp -4
li $a0 2
sw $a0 0($sp)
addiu $sp $sp -4
jal F_ENTRADA
G_ENTRADA:               # g(x, m) = x * m
move $fp $sp
sw $ra 0($sp)
addiu $sp $sp -4
lw $a0 4($fp)             # x
lw $t1 8($fp)             # m
mult $a0 $t1
mflo $a0
lw $ra 4($sp)
addiu $sp $sp 16          # z = 4·2 + 8
lw $fp 0($sp)
jr $ra
F_ENTRADA:               # f(y) = g(y, 5) + b[6] + b[7]
move $fp $sp
sw $ra 0($sp)
addiu $sp $sp -4
sw $fp 0($sp)             # chamada g(y, 5)
addiu $sp $sp -4
li $a0 5                  # m
sw $a0 0($sp)
addiu $sp $sp -4
lw $a0 4($fp)             # x = y ($fp ainda é o de f)
sw $a0 0($sp)
addiu $sp $sp -4
jal G_ENTRADA             # $a0 = g(y, 5)
sw $a0 0($sp)             # push g(…)
addiu $sp $sp -4
lui $t1 0x0060
lw $a0 24($t1)            # b[6]
lw $t1 4($sp)
add $a0 $t1 $a0
addiu $sp $sp 4
sw $a0 0($sp)
addiu $sp $sp -4
lui $t1 0x0060
lw $a0 28($t1)            # b[7]
lw $t1 4($sp)
add $a0 $t1 $a0
addiu $sp $sp 4
lw $ra 4($sp)
addiu $sp $sp 12          # z = 4·1 + 8
lw $fp 0($sp)
jr $ra

Trechos soltos (Lista 4, Q11)

x = b * c:   lw $a0 off_b($fp) / lw $t1 off_c($fp) / mult $a0 $t1 / mflo $a0 / sw $a0 off_x($fp)
y = *q:      lw $t1 off_q($fp) / lw $a0 0($t1) / sw $a0 off_y($fp)
*p = y:      lw $t1 off_p($fp) / lw $a0 off_y($fp) / sw $a0 0($t1)
x = a[i]:    lw $t1 off_i($fp) / sll $t1 $t1 2 / lw $t2 off_a($fp) / add $t1 $t2 $t1 / lw $a0 0($t1) / sw $a0 off_x($fp)
q = q + 4:   lw $a0 off_q($fp) / addiu $a0 $a0 4 / sw $a0 off_q($fp)

No a[i], lw $t2 off_a($fp) vale quando a variável guarda o endereço-base (ponteiro ou parâmetro). Se o vetor está inteiro dentro do AR (int a[N] local em −4N … −4($fp)), a base é addiu $t2 $fp −4N.

8. Objetos: layout e despacho 6 min

Layout

• Objeto contíguo. Cabeçalho: tag da classe em 0, tamanho em palavras em 4, ponteiro da tabela de despacho em 8. Atributos a partir de 12, na ordem da classe: herdados primeiro, novos no fim.
• Por isso cada prefixo é um objeto válido da superclasse: código compilado para A funciona com B sem saber que B existe.
• Tabela de despacho: uma por classe (não por objeto), com os endereços dos métodos. Cada método tem offset fixo em toda a hierarquia; redefinir troca o endereço; método novo vai no fim. Construtores não entram.

Despacho dinâmico em MIPS (Lista 4, Q8)

cgen(e.f(arg)) com e já avaliado em $a0; f recebe self e arg:

sw $a0 0($sp)          # guarda e
addiu $sp $sp -4
sw $fp 0($sp)          # início da chamada
addiu $sp $sp -4
cgen(arg)
sw $a0 0($sp)          # arg (x2)
addiu $sp $sp -4
lw $a0 12($sp)         # recupera e
beq $a0 $zero ERRO_NULO
sw $a0 0($sp)          # self (x1, o último)
addiu $sp $sp -4
lw $t1 8($a0)          # tabela de despacho do objeto
lw $t1 OF_f($t1)       # endereço de f (offset fixo)
jalr $t1               # chamada indireta
addiu $sp $sp 4        # descarta o e guardado

• Em f: self em 4($fp), arg em 8($fp); n conta self, então z = 4·2 + 8 = 16.
• Compilação fixa os offsets (8 para a tabela, OF_f para o método). Execução decide qual tabela (a da classe dinâmica do objeto) e, portanto, qual implementação roda.
• jalr, não jal: o endereço só é conhecido em execução.
• Atributo dentro de um método: lw $t1 4($fp) (self) / lw $a0 12($t1) lê o 1º atributo; sw $a0 12($t1) escreve.

COUNT_ENTRADA:
move $fp $sp
sw $ra 0($sp)
addiu $sp $sp -4
addiu $sp $sp -16         # c inteiro
li $a0 TAG_CONTADOR
sw $a0 -16($fp)
li $a0 4
sw $a0 -12($fp)
la $a0 CONTADOR_DISP
sw $a0 -8($fp)
li $a0 10
sw $a0 -4($fp)            # cont = 10
LACO:
lw $a0 -4($fp)
slt $t1 $zero $a0         # 0 < cont ?
beq $t1 $zero FIM
lw $a0 -4($fp)
addiu $a0 $a0 -1
sw $a0 -4($fp)            # countdown inline
b LACO
FIM:
addiu $sp $sp 16
lw $ra 4($sp)
addiu $sp $sp 8
lw $fp 0($sp)
jr $ra

Herança múltipla e interfaces

• O objeto concatena os subobjetos dos pais, cada um com cabeçalho e tabela própria. Upcast para o 2º pai soma o offset do subobjeto; downcast subtrai e precisa checar o tipo em execução (RTTI).
• Conflito (diamante): mesmo método ou atributo em dois pais → chamada ambígua e atributo da base duplicado. Saídas: sobrescrever na subclasse, qualificar (A::f), linearização (MRO C3 do Python), herança virtual (C++).
• Interfaces não têm atributos: o layout continua de herança simples e o cast não muda o endereço.

9. Avulsas 4 min

Seleção de instruções por ladrilhamento (2025/1)

Cada regra de tradução é um padrão de árvore (tile) com custo. Cobrir a AST com tiles de custo total mínimo. Tiles da prova: #1 Ri ← Add(Ri, Rj) custo 2; #2 Ri ← Add(Ri, Kc) custo 3; #3 Ri ← Kc custo 2; #4 Ri ← Add(Ri, Add(Rj, Kc)) custo 4. Expressão Add(Add(K1, K2), Add(K3, K4)):

1. #3 LOADI R1, K1 (2)
2. #2 ADDI R1, K2 (3) → R1 = K1 + K2
3. #3 LOADI R2, K3 (2)
4. #4 ADDRI R1, R2, K4 (4) → R1 = R1 + (R2 + K4)

Por que código ótimo nem sempre sai: em DAGs (subexpressões comuns) a seleção ótima é NP-completa; a escolha interage com alocação de registradores e escalonamento; os custos reais dependem do contexto. Na prática: maximal munch (maior tile a partir da raiz) ou programação dinâmica em árvores.

Literais maiores que a palavra (2025/2)

Um unsigned int32 numa máquina de w bits ocupa k = ⌈32/w⌉ palavras: parte[i] = (n >> i·w) & (2ʷ − 1). w = 8 → 4 partes; w = 16 → 2; w = 64 → 1 (extensão com zeros). Faixa 0 ≤ n ≤ 2³² − 1, senão erro semântico. 4294967295 = 0xFFFFFFFF → em 16 bits, [0xFFFF, 0xFFFF]; nunca tratar como int32 com sinal (viraria −1). Operações propagam o carry entre as partes.

Compilado × interpretado

• Compilado: execução rápida, otimização global, erros antes de rodar, não precisa do compilador para executar; um binário por arquitetura, ciclo editar-compilar mais longo.
• Interpretado: portável, ciclo rápido, recursos dinâmicos (eval, tipagem dinâmica); mais lento, erros aparecem tarde.
• Híbrido: bytecode + máquina virtual + JIT (Java, V8). Compilar ou interpretar é propriedade da implementação, não da linguagem.

Qualidade de um gerador de código

Corretude (preserva a semântica) em primeiro lugar; depois velocidade e tamanho do código, uso de registradores e memória, tempo de compilação, energia. O gerador depende da arquitetura (instruções, registradores, alinhamento).

10. Roteiro de prova 2 min

• Regras semânticas → Uma regra por produção; caso base; teste com string curta (seção 2).
• Herdado ou sintetizado → Qual atributo está sendo definido: da cabeça (sintetizado) ou do corpo (herdado).
• Ordem da TDS → Árvore de derivação; herdados ao descer, sintetizados ao voltar; numere.
• Classificar erros → Token? Ordem? Sentido? Só ao rodar? (seção 3).
• Tabela de símbolos → Escopos abertos na linha; o que foi declarado até ali; tamanhos; resolva os nomes.
• Regra de inferência → Uma hipótese por subexpressão + condições de tipo ⇒ conclusão (seção 4).
• "Compila?" → Use o tipo estático; diga a linha e o motivo; proponha cast ou virtual.
• Região da variável → Global/static → estática; local/parâmetro → pilha; new/malloc → heap.
• Desenhe a pilha → Um bloco por chamada; $fp antigo, argumentos, retorno, locais; $fp e $sp marcados.
• Links → Controle → quem chamou. Acesso → quem envolve no texto. k níveis = k links + offset.
• MIPS de função → Convenções escritas; caller; entrada; corpo com moldes; saída; conferir o saldo de $sp.
• Layout / despacho → tag 0, tamanho 4, disp 8, atributos 12+; tabela por classe com offsets fixos; lw 8($a0), lw OF($t1), jalr.
• Certo/Incorreto → Procure a palavra exagerada; justifique em uma linha.