INÍCIO
Livros do Prof.
Representações Intermediárias em Compiladores
Uma visão completa sobre Árvores de Sintaxe Abstrata (AST) e outras representações intermediárias essenciais no processo de compilação.
Por que usar Representações Intermediárias?
Representações Intermediárias (IR) são estruturas de dados que servem como ponte entre o código-fonte e o código de máquina. Elas transformam o código em uma forma que facilita análises e otimizações.
As IRs abstraem detalhes da linguagem fonte e da máquina alvo, permitindo que o compilador trabalhe com uma forma mais uniforme e manipulável do programa original.
IRs possibilitam que compiladores realizem otimizações independentes de plataforma antes de gerar código específico para determinada arquitetura.
Onde entra o IR na cadeia do compilador?
Análise Léxica e Sintática
Reconhecimento de tokens e construção da árvore sintática a partir do código-fonte.
Análise Semântica
Verificação de tipos e outras regras semânticas da linguagem.
Geração de IR
Criação da representação intermediária (AST, Triplas, Quadruplas).
Otimização
Aplicação de técnicas para melhorar desempenho e tamanho do código.
Geração de Código
Tradução da IR para o código da máquina alvo.
A IR é gerada após as análises iniciais e serve como base para as etapas posteriores de otimização e geração de código.
Vantagens do uso de IR na compilação
Modularidade
Permite dividir o compilador em front-end (análise do código-fonte) e back-end (geração de código objeto), facilitando manutenção e extensão.
Portabilidade
Com IRs, é possível criar compiladores para múltiplas plataformas reutilizando o front-end e apenas adaptando o back-end para cada arquitetura alvo.
Otimização
Facilita a aplicação de algoritmos de otimização independentes da linguagem fonte e da máquina alvo, melhorando o desempenho do código gerado.
Análise
Simplifica a implementação de verificadores estáticos, analisadores de fluxo de dados e outras ferramentas de análise de código.
Diferença entre árvore sintática concreta e abstrata
Árvore Sintática Concreta
  • Representa todos os elementos da gramática
  • Inclui tokens como parênteses e ponto-e-vírgula
  • Reflete exatamente a estrutura da gramática
  • Contém muitos nós que não afetam a semântica
Árvore Sintática Abstrata (AST)
  • Representa apenas a estrutura essencial
  • Omite parênteses, pontuação e outros tokens auxiliares
  • Foca na semântica e não na sintaxe exata
  • Mais compacta e direta para processamento
Definição de AST
Uma Árvore de Sintaxe Abstrata (AST) é uma representação em árvore da estrutura sintática abstrata do código-fonte, onde cada nó denota uma construção importante na linguagem.
A AST captura a essência estrutural do programa, eliminando detalhes sintáticos desnecessários para o processamento posterior. Diferentemente da árvore sintática concreta, a AST omite símbolos gramaticais como chaves, parênteses e delimitadores.
Esta representação serve como base ideal para análise semântica, otimização e geração de código, pois destaca as relações importantes entre os elementos do programa sem o ruído de detalhes sintáticos.
Exemplo visual: expressão aritmética → AST
Na expressão a + b * c, a AST reflete corretamente a precedência de operadores. O operador de multiplicação * forma um subárvore com b e c, e este subárvore inteiro torna-se o operando direito da operação de adição com a.
Observe como a AST preserva naturalmente a ordem correta de avaliação: primeiro b * c e depois a adição do resultado com a, sem necessidade de parênteses ou regras adicionais.
Comparação: Árvore concreta vs. AST
Para a expressão: a * (b + c)
A árvore concreta inclui nós para parênteses e reflete cada regra da gramática, resultando em uma estrutura mais volumosa.
A AST é mais enxuta, contendo apenas os nós essenciais: operadores e operandos. Os parênteses desaparecem, pois sua função já está incorporada na estrutura da árvore.
A AST é mais adequada para otimizações e análises posteriores por não conter elementos supérfluos da sintaxe.
Elementos da AST: nós, operadores, folhas
Nós Internos
Representam operadores ou construções da linguagem (if, while, etc.)
Cada nó interno tem pelo menos um filho, representando os operandos ou subexpressões
Folhas
Representam valores literais, variáveis ou identificadores
Não possuem filhos e geralmente contêm informações como nome da variável ou valor da constante
Estrutura Completa
A raiz representa a operação principal ou construção de mais alto nível
A profundidade reflete a complexidade e aninhamento das expressões
A AST codifica implicitamente a ordem de avaliação através da relação hierárquica entre seus nós, seguindo as regras de precedência da linguagem.
Estrutura de nós (Node) em Python
class Node:
    def __init__(self):
        pass
        
    def __str__(self):
        pass

