INÍCIO
Livros do Prof.
Aula 15: Apresentação e Revisão Final
Bem-vindos à nossa aula final de compiladores! Hoje teremos apresentações dos projetos desenvolvidos, uma revisão completa dos conteúdos abordados durante o semestre e a avaliação final da disciplina.
Programação da Aula Final
1
Apresentações dos Grupos
Cada grupo terá 15 minutos para apresentar sua linguagem de programação e demonstrar a compilação de um programa simples.
2
Revisão dos Conteúdos
Reforçaremos os principais conceitos abordados durante o semestre, desde análise léxica até otimização de código.
3
Avaliação Final
Realizaremos uma avaliação prática ou teórica para verificar o aprendizado e encerraremos com feedback da turma.
Apresentações dos Grupos: Orientações Gerais
Cada grupo terá 15 minutos para apresentar seu projeto de compilador. A apresentação deve incluir:
  • Nome e escopo da linguagem desenvolvida
  • Principais características e estrutura do compilador
  • Demonstração prática de um programa simples sendo compilado
  • Desafios enfrentados e soluções encontradas
Após cada apresentação, teremos 5 minutos para perguntas e feedback dos colegas e do professor.
Grupo 1: Nome da Linguagem e Escopo
1
Apresentação da Linguagem
  • Nome da linguagem: [Nome]
  • Paradigma: [Imperativo/Funcional/Lógico]
  • Aplicações pretendidas: [Educacional/Específica/Geral]
  • Inspirações e influências
2
Estrutura do Compilador
  • Fases implementadas
  • Ferramentas utilizadas (Flex, Bison, etc.)
  • Desafios específicos
  • Funcionalidades destacadas
O Grupo 1 desenvolveu uma linguagem com foco em [objetivo principal], implementando um compilador completo capaz de transformar código-fonte em código executável através de [abordagem técnica escolhida].
Grupo 1: Demonstração
Compilação de Programa Simples
Nesta demonstração, o Grupo 1 mostrará:
  • Código-fonte de exemplo
  • Tokens gerados na análise léxica
  • Árvore sintática abstrata (AST)
  • Código intermediário gerado
  • Código final e execução
// Exemplo de código na linguagem
function main() {
 var x = 10;
 var y = 20;
 print(x + y);
}
Grupo 2: Nome da Linguagem e Escopo
1
Apresentação da Linguagem
  • Nome da linguagem: [Nome]
  • Paradigma: [Imperativo/Funcional/Lógico]
  • Aplicações pretendidas: [Educacional/Específica/Geral]
  • Inspirações e influências
2
Estrutura do Compilador
  • Fases implementadas
  • Ferramentas utilizadas (Flex, Bison, etc.)
  • Desafios específicos
  • Funcionalidades destacadas
O Grupo 2 desenvolveu uma linguagem voltada para [objetivo principal], com ênfase em [características específicas]. O compilador foi implementado utilizando [tecnologias principais] e possui recursos como [recursos destacados].
Grupo 2: Demonstração
Compilação de Programa Simples
Nesta demonstração, o Grupo 2 mostrará:
  • Código-fonte de exemplo
  • Processo de análise léxica e sintática
  • Representação intermediária
  • Otimizações implementadas
  • Código final e execução
/* Exemplo de código na linguagem */
programa {
 inteiro a, b;
 a = 15;
 b = 25;
 imprimir(a + b);
}
Grupo 3: Nome da Linguagem e Escopo
1
Apresentação da Linguagem
  • Nome da linguagem: [Nome]
  • Paradigma: [Imperativo/Funcional/Lógico]
  • Aplicações pretendidas: [Educacional/Específica/Geral]
  • Inspirações e influências
2
Estrutura do Compilador
  • Fases implementadas
  • Ferramentas utilizadas (Flex, Bison, etc.)
  • Desafios específicos
  • Funcionalidades destacadas
O Grupo 3 criou uma linguagem inovadora focada em [objetivo principal], implementando recursos como [características específicas]. O compilador foi desenvolvido com [abordagem técnica] e se destaca por [diferenciais do projeto].
Grupo 3: Demonstração
Compilação de Programa Simples
Nesta demonstração, o Grupo 3 mostrará:
  • Código-fonte de exemplo
  • Análise léxica e geração de tokens
  • Construção da AST
  • Verificação semântica
  • Geração e execução do código
# Exemplo de código na linguagem
def calcular_soma(x, y):
 resultado = x + y
 retornar resultado

principal():
 mostrar(calcular_soma(10, 20))
