Centro de Estudos, Desenvolvimento e Inovação em Software | Universidade de Brasília

Otimização de código

FGA0003 - Compiladores 1 | Semana 9 | Aula prática

Prof. Sergio Antônio Andrade de Freitas
Compiladores 1 - Engenharia de Software · 2025/2
símbolo CEDIS logo UnB
símbolo CEDISCEDIS
2/21

Resultado esperado da prática

  • Compilar o protótipo com make.
  • Executar a suíte de testes com make test.
  • Entender onde a AST é construída pelo parser.
  • Acompanhar a função optimize() em uma travessia recursiva.
  • Adicionar novos casos de teste e propor melhorias no código.
símbolo CEDISCEDIS
3/21

Acesso ao código da Semana 9

O material da prática está no repositório público da disciplina.

  • Repositório: https://github.com/sergioaafreitas/COMP1
  • Diretório: semana 09
  • Linguagem: C
  • Ferramentas: Flex, Bison, GCC e Make
Organização dos arquivos da Semana 9
Use git pull se o repositório já existir localmente.
símbolo CEDISCEDIS
4/21

Preparação no terminal

1

Clonar ou atualizar

git clone https://github.com/sergioaafreitas/COMP1.git # ou, se já existe: git pull

2

Entrar na prática

cd "COMP1/semana 09"

3

Conferir ferramentas

flex --version bison --version gcc --version make --version

símbolo CEDISCEDIS
5/21
Hierarquia de arquivos do protótipo
O objetivo é enxergar responsabilidades, não apenas executar comandos.

Estrutura do projeto