class BinOp(Node):
    def __init__(self, left, op, right):
        self.left = left
        self.op = op
        self.right = right
        
    def __str__(self):
        return f"({self.left} {self.op} {self.right})"

class Num(Node):
    def __init__(self, value):
        self.value = value
        
    def __str__(self):
        return str(self.value)

class Var(Node):
    def __init__(self, name):
        self.name = name
        
    def __str__(self):
        return self.name
Esta estrutura básica permite representar expressões aritméticas em Python, onde cada tipo de nó é uma classe que herda de uma classe base comum.
Classe base para AST – exemplo com operadores
class AST:
    pass

class BinOp(AST):
    def __init__(self, left, op, right):
        self.left = left
        self.op = op
        self.right = right

class UnaryOp(AST):
    def __init__(self, op, expr):
        self.op = op
        self.expr = expr

class Assign(AST):
    def __init__(self, left, right):
        self.left = left
        self.right = right

class Var(AST):
    def __init__(self, token):
        self.token = token
        self.value = token.value

class Num(AST):
    def __init__(self, token):
        self.token = token
        self.value = token.value
Esta implementação mais completa permite representar não apenas operações binárias, mas também atribuições e operações unárias, cobrindo os casos mais comuns em linguagens de programação.
Construção manual de AST simples (a + b * c)
# Construção manual da AST para "a + b * c"
a = Var(Token('ID', 'a'))
b = Var(Token('ID', 'b'))
c = Var(Token('ID', 'c'))

# Primeiro b * c (precedência maior)
mult = BinOp(b, Token('MUL', '*'), c)

# Depois a + (b * c)
expr = BinOp(a, Token('PLUS', '+'), mult)

# A variável expr agora contém a AST completa
Neste exemplo, construímos manualmente a AST para a expressão a + b * c, respeitando a precedência de operadores. Na prática, essa construção seria automatizada pelo analisador sintático.
Visualização em pré-ordem, pós-ordem
Pré-ordem (raiz-esquerda-direita)
def preorder(node):
    if node is None:
        return
    print(node)
    preorder(node.left)
    preorder(node.right)
Para a + b * c: +, a, *, b, c
Pós-ordem (esquerda-direita-raiz)
def postorder(node):
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node)
Para a + b * c: a, b, c, *, +
Útil para gerar código de pilha!
Os diferentes percursos de árvore são fundamentais para várias aplicações: pós-ordem é útil para gerar código de máquinas de pilha, enquanto pré-ordem pode ser útil para análise.
Usando a biblioteca ast do Python
import ast

# Código fonte para análise
source = "a = b + c * d"

# Parsear o código para AST
tree = ast.parse(source)

# Imprimir a AST de forma legível
print(ast.dump(tree, indent=4))

