Compiladores
Profº. Johni Douglas Marangon
cpl.johnidouglas.com.br
• A escrita de compiladores abrange conceitos de linguagens de
programação, arquitetura de máquina, teoria de linguagens e
engenharia de software.
• O objetivo dessa aula é apresentar uma introdução ao processo de
compilação dando uma visão de alto nível da estrutura de um
compilador.
Linguagens de programação
• A linguagem é o meio de comunicação entre pessoas e é chamada de
língua ou idioma.
• Em programação a linguagem é o meio de comunicação entre o
pensamento humano e as ações de um computador.
• Todo o software é escrito em uma linguagem e deve ser traduzido
para um formado em que o computador possa ser executado.
• Os programas executados no computador são sequencias de zeros e
uns e representam valores como inteiros, strings e instruções.
• Exemplo de execução de uma soma em linguagem de máquina.
• Uma linguagem de programação é de alto nível se sua representação
esta próxima do domínio da aplicação e do problema a ser resolvido.
• As linguagem de baixo nível é uma linguagem própria do computador
e possuem uma gramatica composta por zeros e uns.
• O processo de tradução de uma linguagem de alto nível para uma
linguagem de abaixo nível é feita normalmente por software
conhecidos como compiladores ou interpretadores.
• As linguagem são classificadas em 5 gerações.
•
•
•
•
•
Primeira geração: linguagem de máquina – baixo nível.
Segunda geração: Linguagem simbólica ou assembly – baixo nível.
Terceira geração: Linguagem orientadas a usuários – alto nível.
Quarta geração: Linguagem orientada a aplicação – alto nível.
Quinta geração: Linguagem de conhecimento – alto nível.
• As primeiras aplicações eram escrita em linguagem de máquina logo
depois surgiram as linguagem simbólicas ou de montagem que
diminuíram o problema e substituíram as instruções binarias pro
mnemônicos.
• O montador converte o código assembly para linguagem de maquina.
• As linguagem de terceira geração são voltadas a solução de
problemas específicos – aplicações comerciais e cientificas – e se
caracterizam por serem por serem declarativas, imperativas,
procedimentais e logicas.
• Seus programas descreverem como o problema deve ser resolvido.
• A terceira geração de linguagem foi projetada para serem utilizada
por engenheiro de software ou simplesmente programadores.
• As linguagem de quarta geração surgiram para serem utilizar pro
usuários finais sendo de fácil programação permitindo que os
próprios usuário resolvam os seus problemas. Excel , Acesse, SQL.
• As linguagem de quinta geração são voltadas para inteligência
artificial. Como exemplo temos o PROLOG.
Tradutores
• São sistemas que aceitam como entrada um programa escrito em
uma linguagem e produzem como resultado um programa
equivalente em outra forma. São classificados em:
• Montadores: ou assemblers, mapeiam instruções simbólicas para instruções
de máquina.
• Marco-assemblers: funcionam como os montadores mas tem a possibilidade
de criar “macros”.
• Compiladores: Mapeiam programas escritos em linguagem de alto nível para
linguagem simbolica ou de máquina.
• Pre-compiladores: pré-proessadores ou filtros são programas que convertem
uma linguagem de alto nível estendida da original para outra linguagem de
alto nível.
• Interpretadores: Como entrada possuem uma linguagem intermediaria ou a
própria linguagem fonte e um programa compilador produz o efeito de
execução, interpretadores não geram código objeto.
O tempo de compilação é o intervalo de tempo de conversão de um programa fonte para um
programa objeto. Já o programa objeto é executado no intervalo de tempo chamado tempo de
execução.
Compiladores cruzados ou cross-compilers são compiladores que geram código objeto para outras
máquinas que não são hospedeiras
Compiladores x Interpretadores
• Um programa gerado por um compilador tende a ser mais rápidos
que um programa executado por um interpretador, porem um
interpretadores oferecem melhora condições de diagnósticos de
erros.
Estrutura de um compilador
• O processo de compilação é muito complexo, porem existe uma
estrutura básica dividia em fases.
• As fases são representadas por duas tarefas a analise e a síntese.
• A tarefe de analise é conhecida como front-end e a tarefa de síntese é
conhecida como back-end.
• Front-end tem a função de garantira a estrutura gramatical e
semântica do programa fonte.
• Back-end tem o objetivo de construir o programa objeto.
• No processo de compilação pode ocorre a combinação de diferentes
linguagem fontes para diferentes maquinas alvo.
• A compilação inicia com a fase de analise léxica, que varre o programa
fonte e transfora o texto em conjunto de tokens.
• Logo após tem a analise sintática que garante a validade de todas as
regras semânticas do fluxo de tokens e cria a arvores sintática.
• A terceira fase é analise semântica que garante as validade das regras
semânticas.
• Na próxima fase temos a geração do código intermediário que cria
uma abstração do código fonte.
• Na sequencia temos a otimização do código intermediário
• E por fim a geração do código objeto.
• Os interpretadores são uma forma de tradução no qual as duas
ultimas fases de um compilador são substituídas por um programa
que executa o código intermediário.
• Dividimos os interpretadores em:
• Interpretadores puros: AS instruções são executadas uma a uma. Ex:
comandos shell.
• Integradores mistos: traduzem todo o script em código intermediário.
Analise Léxica
• Primaria faze do processo de compilação.
• Também conhecida como leitura ou scanning.
• Tem como objetivo identificar as unidade léxicas(lexemas).
• Le caractere a caractere do programa fonte.
• Os comentário e espaços em branco são removidos.
• O resultado é um conjunto de tokens.
• Nesse momento é iniciado a construção da tabelas de símbolos.
Analise Léxica – exemplo
123 x1 ; Y2 true begin
Lexema
Categoria
123
Constante inteira
X1
Nome de variável ou procedimento
;
Símbolo especial (ponto e vírgula)
Y2
Nome de variável ou procedimento
true
Constante booleana
begin
Palavra reservada
<nome-token, valor-atributo>
position = initial + rate * 60
Lexema
position
=
initial
+
rate
*
60
Símbolo
Id
Significado
Identificador
Entrada
1
Id
Identificador
2
Id
Identificador
3
Número
Inteiro
4
Token
<ID, 1>
<=>
<ID, 2>
<+>
<ID, 3>
<*>
<60>
<ID, 1> <=> <ID, 2> <+> <ID, 3> <*> <60>
Analise Sintática
• A analise sintática é o coração do compilador e tem com objetivo
validar os símbolos do programa.
• O objetivo é validar os símbolos que pertencem ao programa.
• Caso sejam invalido devem emitir um erro sintático informando a
posição exata do erro.
• A estrutura gramatica da linguagem é gerada.
• Os tokens são varridos com o objetivo de criar a árvore sintática.
if (a – 10 > b * 2) a = b;
• No caso do comando acima o analisador deve reconhecer como um
comando valido ou invalido.
position = initial + rate * 60
Mesmo com uma boa técnica de detecção de erros o analisador sintático deve recuperá-los e
continuar o processo de compilação identificando o maior número de erros possíveis.
Sintático tem o sentido de verificação de forma, estrutura sem referência a significado.
Analise Semântica
• O objetivo dessa etapa é garantir a semântica do programa fonte.
• Ele utiliza a arvore sintática e as informações da tabela de símbolos.
• Um exemplo de erro de semântica é operações incompatíveis com
tipos de dados.
• Índice de um vetor deve ser um inteiro.
• Caso necessário nessa fazer deve ser feito a conversão de tipos.
position = initial + rate * 60
• Suponha que a variável position for declarada como inteiro, nesse
caso deverá deve ser identificado um erro de tipo e o processo de
compilação deve ser interrompido.
• Caso position, initial, rate sejam declarados como
ponto flutuante o inteiro 60 deve ser convertido para ponto flutuante.
• Tipos de erros semânticos:
•
•
•
•
•
Tipos de operandos incompatíveis com operadores.
Identificadores não declarados (variáveis e procedimento).
Chamada de funções ou métodos com número incorreto de operadores.
Comando fora de contextos (um comando continue fora de um loop).
Operações de conversão.
Geração de código intermediário
• Nesse momento é gerado o código intermediário que vai ser utilizado
nas próximas fases da compilação.
• Essa faze podem não existir e ser feito diretamente a geração de
código objeto.
• O código intermediário não tem detalhes do código objeto final.
• A representação intermediária deve ser de fácil interpretação pois
será utilizada para a geração do código da máquina alvo.
T1 = inttofloar(60);
T2 = id3 * t1
T3 = id2 + t2
id1 = t3
• Exemplo de código intermediário gerado. Esse exemplo gera código
em uma forma conhecida como código de três endereços.
Uma das vantagens de gerar um código intermediário é a possibilidade de obter um
código final mais eficiente.
Otimização de Código
• Nessa faze o código é otimizado para possuir uma represarão que ira
consumir menos espaço em memória e ira ter velocidade de execução.
• Essa etapa não depende da arquitetura da maquina alvo.
T1 = id3 * 60.0
id1 = id2 * t1
• O numero de otimizações ira depender de como o compilador foi
implementado.
• E uma etapa que consome muitos recursos.
• Alguns compiladores tem uma fase chamada de otimização de código
dependente de maquina.
Geração de código objeto
• E a etapa final onde a representação intermediária e mapeada para
uma linguagem objeto.
• Se for linhagem de máquina gera o código binário para a arquitetura
especifica, fazendo a seleção de registradores alocando espaço na
memoria.
• É uma etapa muito importante pois deve produzir um código objeto
eficiente com uma cuidadosa seleção de registradores.
position = initial + rate * 60
LDF R2,
MULF R2,
LDF R1,
ADDF R1,
STF id1
id3
R2 #60.0
id2
R1, R2
R1
• O programa objeto reflete as instruções de baixo nível da plataforma
que esta sendo utilizada.
• Após essa faze concluir um programa chamado linkeditor reúne
outros programas objetos e recursos adicionais e monta o arquivo
executável.
Linkeditor ou Linker é um programa que reúne módulos compilados e arquivos para criar o
programa executável.
Registradores são áreas no processador que possuem uma grande velocidade e são utilizados
para armazenar valores. Existem vários tipos de registradores com finalidade especificas.
Tabela de símbolos
• Durante toda a faze de compilação algumas informações são
armazenadas em uma tabela chamada de tabela de símbolos. As
informações coletadas nessa tabela dependem do tipo de tradutor
desenvolvido e do programa objeto a ser gerado.
• Exemplo de informação armazenadas na tabela de símbolos
• Variáveis: classe(var), tipo, endereço no texto, posição e tamanho.
• Parâmetros formais: classe(par), tipo mecanismo de passagem.
• Procedimentos/sub-rotinas: classe(proc), número de parâmetros.
• A tabela de símbolos é uma estrutura de dados utilizada em todo o
processo de compilação e tem como objetivo extrair e inserir
informação de forma rápida.
Construção de compiladores
• Os avanços nas linguagem de programação impõem vários desafios
aos projetistas de compiladores. Eles devem criar algoritmos para
traduzir esse recursos para linguagem de maquina.
• Outro desafio e a evolução da arquitetura de computadores.
• A tradução para uma linguagem objeto deve tirar o máximo de
proveito sobre o hardware e o software.
• A compilação tem um papel muito importante no desempeno de
sistemas computacionais.
• A ideia da disciplina não é ensinar todas as técnicas e algoritmos
envolvidos no processo e compilação, pois é algo muito complexo e
infinito.
Java é interprestado ou compialdo?
• O Java é um exemplo incomum de um sistema que combina
compilação e interpretação.
• O javac compila o código fonte para byte codes.
• O java interprea os byte codes na JVM.
• Ainda tem o Just-in-Time Compiler que compila para linguagem de
máquina os byte codes mais utilizados.
Exercícios