Grupo 4: Nome da Linguagem e Escopo
1
Apresentação da Linguagem
  • Nome da linguagem: [Nome]
  • Paradigma: [Imperativo/Funcional/Lógico]
  • Aplicações pretendidas: [Educacional/Específica/Geral]
  • Inspirações e influências
2
Estrutura do Compilador
  • Fases implementadas
  • Ferramentas utilizadas (Flex, Bison, etc.)
  • Desafios específicos
  • Funcionalidades destacadas
O Grupo 4 desenvolveu uma linguagem com foco em [objetivo principal], implementando recursos inovadores como [características específicas]. O compilador utiliza [tecnologias] e resolve problemas como [desafios superados].
Grupo 4: Demonstração
Compilação de Programa Simples
Nesta demonstração, o Grupo 4 mostrará:
  • Código-fonte de exemplo
  • Processo de compilação passo a passo
  • Estruturas de dados utilizadas
  • Otimizações implementadas
  • Execução do programa final
// Exemplo de código na linguagem
inicio
 variavel num1 = 30;
 variavel num2 = 40;
 escrever(num1 * num2);
fim
Grupo 5: Nome da Linguagem e Escopo
1
Apresentação da Linguagem
  • Nome da linguagem: [Nome]
  • Paradigma: [Imperativo/Funcional/Lógico]
  • Aplicações pretendidas: [Educacional/Específica/Geral]
  • Inspirações e influências
2
Estrutura do Compilador
  • Fases implementadas
  • Ferramentas utilizadas (Flex, Bison, etc.)
  • Desafios específicos
  • Funcionalidades destacadas
O Grupo 5 criou uma linguagem especializada em [objetivo principal], com características como [características específicas]. O compilador foi desenvolvido utilizando [abordagem técnica] e apresenta soluções inovadoras para [problemas resolvidos].
Grupo 5: Demonstração
Compilação de Programa Simples
Nesta demonstração, o Grupo 5 mostrará:
  • Código-fonte de exemplo
  • Análise léxica e sintática
  • Verificação semântica
  • Geração de código intermediário
  • Código final e execução
// Exemplo de código na linguagem
classe Exemplo {
 funcao principal() {
 var a = 5;
 var b = 10;
 retornar a + b;
 }
}
Feedback dos Projetos: Pontos Fortes Observados
Inovação
Vários grupos implementaram recursos inovadores em suas linguagens, como sistemas de tipos avançados, inferência de tipos e abstrações de alto nível que simplificam a expressão de algoritmos complexos.
Organização do Código
Destaque para a modularidade do código-fonte dos compiladores, com separação clara entre as fases de compilação e uso adequado de padrões de projeto para facilitar manutenção e evolução.
Documentação
Documentação detalhada da linguagem e do compilador, incluindo gramáticas formais bem definidas, especificações claras da semântica e guias de uso que facilitam o entendimento e a utilização.
Os projetos demonstraram excelente compreensão dos conceitos teóricos aplicados à prática da construção de compiladores, com soluções criativas para desafios técnicos.
Erros Comuns Entre os Grupos
Dificuldades Técnicas
  • Tratamento inadequado de erros sintáticos
  • Verificação semântica incompleta
  • Problemas com escopo de variáveis
  • Otimizações que alteram a semântica do programa
  • Limitações na geração de código final
Aspectos Metodológicos
  • Definição imprecisa da gramática
  • Falta de testes sistemáticos
  • Documentação insuficiente
  • Escopo muito ambicioso para o tempo disponível
  • Integração problemática entre os módulos
Estes erros são oportunidades de aprendizado e aprimoramento para futuras implementações de compiladores, tanto em contexto acadêmico quanto profissional.
Aprendizados Compartilhados
Importância da Especificação Formal
Os grupos que investiram tempo em definir formalmente a gramática e a semântica de suas linguagens enfrentaram menos problemas durante a implementação e conseguiram detectar inconsistências antecipadamente.
Abordagem Incremental
A estratégia de implementar o compilador em incrementos funcionais, testando cada componente isoladamente antes de integrá-lo, mostrou-se muito mais eficaz do que tentar implementar todas as fases simultaneamente.
Valor dos Testes Automatizados
Os compiladores que incluíram suítes de testes automatizados para cada fase do processo de compilação conseguiram identificar regressões rapidamente e garantir a robustez do sistema como um todo.
Sugestões de Melhoria para Próximas Turmas
Aspectos Técnicos
  • Iniciar com uma linguagem mais simples e expandir gradualmente
  • Implementar suites de testes desde o início
  • Definir claramente interfaces entre os módulos
  • Adotar ferramentas de geração automática quando apropriado
  • Focar em uma fase do compilador por vez