# Resultado:
# Module(
#     body=[
#         Assign(
#             targets=[Name(id='a', ctx=Store())],
#             value=BinOp(
#                 left=Name(id='b', ctx=Load()),
#                 op=Add(),
#                 right=BinOp(
#                     left=Name(id='c', ctx=Load()),
#                     op=Mult(),
#                     right=Name(id='d', ctx=Load())
#                 )
#             )
#         )
#     ]
# )
Python oferece uma biblioteca embutida ast que permite analisar código Python e gerar ASTs automaticamente, facilitando manipulação e análise de código.
O que são notações intermediárias?
Notações intermediárias são formas padronizadas de representar código entre a análise sintática e a geração de código final. Enquanto ASTs preservam a estrutura hierárquica, outras notações como código de três endereços (TAC) ou SSA (Static Single Assignment) aproximam-se mais do código de máquina.
Linearização
Transformam a estrutura hierárquica da AST em uma sequência linear de instruções, mais próxima do código de máquina.
Explicitação
Tornam explícitas operações que estavam implícitas na AST, como ordem de avaliação e armazenamento de valores temporários.
Otimização
Facilitam análises e transformações que seriam difíceis de realizar diretamente na AST ou no código fonte.
Tripla (three-address code – TAC em 3 colunas)
O código de três endereços ou tripla (TAC) é uma representação intermediária onde cada instrução tem a forma geral: resultado = operando1 operador operando2. Cada instrução realiza uma única operação com no máximo dois operandos.
Na representação em três colunas, cada linha contém um operador e dois operandos, com o resultado implícito sendo uma variável temporária ou identificada pelo número da linha.
# Tripla para: a = b + c * d
(*, c, d) # t1 = c * d
(+, b, t1) # t2 = b + t1
(=, t2, a) # a = t2
Quadrupla (quatro colunas)
A quadrupla é similar à tripla, mas inclui explicitamente o destino de cada operação, formando uma tabela de quatro colunas: operador, operando1, operando2 e resultado.
# Quadrupla para: a = b + c * d
(*, c, d, t1)     # t1 = c * d
(+, b, t1, t2)    # t2 = b + t1
(=, t2, -, a)     # a = t2
Essa representação torna mais explícito o fluxo de dados entre operações e facilita a implementação de otimizações como eliminação de subexpressões comuns.
Código de três endereços – estrutura e propósito

O código de três endereços é chamado assim porque cada instrução tem, no máximo, três endereços de memória referenciados (dois operandos e um resultado).
Características principais do código de três endereços:
  • Cada instrução realiza uma única operação básica
  • Usa variáveis temporárias para armazenar resultados intermediários
  • Torna explícita a ordem de avaliação das operações
  • Aproxima-se do código de máquina, mas mantém-se independente de arquitetura
O propósito é simplificar as expressões complexas em uma sequência de operações elementares, facilitando a geração de código e otimizações.
Exemplo de conversão: a = b + c * d
AST
Assign
├── Var: a
└── BinOp: +
    ├── Var: b
    └── BinOp: *
        ├── Var: c
        └── Var: d
Código de Três Endereços
t1 = c * d
t2 = b + t1
a = t2
Ou, em forma mais compacta:
t1 = c * d
t2 = b + t1
a = t2
Observe como a conversão preserva a ordem correta de avaliação ditada pela precedência dos operadores, primeiro calculando c * d e depois adicionando b.
Tripla vs. Quadrupla: vantagens e desvantagens
A escolha entre tripla e quadrupla depende das necessidades específicas do compilador e das otimizações planejadas.
Tabela comparativa: AST, Tripla, Quadrupla
Cada representação tem seus pontos fortes, e compiladores modernos frequentemente usam múltiplas representações em diferentes fases.
Aplicações típicas de cada IR em compiladores reais
1
AST
  • Análise semântica e verificação de tipos
  • Otimizações de alto nível como inlining de funções
  • Transpilação entre linguagens de alto nível
  • IDEs para refatoração e navegação de código
Exemplo: Clang usa AST para análise estática e refatoração
2
Tripla/TAC
  • Compiladores educacionais e simples
  • Otimizações locais de código
  • Compiladores para linguagens embarcadas
  • Geração de bytecode para máquinas virtuais
