Compiladores
● Um compilador é um programa que lê um programa escrito em uma
linguagem (linguagem fonte) e a traduz em um programa equivalente em
outra linguagem (linguagem alvo).” Aho, Sethi, Ullman.
● Para desempenhar suas tarefas, um compilador deve executar dois tipos
de atividade. A primeira atividade é a análise do código fonte, onde a
estrutura e significado do programa de alto nível são reconhecidos. A
segunda atividade é a síntese do programa equivalente em linguagem
simbólica. Embora conceitualmente seja possível executar toda a análise
e apenas então iniciar a síntese, em geral estas duas atividades ocorrem
praticamente em paralelo.
Tradução
● Nesse processo de tradução, há duas tarefas básicas a
serem executadas por um compilador:
○ Análise, em que o texto de entrada (na linguagem fonte) é
examinado, verificado e compreendido
■ Análise léxica, sintática e semântica
○ Síntese, ou geração de código, em que o texto de saída (na
linguagem objeto) é gerado, de forma a corresponder ao texto de
entrada
É possível representar completamente a sintaxe de uma LP através
de uma gramática sensível ao contexto.
Mas como não existem algoritmos práticos para tratar essas
gramáticas, a preferência recai em usar gramáticas livres de
contexto.
Deixa-se para a análise semântica a verificação de todos os
aspectos da linguagens que não se consegue exprimir de forma
simples usando gramáticas livres de contexto.
A implementação de reconhecedores de linguagens regulares
(autômatos finitos) é mais simples e mais eficiente do que a
implementação de reconhecedores de linguagens livres de
contexto (autômatos de pilha).
Nesse caso, é possível usar expressões regulares para
descrever a estrutura de componentes básicos das LP, tais como
identificadores, palavras reservadas, literais numéricos, operadores
e delimitadores, etc.
Essa parte da tarefa de análise (análise léxica) é implementada
separadamente, pela simulação de autômatos finitos.
Arquivo
Haskell
'
Análise
O processo Parser
Verificador de Tipos
Desugarer
Otimizações Sintaxe Core CorePrinter
CoreToSTG Arquivo
Core
Sintaxe STG
Gerador GHC
Haskell.NET
Gerador de IL PhxSTGCompiler
Código Assembly
/ Código C Código MSIL
GHC Nativo
(Texto)
Assembler / ILDASM Assembly MSIL
Compilador C
Código Nativo JIT
Síntese
Código Nativo
Exemplo de código
● Parser - tradutor, lê linha por linha e traduz estruturas do texto.
● Verificador de tipos - analisa símbolos e funções, e verifica eles através de
um banco de dados
● Desugarer - comparador, pega o arquivo verificado pelo parser e compara
com uma estrutura padrão
● Sintaxe core - analisa a sintaxe do código, otimiza e aponta erros de
sintaxe
código fonte
Analisador
léxico
Analisador
sintático
Gerador tabela Analisador Tratador de
de símbolos semântico erros
Gerador de
código
intermediário
Otimizador
de código
Gerador de
código
código alvo
Análise Léxica
Também chamada de scanner
Agrupa caracteres em símbolos (ou tokens)
Entrada: fluxo de caracteres
Saída: fluxo de símbolos
Símbolos são:
◦ Palavras reservadas, identificadores de variáveis e procedimentos, operadores, pontuação,...
Uso de expressões regulares no reconhecimento
Lex/Flex são ferramentas que geram scanners.
Dado os caracteres da instrução
montante := saldo + taxa_de_juros * 30;
São identificados os seguintes tokens:
Identificador montante
Símbolo de atribuição :=
Identificador saldo
Símbolo de adição +
Identificador taxa_de_juros
Símbolo de multiplicação *
Número 30
Análise Sintática
Também chamada de parser
Agrupa símbolos em unidades sintáticas
Ex.: os 3 símbolos A+B podem ser agrupados em uma estrutura chamada
de expressão.
Expressões depois podem ser agrupados para formar comandos ou outras
unidades.
Saída: representação árvore de parse do programa
Gramática livre de contexto é usada para definir a estrutura do programa
reconhecida por um parser
Yacc/Bison são ferramentas para gerar parsers
Comando
:=
Identificador Expressão
montante +
Expressão Expressão
Identificador *
Expressão Expressão
saldo
Identificador Número
taxa_de_juros 30
Árvore gerada para: montante := saldo + taxa_de_juros * 30
Análise Semântica
Verifica se estruturas sintáticas, embora corretas sintaticamente, têm
significado admissível na linguagem.
Por exemplo, não é possível representar em uma gramática livre de
contexto uma regra como “todo identificador deve ser declarado antes
de ser usado“
Um importante componente é checagem de tipos.
Utiliza informações coletadas anteriormente e armazenadas na tabela de
símbolos
Considerando “A + B”, quais os possíveis problemas semânticos?
Saída: árvore de parse anotada
= =
montante + montante +
saldo * saldo *
taxa_de_juros 30 taxa_de_juros inttoreal
Conversão de inteiro para real inserida pela análise semântica
Gerador de Código Intermediário
● Usa as estruturas produzidas pelo analisador sintático e verificadas pelo
analisador semântico para criar uma seqüência de instruções simples
(código intermediário)
● Está entre a linguagem de alto nível e a linguagem de baixo nível
Gerador de Código Intermediário
Considere que temos um único registrador acumulador.
Considere o comando de atribuição
x := a + b * c
pode ser traduzido em:
t1:=b*c
t2:=a+t1
x:=t2
Pode-se fazer um gerador de código relativamente simples usando regras
como:
Toda operação aritmética (binária) gera 3 instruções. Para b*c
1. Carga do primeiro operando no acumulador
load b
2. Executa a operação correspondente com o segundo operando, deixando o resultado no acumulador
mult c
3. Armazena o resultado em uma nova variável temporária
store t1
Um comando de atribuição gera sempre duas instruções. Para x:= t2
1. Carrega o valor da expressão no acumulador
load t2
2. Armazena o resultado na variável
store x
Para o comando de atribuição
x := a + b * c;
é gerado o código intermediário:
1. Load b { t1 := b * c }
2. Mult c
3. Store t1
4. Load a { t2 := a + t1 }
5. Add t1
6. Store t2
7. Load t2
8. Store x { x := t2 }
Otimizador de Código
● Independente da máquina
● Melhora o código intermediário de modo que o programa objeto seja
menor (ocupe menos espaço de memória) e/ou mais rápido (tenha
tempo de execução menor)
● A saída do otimizador de código é um novo código intermediário
Gerador de Código
Produz o código objeto final
Toma decisões com relação à:
◦ Alocação de espaço para os dados do programa;
◦ Seleção da forma de acessá-los;
◦ Definição de quais registradores serão usados, etc.
O projeto de um gerador de código que produza
programas objeto eficientes é uma das tarefas mais
difíceis no projeto de um compilador
Até a próxima aula!
