🔧 Otimizações em Interpretador da Linguagem Lox

👥 Integrantes

Nome	Matrícula	Turma
David William Lemos Ferreira	232001649	18h
Yasmin Dayrell Albuquerque	232014226	16h

Orientador: Fabio M. Mendes

📌 Introdução

Linguagem Lox

Este é o código fonte de um interpretetador da linguagem de programação Lox desenvolvido durante o curso de Compiladores 1 da Universidade de Brasilia.

Ele estende um interpretador já desenvolvido ao longo do curso com otimizações de código-fonte baseadas em análise da AST (Abstract Syntax Tree).

Otimizações

As otimzações realizadas no interpretador incluem:

• 🔁 Constant Propagation: substituição de variáveis constantes diretamente por seus valores.
• 🔢 Constant Folding: avaliação de expressões constantes em tempo de compilação.
• 🗑️ Dead Code Elimination:
  • Unused Variables: remoção de variáveis nunca utilizadas.
  • Unreachable Code: ainda não implementado.

Outras otimizações planejadas (não implementadas):

• ⏳ Loop Unrolling
• ⏳ Inline Expansion

As otimizações são aplicadas diretamente sobre a AST utilizando classes específicas localizadas no arquivo lox/optimizations.py.

Exemplo de uso

from optimizations import ConstantPropagation

ast = ...  # AST original

ConstantPropagation().propagate(ast)

print(ast.pretty())  # AST otimizada

🛠️ Instalação

O projeto utiliza o gerenciador uv, então o primeiro passo é ter ele instalado.

1. Clonar o repositório:

git clone https://github.com/fcte-compiladores/trabalho-final-trabalho_final_loxotimizacoes.git

cd trabalho-final-trabalho_final_loxotimizacoes

2. Instalar os pacotes

Inicie o ambiente uv e intale os pacotes:

uv venv
uv run

3. Rodar os testes

O sistema de otimizações possui uma CLI, agora basta executar:

uv run optimization

E ele criará um arquivo tests/results.txt com o resultado dos testes, para visualizar execute:

less -R tests/results.txt
# ou
cat tests/results.txt

⚠️ Importante: O arquivo results.txt usa caracteres ANSI (cores), recomenda-se a leitura com programas adequados

Veja mais comandos da CLI com uv run optimization --help

---

Também é possível rodar um arquivo lox otimizado com a CLI padrão:

uv run lox exemplos/optimization/propagation/3.lox -o
# ou
uv run lox --help

💡 Exemplos

A pasta exemplos/optimization contém os exemplos utilizados para testes das otimizações. Subpastas:

• propagation/: testes de propagação de constantes.
• unsed_vars/: testes de variáveis não utilizadas.
• all/: testes com múltiplas otimizações aplicadas.

Cada exemplo serve como benchmark incremental, com dificuldades crescentes.

📁 Estrutura do Código

.
├── exemplos
│   └── optimization
│       ├── all
│       ├── propagation
│       └── unsed_vars
├── lox
│   ├── __init__.py
│   ├── __main__.py
│   ├── ast.py
│   ├── cli.py
│   ├── ctx.py
│   ├── errors.py
│   ├── grammar.lark
│   ├── node.py
│   ├── optimizations.py
│   ├── parser.py
│   ├── runtime.py
│   ├── testing.py
│   └── transformer.py
├── pyproject.toml
├── pytest.ini
├── README.md
├── tests
│   ├── configs.py
│   ├── optimization.py
│   └── results.txt
└── uv.lock

📚 Referências

• IBM - Otimization Techniques - Usado como exploratório para descobrir tecnicas de otimizções
• Geek for Geeks - Principal base para aplicação das otimizações
• Medium - Guannan Shen - Explica algumas tecnicas de otimização que o GCC utiliza
• Crafting Interpreters – Bob Nystrom: principal base teórica e prática para o interpretador da linguagem Lox.
• Repositório da disciplina: usado como base do interpretador.
• Implementações próprias: as otimizações foram inteiramente desenvolvidas pela equipe como extensão do interpretador.

🐞 Bugs / Limitações / Problemas Conhecidos

• ❌ Otimizações não incluem ainda análise de código inatingível
• ❌ Otimizações NÃO seguras podem ocorrer devido a falta de heurística no otimizador
• 🔜 Outras otimizações (unroll, inline) ainda estão em planejamento
• 🛠️ Melhorias futuras podem incluir mais padrões da linguagem e heurísticas para otimizações