Exemplo: Pequenos compiladores de linguagens educacionais
3
Formas Avançadas (SSA, LLVM IR)
  • Compiladores de produção modernos
  • Otimizações globais complexas
  • Análise de fluxo de dados sofisticada
  • Geração de código otimizado para múltiplas plataformas
Exemplo: GCC e LLVM usam SSA e IRs próprias
Transformando AST em tripla/quadrupla
A transformação de AST para código de três endereços segue um padrão de visitação da árvore, geralmente em pós-ordem, gerando instruções para cada nó visitado. Durante esse processo:
  1. Expressões complexas são decompostas em operações elementares
  1. Variáveis temporárias são criadas para armazenar resultados intermediários
  1. A ordem de avaliação é preservada pela ordem das instruções geradas
  1. Estruturas de controle (if, while) são convertidas em saltos condicionais e incondicionais
O resultado é uma sequência linear de instruções simples que preservam a semântica do programa original.
Exemplo passo a passo: AST → TAC
Considerando a expressão: x = a + b * (c - d)
AST
Assign
├── Var: x
└── BinOp: +
    ├── Var: a
    └── BinOp: *
        ├── Var: b
        └── BinOp: -
            ├── Var: c
            └── Var: d
Geração de TAC (pós-ordem)
  1. Visitar c → nada a gerar, usar diretamente
  1. Visitar d → nada a gerar, usar diretamente
  1. Visitar c - d → gerar t1 = c - d
  1. Visitar b → nada a gerar, usar diretamente
  1. Visitar b * (c - d) → gerar t2 = b * t1
  1. Visitar a → nada a gerar, usar diretamente
  1. Visitar a + b * (c - d) → gerar t3 = a + t2
  1. Visitar x = ... → gerar x = t3
t1 = c - d
t2 = b * t1
t3 = a + t2
x = t3
Criando uma AST a partir de entrada textual
Para criar uma AST a partir de código-fonte, precisamos de um analisador léxico para gerar tokens e um analisador sintático para construir a árvore. Abaixo está uma implementação simplificada em Python:
class Lexer:
    def __init__(self, text):
        self.text = text
        self.pos = 0
        self.current_char = self.text[self.pos] if self.text else None
        
    def advance(self):
        self.pos += 1
        if self.pos >= len(self.text):
            self.current_char = None
        else:
            self.current_char = self.text[self.pos]
            
    def get_next_token(self):
        # Implementação simplificada do analisador léxico
        # ...

class Parser:
    def __init__(self, lexer):
        self.lexer = lexer
        self.current_token = self.lexer.get_next_token()
        
    def eat(self, token_type):
        if self.current_token.type == token_type:
            self.current_token = self.lexer.get_next_token()
        else:
            raise Exception('Erro de sintaxe')
            
    def expr(self):
        # Implementação do analisador sintático
        # ...
        
    def parse(self):
        return self.expr()
Esta estrutura básica pode ser expandida para reconhecer expressões mais complexas e gerar a AST correspondente.
Construção automatizada da AST com analisador sintático
O método mais comum para construir ASTs automaticamente é usando um analisador sintático descendente recursivo. Cada função de análise corresponde a uma regra gramatical e retorna um nó da AST:
def expr(self):
 # expr : term ((PLUS | MINUS) term)*
 node = self.term()
 
 while self.current_token.type in (PLUS, MINUS):
 token = self.current_token
 if token.type == PLUS:
 self.eat(PLUS)
 node = BinOp(left=node, op=token, right=self.term())
 elif token.type == MINUS:
 self.eat(MINUS)
 node = BinOp(left=node, op=token, right=self.term())
 
 return node

def term(self):
 # term : factor ((MUL | DIV) factor)*
 node = self.factor()
 
 while self.current_token.type in (MUL, DIV):
 token = self.current_token
 if token.type == MUL:
 self.eat(MUL)
 node = BinOp(left=node, op=token, right=self.factor())
 elif token.type == DIV:
 self.eat(DIV)
 node = BinOp(left=node, op=token, right=self.factor())
 
 return node