Aspectos Metodológicos
  • Realizar mais entregas parciais durante o semestre
  • Promover sessões de revisão de código entre grupos
  • Criar documentação detalhada desde o início
  • Definir melhor a divisão de tarefas entre membros
  • Reservar tempo adequado para integração e testes
Estas sugestões refletem os desafios enfrentados pelos grupos e podem contribuir significativamente para o sucesso dos projetos em futuras edições da disciplina.
Vídeo do Melhor Projeto
Destaques do Projeto
O projeto do Grupo [X] se destacou pelos seguintes aspectos:
  • Implementação completa de todas as fases do compilador
  • Linguagem com sintaxe clara e recursos avançados
  • Excelente tratamento de erros com mensagens informativas
  • Otimizações eficientes no código gerado
  • Documentação detalhada e testes abrangentes
O vídeo demonstra a execução do compilador, desde a análise léxica até a geração de código executável, destacando a qualidade da implementação e a originalidade da solução.
Ferramentas Mais Utilizadas nos Projetos
Flex e Bison
Geradores de analisadores léxicos e sintáticos que automatizam a criação de scanners e parsers a partir de especificações formais. Utilizados por 80% dos grupos para implementar as fases iniciais da compilação.
LLVM
Infraestrutura de compilação modular que fornece um conjunto de ferramentas para geração e otimização de código. Adotada por 40% dos grupos para a fase de geração de código final.
Git e GitHub
Sistemas de controle de versão e plataformas de colaboração que facilitaram o desenvolvimento paralelo e a integração do trabalho entre os membros das equipes.
Exemplos de Código Bem Estruturado
Análise Léxica com Flex
%{
#include "tokens.h"
%}

%%
[ \t\n]+    { /* ignora espaços */ }
"if"        { return IF; }
"else"      { return ELSE; }
"while"     { return WHILE; }
[0-9]+      { return NUM; }
[a-zA-Z]+   { return ID; }
"+"         { return PLUS; }
"-"         { return MINUS; }
%%
Análise Sintática com Bison
%{
#include "ast.h"
%}

%token IF ELSE WHILE NUM ID PLUS MINUS

%%
program : statement
        ;
statement : IF '(' expr ')' statement
          | WHILE '(' expr ')' statement
          | expr ';'
          ;
expr : expr PLUS term
     | expr MINUS term
     | term
     ;
term : NUM
     | ID
     ;
%%
Estes exemplos demonstram clareza, organização e aderência às boas práticas de programação, facilitando a manutenção e a evolução do código.
Revisão Geral: Fases do Compilador
Análise Léxica
Transforma o código-fonte em tokens, identificando lexemas como identificadores, palavras-chave, operadores e constantes.
Análise Sintática
Verifica se a sequência de tokens segue as regras gramaticais da linguagem, construindo a árvore sintática abstrata (AST).
Análise Semântica
Verifica a coerência semântica do programa, como tipos, escopos e outras regras não expressáveis pela gramática formal.
Geração de Código
Transforma a representação intermediária em código executável na plataforma alvo, otimizando quando possível.
Análise Léxica: Tokens e Autômatos
A análise léxica é a primeira fase do processo de compilação, responsável por dividir o código-fonte em tokens significativos:
  • Tokens: identificadores, palavras-chave, operadores, delimitadores e constantes
  • Expressões regulares: definem os padrões que os tokens podem assumir
  • Autômatos finitos: implementam o reconhecimento de tokens eficientemente
  • Tabela de símbolos: armazena informações sobre identificadores
O analisador léxico percorre o código-fonte caracter por caracter, identificando tokens através de autômatos finitos determinísticos, ignorando espaços em branco e comentários conforme necessário.
Análise Sintática: Gramáticas e AST
A análise sintática verifica se a sequência de tokens forma estruturas válidas segundo a gramática da linguagem:
  • Gramáticas livres de contexto: definem a sintaxe da linguagem
  • Algoritmos de parsing: LL(k), LR(k), LALR, descendente recursivo
  • Árvore Sintática Abstrata (AST): representa a estrutura hierárquica do programa
  • Tratamento de erros: recuperação e mensagens informativas
