Compiladores: fases, componentes e otimização

Compiladores: visão geral

Definição

Compilador: programa que lê um programa escrito em uma linguagem (fonte) e o traduz para outra linguagem (destino), reportando erros quando eles ocorrem.

Fluxo de tradução

Programa fonte > tradutor > programa intermediário > máquina virtual > Saída
Sistema de processamento de uma linguagem > processador > programa fonte modificado > Compilador > Assembler > código objeto > link/loader > executável

Programas auxiliares do processo de compilação

Existem ferramentas que apoiam o processo de compilação, entre as quais se destacam:

Reprocessadores

• Processam macros
• Includes
• Extensão de linguagens

Assemblers

Abstração da arquitetura da máquina de destino.

Carregadores (loaders)

Resolvem referências externas e fazem o linking (linkers / linkeditores).

Análise e Síntese

Análise: quebra o código-fonte em suas partes e cria uma representação intermediária do programa. Verifica erros e constrói a tabela de símbolos.

Síntese: constrói o programa-destino a partir da representação intermediária.

Fases de um compilador

• Stream de caracteres
• Analisador léxico
• Stream de tokens
• Analisador sintático
• Árvore sintática
• Analisador semântico
• Árvore sintática (anotada)
• Gerador de código intermediário
• Representação intermediária
• Otimizador de código
• Representação intermediária otimizada
• Gerador de código
• Código de máquina

Front-end (Análise)

A análise corresponde ao front end do compilador (até a geração do código intermediário) e inclui:

• Analisador léxico
• Analisador sintático
• Analisador semântico

Back-end (Síntese)

A síntese corresponde ao back end do compilador e inclui:

• Geradores de código intermediário
• Otimizador de código
• Gerador de código

Análise léxica

A análise léxica converte uma sequência de caracteres em tokens.

Exemplo: p = i + R * 60

<= >  <+>  <*>
Ou
(entradas possíveis e tokens correspondentes)

Análise sintática

A análise sintática agrupa tokens em uma estrutura hierárquica com significado (árvore sintática).

Análise semântica

A análise semântica verifica se os componentes de um programa se encaixam de forma a ter um significado adequado.

Resumo: análise

Análise: quebra o código-fonte em suas partes e cria uma representação intermediária do programa. Verifica erros e constrói a tabela de símbolos.

Resumo: síntese

Síntese: constrói o programa-destino a partir da representação intermediária.

Análise do programa-fonte (detalhes)

• Análise léxica – lê a sequência de caracteres e a organiza como tokens (sequências de caracteres com algum significado).
• Análise sintática – agrupa caracteres ou tokens em uma estrutura hierárquica com significado.
• Análise semântica – verifica se os componentes de um programa têm significado adequado quando combinados.

Código intermediário

• Idealmente deve ser fácil de produzir e também de traduzir para a linguagem-destino.
• Na prática, costuma-se gerar código para uma máquina abstrata.
• Por exemplo, three-address code: usa três operandos por instrução, cada um como se fosse um registrador.

Otimização de código

• Realiza transformações no código visando melhorar sua performance em tempo de execução, uso de memória, tamanho do executável etc.

Geração de código

• Realiza a alocação de registradores (quando necessária) e a tradução do código intermediário para a linguagem-destino.

Classificações por paradigma

• Imperativo – "como": conceito de estado e comandos que mudam o estado (ex.: C, C++, C#, Java).
• Declarativo – "o quê": ex.: Haskell, Prolog.

Tempo de ligação

• Estático: em tempo de compilação.
• Dinâmico: em tempo de execução.

Árvore sintática

Representação hierárquica (AST) construída pelo analisador sintático e anotada pelo analisador semântico.

Objetivos dos compiladores

• Gerar código corretamente.
• Ser capaz de tratar programas de qualquer tamanho.
• A velocidade da compilação não é a característica principal em muitos casos.
• O tamanho do compilador já não é mais um problema relevante.
• Usabilidade (user-friendliness): medida pela qualidade das mensagens de erro.
• A importância da velocidade e do tamanho do código gerado depende do propósito do compilador; em muitos casos, a velocidade do código vem em primeiro lugar.

Modelo de compilação

Dois grandes passos:

• Análise: interpreta o programa-fonte e cria uma representação intermediária do mesmo.
• Síntese: a partir da representação intermediária, produz o programa-alvo.

Por que estudar compilação?

Várias aplicações e necessidades atuais:

• Validação de arquiteturas diferenciadas de computadores.
• Aceitação de novas linguagens de programação.
• Otimização de código para celulares, sistemas embarcados e novas arquiteturas.
• Teste de falhas/erros em software.
• Busca por brechas/falhas de segurança em sistemas.
• Efetividade do paralelismo (ambientes multicore).
• Melhor uso de memória (registradores, caches, RAM).
• Tradução entre sistemas diferentes; síntese de hardware (da especificação para o modelo).
• Interpretação de linguagens especiais: SQL, por exemplo.
• Etc.

24,>,>,>,>,>,>,>*>,>+>,>=>,>