Geração de tripla a partir da AST
Para gerar código de três endereços a partir de uma AST, implementamos um visitante que percorre a árvore e emite instruções para cada nó:
class TACGenerator:
 def __init__(self):
 self.code = []
 self.temp_counter = 0
 
 def new_temp(self):
 temp = f"t{self.temp_counter}"
 self.temp_counter += 1
 return temp
 
 def visit_BinOp(self, node):
 # Visita recursivamente a subárvore esquerda
 left = self.visit(node.left)
 
 # Visita recursivamente a subárvore direita
 right = self.visit(node.right)
 
 # Gera uma nova variável temporária para o resultado
 temp = self.new_temp()
 
 # Emite a instrução de três endereços
 self.code.append((node.op.value, left, right, temp))
 
 # Retorna o nome da variável temporária
 return temp
 
 def visit_Num(self, node):
 # Para números literais, apenas retorna o valor
 return str(node.value)
 
 def visit_Var(self, node):
 # Para variáveis, apenas retorna o nome
 return node.value
 
 def visit(self, node):
 # Despacha para o método de visita apropriado
 method_name = f'visit_{type(node).__name__}'
 visitor = getattr(self, method_name, self.generic_visit)
 return visitor(node)
 
 def generic_visit(self, node):
 raise Exception(f'Nenhum método de visita para {type(node).__name__}')
Geração de quadrupla a partir da AST
A geração de quadruplas é muito similar à de triplas, apenas com uma representação diferente das instruções:
class QuadrupleGenerator(TACGenerator):
    def __init__(self):
        super().__init__()
        
    def visit_BinOp(self, node):
        # Visita recursivamente a subárvore esquerda
        left = self.visit(node.left)
        
        # Visita recursivamente a subárvore direita
        right = self.visit(node.right)
        
        # Gera uma nova variável temporária para o resultado
        temp = self.new_temp()
        
        # Emite a instrução quadrupla
        self.code.append((node.op.value, left, right, temp))
        
        # Retorna o nome da variável temporária
        return temp
        
    def visit_Assign(self, node):
        # Visita recursivamente o lado direito da atribuição
        right = self.visit(node.right)
        
        # Obtém o nome da variável alvo
        left = node.left.value
        
        # Emite a instrução de atribuição
        self.code.append(('=', right, None, left))
        
        # Não há valor de retorno para uma atribuição
        return None
A principal diferença entre tripla e quadrupla está na representação das instruções e como os resultados temporários são referenciados.
Exercício prático: gere a AST e as representações intermediárias

Exercício: Considere a expressão resultado = (x + y) * (z - 10) / 2. Desenhe a AST e gere manualmente o código de três endereços (tripla) correspondente.
Solução (AST):
Assign
├── Var: resultado
└── BinOp: /
    ├── BinOp: *
    │   ├── BinOp: +
    │   │   ├── Var: x
    │   │   └── Var: y
    │   └── BinOp: -
    │       ├── Var: z
    │       └── Num: 10
    └── Num: 2
Solução (Tripla):
t1 = x + y
t2 = z - 10
t3 = t1 * t2
t4 = t3 / 2
resultado = t4
Resumo e próxima aula
1
Representações Intermediárias
Vimos como as IRs servem de ponte entre o código-fonte e o código-máquina, facilitando otimizações e análises.
2
Árvores de Sintaxe Abstrata
Aprendemos como as ASTs capturam a estrutura essencial do programa, eliminando detalhes sintáticos desnecessários.
3
Triplas e Quadruplas
Exploramos representações lineares que aproximam o código de sua forma final, decomponho expressões complexas em operações elementares.
Na próxima aula, abordaremos a Geração de Código Intermediário, onde veremos como transformar sistematicamente ASTs em código intermediário e aplicar otimizações iniciais. Estudaremos padrões para estruturas de controle como if, while e for, além de como implementar chamadas de função.