2 Introdução - Compiladores CEFET MG

Prévia do material em texto

Compiladores 
Prof.ª Kecia Aline Marques Ferreira 
CEFET-MG 
 
Introdução 
1 
Introdução 
• Conceitos 
• Sistema de Processamento de Linguagens 
• A estrutura de um compilador 
2 
Conceitos 
3 
Conceitos 
• Compilador é um processador de linguagens. 
 
• Compilador: é um programa que traduz um programa escrito 
em uma linguagem (linguagem fonte) e gera um programa 
equivalente escrito em outra linguagem (linguagem alvo ou 
linguagem objeto). 
Programa 
fonte 
Programa 
objeto 
Compilador 
4 
Conceitos 
• Interpretador: é também um processador de linguagens. 
 
• Interpretador: em vez de gerar um programa objeto, executa 
diretamente as instruções presentes no programa fonte. 
 Em outras palavras, o interpretador executa o programa fonte 
instrução por instrução. 
 
 
5 
Conceitos 
• Compiladores híbridos: é possível combinar compilação e 
interpretação. 
 
– Em Java, essas duas abordagens são combinadas. 
– A compilação de um programa Java gera uma 
representação intermediária denominada bytecodes. 
– Os bytecodes são interpretados por uma máquina virtual, a 
JVM (Java Virtual Machine) 
 
6 
Conceitos 
Programa 
fonte Java 
Compilador 
Java 
Bytecode Interpretador 
Java 
Máquina alvo Entrada do 
usuário 
Saída do 
usuário 
7 
Conceitos 
• Compilação X Interpretação: 
 
– A execução de programas interpretados tende a ser mais 
lenta do que aqueles que foram compilados em programa 
executável. 
 
– O compilador híbrido, como aquele adotado em Java, 
favorece portabilidade dos programas. 
 
8 
Sistemas de Processamento de 
Linguagens 
9 
Sistema de Processamento de Linguagens 
• A criação de um programa objeto executável envolve outros 
programas além do compilador. 
 
• Pré-processador: realiza operações sobre o programa fonte 
antes de ele ser compilado. Por exemplo: 
 
– O programa fonte em uma linguagem pode estar dividido em 
módulos. Neste caso, o pré-processador é responsável por coletar os 
programas fonte. Exemplo: diretiva include de C/C++. 
 
– O programa fonte pode conter macros. Neste caso, o pré-processador 
tem a tarefa de expandir as macros. Exemplo: diretiva define de 
C/C++. 
10 
Sistema de Processamento de Linguagens 
 
• Compilador: traduz o programa fonte (possivelmente 
modificado pelo pré-processador) em um programa objeto. 
Geralmente o programa objeto é gerado em uma linguagem 
simbólica (linguagem de montagem ou assembly). 
 
• Montador (assembler): processa o código gerado em 
assembly e produz código de máquina relocável. 
 
• Editor de Ligação (link editor): realiza ligação dos códigos 
relocáveis produzidos de forma a gerar o código que 
realmente será executado. 
11 
Sistema de Processamento de Linguagens 
Pré-processador 
Compilador 
Montador 
Editor de Ligação / 
Carregador 
Programa fonte 
Programa fonte modificado 
Programa objeto em assembly 
Código de máquina relocável 
Outros arquivos objeto 
relocáveis 
Código de máquina alvo 
12 
A Estrutura de um Compilador 
13 
A Estrutura de um Compilador 
• Um compilador é um programa cujas funcionalidades são 
divididas em duas etapas: análise e síntese. 
 
• Análise 
– Também denominada de front-end do compilador. 
– O compilador subdivide o programa fonte e o submete a análise a fim 
de verificar sua correção conforme a linguagem de programação fonte. 
– Compreende análise léxica, análise sintática e análise semântica. 
– Na presença de uma não conformidade com as especificações da 
linguagem fonte, o compilador apresenta mensagem esclarecedora do 
erro. 
– O compilador armazena informações sobre o programa fonte em uma 
estrutura denominada tabela de símbolos. 
 
 14 
A Estrutura de um Compilador 
– Opcionalmente, o compilador 
• Gera uma representação intermediária do programa 
• Realiza otimizações no programa gerado 
 
• Síntese 
– Também denominada de back-end do compilador. 
– O compilador constroi o programa objeto com base na representação 
intermediária (código intermediário) e nas informações da tabela de 
símbolos. 
– Alguns compiladores podem realizar também otimizações nos código 
gerados 
 
 
 
 15 
A Estrutura de um Compilador 
 
 
 
Front-end 
Back-end 
Programa fonte 
Fluxo de caracteres 
Analisador Léxico 
Fluxo de tokens 
Analisador Sintático 
Árvore de Sintaxe 
Gerador de Código Intermediário 
Gerador de Código 
Representação intermediária 
Código da máquina alvo 
16 
Analisador Semântico 
Árvore de Sintaxe 
Análise Léxica 
• A primeira fase do compilador é a análise léxica ou leitura (scanning). 
 
• O analisador léxico lê o arquivo do programa fonte, caractere a caractere, 
e os agrupa em sequências significativas denominadas lexemas. 
 