A prática separa especificação léxica, gramática, AST, testes e automação de build.

  • src/lexer.l reconhece números, identificadores e operadores.
  • src/parser.y constrói a AST e chama optimize().
  • src/ast.h e src/ast.c definem e manipulam os nós.
  • tests/*.in contém entradas para regressão.
  • Makefile automatiza geração, compilação e testes.
símbolo CEDISCEDIS
6/21

O que o Makefile automatiza

Variáveis principais

  • CC = gcc
  • FLEX = flex
  • BISON = bison
  • CFLAGS = -Wall -Isrc
  • TARGET = optimize

Alvos principais

  • make: gera o executável.
  • make test: executa tests/*.in.
  • make clean: remove arquivos gerados.
  • all: dependência padrão.
símbolo CEDISCEDIS
7/21

Primeira compilação

Execute no diretório semana 09:

  • make clean
  • make
  • ./optimize
  • Digite uma expressão simples ou use echo para enviar entrada.
símbolo CEDISCEDIS
8/21

Primeiras execuções

Expressão constante

echo "2+3*4" | ./optimize Saída esperada: 14

Expressão parcial

echo "2+3+x*4" | ./optimize Saída esperada: (5 + (x * 4))

Parênteses

echo "(1+2)*(3+4)" | ./optimize Saída esperada: 21

símbolo CEDISCEDIS
9/21

Fluxo completo do protótipo

A entrada passa pelo scanner, pelo parser, vira AST e é simplificada por optimize().

  • Flex produz tokens.
  • Bison aplica a gramática e cria nós.
  • A AST representa números, variáveis e operações.
  • optimize() reduz operações com dois operandos constantes.
  • printNode() mostra a árvore resultante.
Fluxo do protótipo da prática
A otimização é executada depois do parsing e antes da impressão.
símbolo CEDISCEDIS
10/21

Leitura orientada do lexer e do parser

lexer.l

  • Reconhece NUM.
  • Reconhece ID.
  • Retorna PLUS, MINUS, TIMES e DIVIDE.
  • Ignora espaços e quebras de linha.
  • Informa caractere inválido.

parser.y

  • Define union semântica.
  • Usa expr, term e factor.
  • Constrói nós da AST.
  • Chama optimize(root).
  • Imprime a AST resultante.
símbolo CEDISCEDIS
11/21
Antes e depois de constant folding
A transformação muda a árvore, não apenas a impressão final.

Estrutura dos nós da AST

O nó diferencia três categorias: número, variável e operador.

  • NODE_NUM armazena um valor inteiro.
  • NODE_VAR armazena o nome do identificador.
  • NODE_OP armazena operador e dois filhos.
  • A otimização altera nós operadores para nós numéricos quando possível.
símbolo CEDISCEDIS
12/21

Como optimize() percorre a árvore

A função visita os filhos antes de tentar simplificar o nó atual.

  • Primeiro otimiza left.
  • Depois otimiza right.
  • Só então testa se ambos são números.
  • Se forem constantes, calcula o resultado.
  • O nó operador vira NODE_NUM.
Travessia recursiva em pós-ordem para folding
A ordem de baixo para cima é essencial para simplificações encadeadas.
símbolo CEDISCEDIS
13/21

Rastreamento de 2+3*4

Passo 1

A gramática reconhece 3*4 como term.

Passo 2

optimize() reduz 3*4 para 12.

Passo 3

A raiz passa a ser 2+12.

Passo 4

2+12 é reduzido para 14.

símbolo CEDISCEDIS
14/21
Exemplo de simplificação em ramos da AST
Otimizações locais podem produzir novas oportunidades de otimização.

Rastreamento de (1+2)*(3+4)

Este caso mostra folding em dois ramos e depois na raiz.

  • 1+2 vira 3.
  • 3+4 vira 7.
  • 3*7 vira 21.
  • O resultado final é um único nó numérico.
símbolo CEDISCEDIS
15/21

Expressões parcialmente otimizáveis

Entrada

2 + 3 + x * 4

  • 2+3 pode ser reduzido.
  • x*4 não pode ser reduzido sem valor de x.
  • A árvore resultante ainda contém uma operação.

Saída esperada

(5 + (x * 4))

  • A parte constante é simplificada.
  • A parte dependente de variável é preservada.
  • A semântica continua equivalente.
seção

Problemas didáticos do protótipo

O protótipo funciona, mas também serve para discutir qualidade de implementação.

símbolo CEDISCEDIS
17/21

Correções e melhorias guiadas

Separar responsabilidades

Mover optimize() de parser.y para ast.c.

Divisão por zero

Não transformar 10/0 em 0; preservar erro ou manter o nó.

Memória de ID

Liberar a string recebida do Flex após criar o nó.

Testes novos

Adicionar entradas que cubram constantes, variáveis e erros.

símbolo CEDISCEDIS
18/21

Novos testes para adicionar

1

Criar arquivos

tests/test4.in tests/test5.in tests/test6.in tests/test7.in

2

Sugerir entradas

x+2*3 10/(2+3) (8-3)*(2+2) 10/0

3

Definir esperado

Antes de executar, escreva a saída esperada no README.

4

Rodar regressão

make clean make test

símbolo CEDISCEDIS
19/21

Integração ao projeto da equipe

  • Executar otimizações depois da análise semântica.
  • Preservar uma forma de imprimir a AST antes e depois.
  • Criar testes que mostrem a transformação esperada.
  • Documentar quais regras de otimização foram implementadas.
  • Fazer commit e push ao final da aula.
símbolo CEDISCEDIS
20/21

Referências e material de apoio

  1. Freitas, S. A. A. de. (2025). COMP1: Repositório da disciplina FGA0003 - Compiladores 1. GitHub. https://github.com/sergioaafreitas/COMP1
  2. Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Pearson.
  3. Appel, A. W. (2002). Modern Compiler Implementation in Java (2nd ed.). Cambridge University Press.
  4. Cooper, K. D., & Torczon, L. (2012). Engineering a Compiler (2nd ed.). Morgan Kaufmann.
símbolo CEDISCEDIS
21/21

Encerramento

Ao final, o protótipo deve compilar, testar e demonstrar folding de constantes de forma documentada.

→ avançar · ← voltar · deslize (touch) · n notas · f tela cheia · p imprimir