A AST é uma representação estruturada do programa onde cada nó representa uma construção sintática (expressão, declaração, bloco), omitindo detalhes sintáticos como parênteses e pontuação.
Análise Semântica: Verificação de Tipos e Escopo
Sistema de Tipos
Verifica a compatibilidade de tipos em operações, atribuições e passagem de parâmetros. Implementa conversões implícitas ou detecta erros de tipo.
Análise de Escopo
Verifica a visibilidade e o tempo de vida das variáveis e funções, garantindo que cada identificador seja usado apenas em seu escopo válido.
Verificação Semântica
Detecta erros como uso de variáveis não declaradas, redeclarações, funções sem retorno, acessos inválidos e outros erros que não podem ser capturados pela gramática.
A análise semântica enriquece a AST com informações de tipo e escopo, preparando-a para a geração de código intermediário e detectando erros semânticos antes da execução.
Representações Intermediárias
Código de Três Endereços
Forma de representação intermediária onde cada instrução tem no máximo três operandos (dois de entrada e um de saída), facilitando a tradução para código de máquina.
t1 = a + b
t2 = t1 * c
x = t2
Tuplas e Quádruplas
Representações tabulares das operações, onde cada linha contém um operador e seus operandos. Quádruplas incluem explicitamente o destino do resultado.
(+, a, b, t1)
(*, t1, c, t2)
(=, t2, -, x)
Representação em Árvore
Mantém a estrutura hierárquica do programa, facilitando certas otimizações como eliminação de subexpressões comuns.
Geração de Código: TAC → Assembly
A geração de código traduz a representação intermediária para código de máquina ou assembly, considerando a arquitetura alvo:
  • Mapeamento de variáveis para registradores ou memória
  • Tradução de operações para instruções da arquitetura
  • Geração de código para estruturas de controle
  • Chamadas de função e convenções de chamada
  • Gerenciamento de memória e pilha
// TAC
t1 = a + b
t2 = t1 * 4
x = t2

// Assembly (x86)
MOV EAX, [a]
ADD EAX, [b]
MOV EBX, 4
MUL EBX
MOV [x], EAX
Alocação de Registradores
1
Análise de Tempo de Vida
Determina o intervalo em que cada variável está "viva" (entre sua definição e último uso), identificando quais variáveis podem compartilhar registradores.
2
Construção do Grafo de Interferência
Cria um grafo onde os nós são variáveis e as arestas indicam que duas variáveis estão vivas simultaneamente e não podem usar o mesmo registrador.
3
Coloração do Grafo
Atribui "cores" (registradores) aos nós de forma que nós adjacentes tenham cores diferentes, minimizando o número de registradores necessários.
4
Spillage
Quando não há registradores suficientes, algumas variáveis são armazenadas na memória (stack) e carregadas quando necessário.
Otimizações de Código
Constant Folding
Calcula expressões constantes em tempo de compilação. Por exemplo, transforma "x = 5 + 3 * 2" em "x = 11", reduzindo operações em tempo de execução.
Dead Code Elimination
Remove código que nunca é executado ou cujos resultados nunca são utilizados, reduzindo o tamanho do programa e melhorando o desempenho.
Loop Optimization
Técnicas como loop unrolling, invariant code motion e strength reduction melhoram o desempenho de loops, que frequentemente são os gargalos de performance.
As otimizações podem ser aplicadas em diferentes níveis: na representação intermediária (independentes da máquina) ou no código final (específicas da arquitetura).
Grafos: Fluxo de Controle e Dependência
Grafo de Fluxo de Controle (CFG)
Representa todos os caminhos que podem ser seguidos durante a execução do programa. Cada nó é um bloco básico (sequência de instruções sem desvios) e as arestas representam possíveis transições.
Utilidades:
  • Análise de fluxo de dados
  • Detecção de código morto
  • Otimizações de laços
Grafo de Dependência de Dados (DDG)
Mostra as dependências entre operações, onde um nó depende do resultado de outro. Essencial para:
  • Análise de paralelismo
  • Reordenação de instruções
  • Detecção de race conditions
Autômatos e Gramáticas Formais
1
2
3
4
1
Autômatos Finitos
Reconhecem linguagens regulares (Tipo 3)
2
Autômatos de Pilha
Reconhecem linguagens livres de contexto (Tipo 2)
3
Autômatos Limitados Linearmente
Reconhecem linguagens sensíveis ao contexto (Tipo 1)
4
Máquinas de Turing
Reconhecem linguagens recursivamente enumeráveis (Tipo 0)
A hierarquia de Chomsky classifica linguagens formais em quatro tipos, com poder expressivo crescente. Os compiladores de linguagens de programação tipicamente trabalham com gramáticas livres de contexto (Tipo 2), com algumas restrições adicionais verificadas na fase semântica.