• Para cada lexema obtido do código fonte, o analisado léxico gera um 
token no formato abaixo. Esse token é passado para o analisador sintático. 
 
<nome_token, valor_atributo> 
 
– nome_token: é um símbolo abstrato representativo do lexema. É 
utilizado no analisador sintático. 
– valor_atributo: no caso de identificadores, aponta para uma entrada 
da tabela de símbolos referente ao token. É útil para a análise 
semântica e para a geração de código. 
 
 17 
Análise Léxica 
• Exemplo: 
precoTotal = 5+ precoUnitário * quantidade 
 Neste comando, identificam-se os seguintes lexemas e seus respectivos 
tokens: 
 
– precoTotal : <id, 1>, onde id é um símbolo que representa identificador e 1, a 
posição da tabela de símbolos na qual estão armazenadas informações sobre precoTotal, 
por exemplo, seu nome e tipo de dado. 
– = : <=>. Esse token representa a operação de atribuição. Ele dispensa o valor do 
atributo, pois não há informações a serem armazenadas na tabela de símbolos. 
– 5: <const, 5> 
– + : <+> 
– precoUnitario: <id, 2> 
– * : <*> 
– quantidade: <id, 3> 
 
 
 
 
18 
Análise Léxica 
 
 
Posição Atributo Outras 
informações 
1 precoTotal ... 
2 precoUnitario ... 
3 quantidade ... 
Tabela de Símbolos 
19 
Gerenciamento da Tabela de Símbolos 
• A tabela de símbolos é uma estrutura de dados na qual são armazenadas 
informações sobre os nomes utilizados no programa: 
 
– Nome, tipo, escopo, espaço de memória alocado 
 
– No caso de funções: quantidade e tipos de argumentos , tipo de retorno, método de 
passagem de parâmetro 
 
 
• A estrutura deve ser projetada de forma a permitir que o 
compilador armazene e recupere rapidamente dados de 
nomes encontrados no programa fonte. 
 
20 
Análise Sintática 
• A segunda fase do compilador é a análise sintática. 
 
• O analisador sintático recebe como entrada os tokens identificados pelo 
analisador léxico e cria uma representação da estrutura gramatical da 
sequência de tokens. 
 
• A representação utilizada pelo analisador sintático é uma árvore sintática. 
 
• O analisador sintático verifica se a ordem em que os tokens aparecem no 
código fonte está de acordo com a sintaxe da linguagem. 
 
• Por exemplo: em C, funcao1)( está sintaticamente incorreto. 
 
 
21 
Análise Semântica 
• A terceira fase do compilador é a análise semântica. 
 
• O analisador semântico utiliza a tabela de símbolos e a árvore sintática 
gerada pelo analisador sintático para verificar se o programa está 
semanticamente de acordo com as especificações da linguagem fonte. 
 
• A atividade principal realizada pelo analisador semântico é a verificação 
de tipos: consiste em verificar se cada operadorpossui operandos 
compatíveis 
 
 
22 
Geração de Código Intermediário 
• Uma representação intermediária (código intermediário) de baixo nível 
pode ser gerada pelo compilador a fim de facilitar a tradução para a 
linguagem alvo. 
 
• Exemplo de representação intermediária: código de três endereços. 
– Sequência de instruções do tipo assembly 
– Cada instrução possui até três operandos 
– Cada instrução de atribuição possui no máximo um operador do lado direito 
– O compilador precisa gerar um nome temporário para guardar o valor computado 
 
t1 = id3 
t2 = t1 * id2 
t3 = 5 + t2 
id1 = t3 
 
23 
Exemplo de código de três endereços gerado para 
a = 5 + x * y 
Otimização de Código 
• A fase de otimização (independente de arquitetura) realiza modificações 
no código intermediário a fim de otimizá-lo. 
 
• Otimizar geralmente significa tornar o código mais rápido. 
 
• Isso pode ser obtido, por exemplo, pela redução da quantidade de 
instruções no código. 
 
• No exemplo anterior, o código poderia se melhorado da seguinte forma: 
 
t1 = id3 * id2 
id1 = t1 + 5 
24 
Geração de Código 
• O gerador de código recebe como entrada o código intermediário e o 
mapeia para a linguagem objeto. 
 
• Se a linguagem objeto for código de máquina, devem ser selecionados os 
registradores e localizações de memória para as variáveis do programa. 
 
• O programa intermediário do exemplo anterior poderia ser mapeado para 
o seguinte conjunto de instruções 
 
LD R2, id3 
LD R1, id2 
MUL R1, R1, R2 
ADD R1, R1, #5 
STR id1, R1 
 
25 
Exercício 
• Na sua linguagem preferida (C/C++ ou Java), dê 2 exemplos de: 
 
 - Erros léxico 
 - Erros sintático 
 - Erros semântico 
 
 
 
26 
Referência Bibliográfica 
 Compiladores – Princípios, técnicas e ferramentas. 
 Alfred V. Aho, Monica S. Lam, Ravi Sethi e Jeffrey D. Ullman. 2ª 
edição. Addison Wesley. 
 Capítulo 1. 
 
27