Embed Size (px)
Citation preview
MOTIVACAO
• Entender os algor ıtmos e estruturas usados para seimplementar linguagens de programacao
• Conhecimento pode ser usado para resolver varios tipos deproblemas: editores de texto, conversores de arquivos, etc.
• Uso do conhecimento adquirido em varias disciplinas do cursode Ciencia da Computacao: Algor ıtmos e Estruturas deDados, Linguagens Formais, Arquitetura de Hardware, etc.
MOTIVACAO 2
MOTIVACAO
• Conhecimento Util: como escolher uma linguagem adequadapara resolver um problema espec ıfico, comparar eficiencia delinguagens, gerenciamento de memoria
• Provavelmente uma das disciplinas mais interessantes docurso de Ciencia da Computacao
MOTIVACAO 3
CURSO DE COMPILADORES
1. Compiladores
2. Fases de um Compilador
• Analise Lexica
• Analise Sintatica
• Analise Semantica
• Geracao de Codigo Intermediario
• Otimizacao de Codigo Intermediario
• Geracao de Codigo Alvo
3. Traducao Dirigida Por Sintaxe
4. Sistemas de Tempo de Execucao
5. Gerencia de Memoria
6. CONSICO (Congresso Simulado de Compiladores)
CURSO DE COMPILADORES 4
INTRODUCAO
• Linguagens de Programacao
• Compiladores
• Fases de um Compilador
– Analise Lexica
– Analise Sintatica
– Analise Semantica
– Geracao de Codigo Intermediario
– Otimizacao de Codigo Intermediario
– Geracao de Codigo Alvo
INTRODUCAO 5
LINGUAGENS
• Linguagem de programacao: Meio de comunicacao entre oprogramador e o computador
• Fornece ligacao entre o pensamento humano e a precisaorequerida pela maquina
• O desenvolvimento de um programa e mais facil se alinguagem estiver mais prox ıma do problema a ser resolvido(Linguagem de Alto N ıvel)
LINGUAGENS 6
LINGUAGENS (CONT.)
• Computadores entendem apenas sua propria linguagem demaquina (Linguagem de Baixo N ıvel). Zeros e Uns.
• Programas hoje em dia sao geralmente escritos emLinguagens de Alto N ıvel
• Programas escritos em linguagens de alto n ıvel devem sertraduzidos para linguagem de maquina atraves decompiladores/interpretadores
LINGUAGENS (CONT.) 7
EVOLUCAO DAS LINGUAGENS DE PROGRAMACAO
1. Linguagem de Maquina
• Computadores eram programados em linguagem de maquina,usando operacoes de maquina primitivas, formadas por umcodigo de operacao e dois enderecos de registradores oumemoria
• Inicialmente usando zeros e uns: 00010000 0000011100000101
• Problemas: dif ıcil de ler, escrever, modificar, fortemente sujeitaa erros
EVOLUCAO DAS LINGUAGENS DE PROGRAMACAO 8
2. Linguagem de Montagem
• Oferece uma notacao simbolica, sao usados nomes ao invesde codigo binario (b = a + 2 )
MOV a, R1
ADD #2, R1
MOV R1, b
• Linguagem Assembly
• Montador / assembler: transforma o programa em Assemblypara linguagem de maquina
• Uma instrucao em assembly equivale a uma instrucao emlinguagem de maquina
EVOLUCAO DAS LINGUAGENS DE PROGRAMACAO 9
2. Linguagem de Alto Nıvel
• Maior n ıvel de abstracao:
let s = (a+b+c)/2
in sqrt (s*(s-a)*(s-b)*(s-c) )
• Ao inves de:
LOAD R1 a; ADD R1 b; ADD R1 c; DIV R1 #2;
LOAD R2 R1; LOAD R3 R1; SUB R3 a;
MULT R2 R3; LOAD R3 R1; SUB R3 b;
MULT R2 R3; LOAD R3 R1; SUB R3 c;
MULT R2 R3; LOAD R0 R2; CALL sqrt;
EVOLUCAO DAS LINGUAGENS DE PROGRAMACAO 10
TRADUTORES DE LINGUAGEM
• Montadores (Assemblers)
• Macro-Assemblers
• Compiladores
• Interpretadores
TRADUTORES DE LINGUAGEM 11
COMPILADORES
COMPILADOR: programa que le um programa escrito em umalinguagem fonte e o traduz para um programa equivalente numa
outra linguagem (linguagem alvo)
FONTEPROGRAMA PROGRAMA
ALVO
MENSAGENS DE ERRO
COMPILADOR
COMPILADORES 12
Fases de Um Compilador
FONTEPROGRAMA PROGRAMA
ALVO
MENSAGENS DE ERRO
Análise Síntese
• Analise: reconhece o programa e divide em suas partesconstituintes criando uma representacao intermediaria domesmo
• S ıntese: Constroi o programa alvo desejado, a partir darepresentacao intermediaria
• Tambem conhecidas como Front-end e Back-end docompilador
COMPILADORES 13
FASES DO COMPILADOR
programa fonte
Léxico Analisador
Analisador Sintático
Analisador Semântico
Gerador de CódigoIntermediário
programa alvo
Otimizadorde Código
Geradorde Código
Análise (Front−End)Síntese (Back−End)
Tabela de Simbolos
FASES DO COMPILADOR 14
ANALISE
• Operacoes sao reconhecidas e registradas numa estruturachamada de Arvore Sintatica
• Cada no representa uma operacao e seus filhos representamos argumentos da operacao
• Exemplo: montante := deposito inicial +
taxa de juros * 60
60deposito_inicial
montante
:=+
*
taxa_de_juros
ANALISE 15
ANALISE
• Varios tipos de software realizam algum tipo de analise:
– Editores de Programas
– Pretty Printers
– Interpretadores
ANALISE 16
TIPOS DE ANALISE
• Analise Lexica: programa e lido (escaneado) e agrupado emtokens i.e., sequencias de caracteres com um significadocoletivo
• Analise Sintatica: tokens sao agrupados hierarquicamente emuma arvore sintatica (baseda na gramatica da linguagem)
• Analise Semantica: o programa e verificado para garantir queos componentes de um programa se combinam de formasignificativa
TIPOS DE ANALISE 17
ANALISE LEXICA
• Fazer a leitura do programa fonte, e traduz ı-lo para umasequencia de sımbolos lexicos, tambem chamados de tokens.Exemplo:
montante = deposito_inicial +taxa_de_juros * 60
Tokens:
1. O identificador montante
2. O s ımbolo de atribuicao :=
3. O identificador deposito inicial
4. O sinal de adicao +
5. O identificador taxa de juros
6. O sinal de multiplicacao *
ANALISE LEXICA 18
7. O n umero 60
Os espacos e linhas sao ignorados
ANALISE LEXICA 19
ANALISE SINTATICA
• Verifica se o programa foi escrito respeitando as regrasgramaticais da linguagem
• Agrupa tokens do programa fonte em frases gramaticais, quesao usadas pelo compilador para gerar a sa ıda
• A gramatica e geralmente definida usando regras recursivas
Exemplo: Regras Recursivas para Expressoes:
1. Qualquer identificador e uma expressao
2. Qualquer numero e uma expressao
3. Se expressao1 e expressao2 sao expressoes, entao tambem osao
expressao1 + expressao2
expressao1 * expressao2
ANALISE SINTATICA 20
Exemplo: Enunciado de uma linguagem de programacao
• Se identificador1 e um identificador e expressao2 e umaexpressao, entao
identificador1 := expressao2
e um enunciado
• Gramatica livre de contexto
ANALISE SINTATICA 21
Arvore Gramatical Exemplo: montante := deposito inicial +
taxa de juros * 60
enunciado deatribuicão
:=
identificador
montante
expressão
expressão
identificador
deposito_inicial
expressão
expressão expressão
identificador número
60taxa_de_juros
+
*
ANALISE SINTATICA 22
ANALISE SEMANTICA
• Verifica erros semanticos e de tipos
• Exemplo: detecta que um n umero real esta sendo usado paraindexar um vetor
• Normalmente, valores em uma linguagem sao classificadospor tipos
• Operacoes possuem regras de tipo, definindo os tipos dosoperandos e resultado
• Uma operacao usando um tipo errado gera um erro de tipo
ANALISE SEMANTICA 23
EXEMPLO DE REGRAS DE TIPO
• Operador +
Se os dois operandos sao do tipo Int o resultado deve ser dotipo Int
• Operador While E do C
E deve possuir tipo Bool
EXEMPLO DE REGRAS DE TIPO 24
ANALISE SEMANTICA (CONT.)
• A semantica da linguagem pode permitir algumas coercoes detipo
• Exemplo: montante := deposito inicial +
taxa de juros * 60
60deposito_inicial
montante
:=+
*
taxa_de_juros
ANALISE SEMANTICA (CONT.) 25
ANALISE SEMANTICA (CONT.)
• Exemplo: montante := deposito inicial +
taxa de juros * 60
deposito_inicial
montante
:=+
*
taxa_de_juros intToReal 60
ANALISE SEMANTICA (CONT.) 26
TABELA DE S IMBOLOS
• A Tabela de Sımbolos e uma estrutura de dados que contemum registro para cada identificador, com campos contendoseus atributos
• Atributos: tipo, memoria reservada, se e um procedimento,n umero e tipo dos argumentos, tipo de retorno etc.
• A tabela permite encontrar rapidamente cada registro,armazenar e recuperar dados do mesmo
• A tabela e preenchida e usada por todas as fases
var montante, deposito_inicial: real;
– Os identificadores sao inseridos na tabela durante aanalise lexica,mas o tipo nao e conhecido no momento emque e inserido
TABELA DE S IMBOLOS 27
FASE DE ANALISE (FRONT-END)
:=
id1
id2id3 60
+*
id1 := id2 + id3 * 60
Analisador Léxico
montante := deposito_inicial + taxa_de_juros + 60
:=
id1
id2id3
+*
60
intToReal
Analisador Semântico
Analisador Sintático
Back − End
código de máquina
TABELA DE SIMBOLOS1 montante | ...2 deposito_inicial | ...3 taxa_de_juros | ...
FASE DE ANALISE (FRONT-END) 28
GERACAO DE CODIGO INTERMEDIARIO
• Alguns compiladores, depois da fase de Analise, geram umarepresentacao intermediaria do programa final
• Propriedades do Codigo Intermediario: Facil de produzir,otimizar e traduzir para a linguagem alvo
• Vantagens
– Portabilidade: O codigo intermediario e independente deplataforma, por isso pode ser traduzido para diversasmaquinas
– Simplifica a implementacao do compilador, resolvendogradativamente o problema de transformar o codigo de alton ıvel em codigo de baixo n ıvel
– Facilita otimizacao do codigo final
GERACAO DE CODIGO INTERMEDIARIO 29
EXEMPLO DE CODIGO INTERMEDIARIO
• Codigo de tres enderecos: sequencia de instrucoes, cada umapossuindo no maximo tres operandos
• Muito mais facil de se traduzir para codigo de maquina
montante := deposito_inicial + taxa_de_juros * 60
temp1 := inttoreal (60)
temp2 := id3 * temp1
temp3 := id2 + temp2
id1 := temp3
EXEMPLO DE CODIGO INTERMEDIARIO 30
OTIMIZACAO DE CODIGO
• Serve para melhorar o codigo intermediario
temp1 := id3 * 60.0
id1 := id2 + temp1
• A conversao de 60 para real pode ser feita durante acompilacao, eliminanto a instrucao inttoreal
• temp3 era usada apenas para transmitir seu valor para id1
por isso pode ser eliminada
• Existem varias transformacoes simples que podem ser usadaspara melhorar o codigo final
• Compiladores Otimizantes gastam boa parte do tempo decompilacao na faze de otimizacao
OTIMIZACAO DE CODIGO 31
GERACAO DE CODIGO
• E a fase final do compilador que gera codigo de maquina oucodigo de montagem (assembly)
• As instrucoes do codigo intermediario sao traduzidas parainstrucoes de maquina e registradores sao associados asvariaveis
• Exemplo:
montante := deposito_inicial + taxa_de_juros * 60
temp1 := id3 * 60.0
id1 := id2 + temp1
pode ser traduzido para
MOVF id3, R2
MULF #60.0, R2
GERACAO DE CODIGO 32
MOVF id2, R1
ADDF R2, R1
MOVF R1, id1
GERACAO DE CODIGO 33
FASE DE S INTESE (BACK-END)
:=
id1
id2id3
+*
60
intToReal
montante := deposito_inicial + taxa_de_juros + 60
TABELA DE SIMBOLOS1 montante | ...2 deposito_inicial | ...3 taxa_de_juros | ...
Front−End
temp1 := inttoreal (60)temp2 := id3 * temp1temp3 := id2 + temp2id1 := temp3
temp1 := id3 * 60.0id1:= id2 + temp1
MOVF ID3, R2MULF #60.0, R2(...)gerardor de código intermediário
otimizador de código
gerador de código
FASE DE S INTESE (BACK-END) 34
DETECCAO DE ERROS
• Cada fase da compilacao pode encontrar erros. Para se darmensagens de erro mais completas, o compilador nao paraassim que encontra o primeiro erro no codigo.
• Analise Lexica: erro quando encontra token invalido. Ex: nomevariavel comecando com n umero
• Analise Sintatica: erro quando o fluxo de tokens viola asregras da linguagem. Ex: Esquecer o BEGIN e END no Pascal.
• Analise Semantica: sintaxe correta mas significado errado. Ex:erro de tipo. Somar o nome de um array com o nome de umprocedimento. :-)
DETECCAO DE ERROS 35
CONTEXTO DE UM COMPILADOR
• Alem do compilador, varios outros programas podem sernecessarios para se criar um programa alvo executavel.
• Exemplo1: o programa pode estar dividido em modulos
• Exemplo2: a linguagem alvo pode nao ser linguagem demaquina
CONTEXTO DE UM COMPILADOR 36
UM SISTEMA DE PROCESSAMENTO DE LINGUAGEM
programa fonte
programa
programa objeto em linguagem de montagem
compilador
montador
carregador
bibliotecas
pré−processador
código de máquina relocável
código de máquina absoluto
UM SISTEMA DE PROCESSAMENTO DE LINGUAGEM 37
INTERPRETADORES
• Primo do compilador
• Gera codigo intermediario, que e executado por um programaou maquina virtual, sem gerar codigo de maquina
Tradutor Interpretador(Máquina Virtual)
programaintermediário
resultadosfonteprograma
• Alguns interpretadores nao geram codigo intermediario,apenas executam as instrucoes presentes no codigo fonte,assim que encontradas, uma por vez. Ex: interpretador dalinguagem BASIC
INTERPRETADORES 38
INTERPRETADORES
• O tempo de traducao da linguagem em um Interpretador, emuito mais rapido do que em um compilador, ja que nao enecessario gerar codigo de maquina
• O tempo de execucao em um interpretador e geralmente muitomais longo do que se usando codigo compilado paralinguagem de maquina
• Interpretador e muito mais facil de usar e possui mensagensde erro melhores ja que o processo de interpretacao e feitoproximo ao codigo fonte
INTERPRETADORES 39
