Skip to content

Latest commit

 

History

History
311 lines (288 loc) · 9.86 KB

introducao.org

File metadata and controls

311 lines (288 loc) · 9.86 KB

Visão geral de um compilador

1 Linguagens de Programação

  • Modelos de Linguagem de Programação (MLP)
  • Linguagem de programação
    • meio de comunicação entre o usuário e o computador \linebreak

./img/pensamento_humano-computador.png

  • <2->Linguagens em diferentes níveis de abstração
    • Baixo nível (de máquina, usada pelo computador)
    • Alto nível (próxima ao pensamento humano)

2 Níveis de Abstração em Linguagens

  • Linguagens de máquina
    • Seqûencia de zeros e uns (0011010000011101)
    • Notação binária
  • <2->Linguagens Simbólicas
    • Exemplo: Assembly
    • Add 4(0), #1
  • <3-> Linguagens orientadas ao usuário
    • Maioria das linguagens de programação
      • C, Fortran, Pascal, Algol, Ada, Objective-C, C++
      • *x += 1;
  • <4->Linguagens orientadas à aplicação (scripts)
    • Excel, SQL, Matlab, R, …

3 Tradução de Linguagens de Programação

  • Duas definições para compilador
  • <1-> Forte: é um programa de computador que transforma uma linguagem de alto nível qualquer em uma linguagem de máquina de uma determinada arquitetura

./img/programa_fonte-compilador-objeto.png \vfill

  • <2-> Fraca: é um programa de computador que transforma uma linguagem de alto nível em outra linguagem qualquer \vfill
  • <3-> Compilador ou interpretador?
    • Há diferença
  • <4-> Combinando as duas abordagens
    • Exemplo: Java, Python
    • Por questões de desempenho

4 Passos no processo de tradução

4.1 Texto

  • Várias etapas
  • Programas auxiliares
    • Normalmente embutidos
  • <2->Exemplo utilizando gcc
    • gcc -E hello.c > hello-pre.c
    • gcc -c hello-pre.c -o hello.o
    • nm hello.o
    • gcc hello.o -o hello
    • nm hello
    • ldd hello
    • hexdump hello.o | wc -l
    • hexdump hello | wc -l

4.2 Figura

\vfill

./img/etapas_compilacao.png

5 Partes do processo de compilação

  • Análise (front-end)
    Reconhecer o que o usuário quer escrever
    • “Palavras” → análise lexical
    • “Frases” → análise sintática/semântica
    • Detecção de erros \vfill
  • <2->Síntese (back-end)
    Produzir alguma coisa, em função da análise
    • Meta-representação do programa (código intermediário)
    • Tabela de símbolos
    • Código otimizado

6 Estrutura de um Compilador em etapas

./img/fases_compilacao.png

7 Análise Lexical (scanner)

  • Identificar sequências significativas na entrada: lexemas
  • Quando um lexema é identificado, gera um token
  • Funções adicionais
    • Começa a construção da tabela de símbolos
    • Detecção de erros léxicos, gerando mensagens de erro

./img/analisa_lexica.png

  • Um token é composto de: <nome-token, valor-atributo>
  • Exemplo

8 Como reconhecer os tokens?

  • Através do uso de Expressões Regulares
  • Algumas regras para formação de palavras válidas
    • Concatenação: xy (x seguido de y)
    • Alternação: x|y (x ou y)
    • Repetição: x* (x repetido 0 ou mais vezes)
    • Repetição: x+ (x repetido 1 ou mais vezes)
  • <2->As mesmas expressões regulares usadas correntemente
    • vim – usando o comando <regexp>
    • emacs – Crtl + Alt + % “Query replace regexp ->”
    • grep, sed, …
  • <3-> Existe uma multitude de recursos de apoio

9 Análise Sintática (parsing)

  • Tem como entrada um fluxo de tokens
  • Mapeia sequências de tokens para estruturas sintáticas
  • Cria uma Árvore de Sintaxe
    • Nós intermediários representam operações
    • Filhos desses nós representam os argumentos

./img/analisa_sintatica.png

  • Funções
    • Verificar a estrutura gramatical do programa
    • Detecção de erros sintáticos, gerando mensagens de erro
    • Tentar sobreviver a um erro sintático

10 Como construir a árvore de sintaxe?

Através do uso de Gramáticas Livres de Contexto

  • Conjunto de símbolos terminais (T), símbolos não-terminais (NT)
  • Conjunto de produções (ou Regras de derivação) \linebreak <NT> → sequência de <T> ou <NT>
  • Um <NT> como o símbolo inicial da gramática
  • Notação para gramáticas: BNF (Backus-Naur Form)
    <comando>→<while>
    <comando>→<atrib>
    <while>→while <expr-bool> do <comando>
    <atrib>→<variável> = <expr-arit>
    <expr-bool>→<expr-arit> < <expr-arit>
    <expr-arit>→<expr-arit> + <termo>
    <expr-arit>→<termo>
    <termo>→<número>
    <termo>→<variável>
    <variável>→i
    <variável>→j
    <número>→100

11 Árvore de derivação

  • Ilustra a derivação das regras de uma gramática
  • Considerando a entrada: while i < 100 do i = j + i

./img/arvore_derivacao.png

12 Análise Semântica

  • Avaliar a consistência semântica do programa
  • Verificação de tipos
    • Métodos de coerção (caso a definição da linguagem autorisar)
  • Exemplo

13 Geração de Código Intermediário

  • Usa a representação interna do compilador
  • Gera código objeto ou intermediário
  • Se for um código intermediário
    • não especifica detalhes arquiteturais
    • registradores
    • endereçamento, etc
  • Exemplo com código de três endereços
  • <2->Exemplo considerando a entrada: while i < 100 do i = j + i 
    L0: if i < 100 goto L1
    goto L2
L1: temp = i + j
    i = temp
    goto L0
L2: ...

14 Otimização de Código

  • Realizar otimizações sobre o código intermediário
    • Desempenho durante a execução
    • Eficiência na ocupação dos recursos \linebreak → diminuir quantidade de memória, de registradores

\vfill

  • <2->Exemplo a partir do código de três endereços
    • Considerando a entrada: while i < 100 do i = j + i
  • <3-> Código original \scriptsize 
    L0: if i < 100 goto L1
    goto L2
L1: temp = i + j
    i = temp
    goto L0
L2:
  • <4-> Código otimizado \scriptsize 
    L0: if i >= 100 goto L2
    i = i + j
    goto L0
L2:

15 Geração de Código Objeto

  • Gerar código objeto considerando
    • Qual é a arquitetura alvo
    • Alocação de memória
    • Seleção de registradores
  • Exemplo considerando a entrada: while i < 100 do i = j + i

15.1 <2-> Código Otimizado

\scriptsize 
L0: if i >= 100 goto L2
    i = i + j
    goto L0
L2:

\vspace{1cm}

15.2 <2-> Código Objeto para PC8086

\scriptsize 
L0: MOV AX, i
    CMP AX, 100
    JGE L2     //jump condicional
    MOV AX, j
    MOV BX, i
    ADD BX
    MOV i, AX
    JMP L0     //jump não condicional
L2: ...

\vspace{1cm}

16 Gerência da Tabela de Símbolos

  • Acompanha todas as fases do compilador
  • Guarda atributos das variáveis e funções do programa
  • <2->Atributos de variáveis
    • Espaço de memória
    • Tipo
    • Escopo
  • <2-> e de funções
    • Quantidade e tipos de argumentos
    • Método de passagem de parâmetro (valor, referência, …)
    • Tipo de retorno

\vfill

  • <3-> Acesso eficiente
    • Inserção
    • Extração

17 Tratamento e Recuperação de Erros

  • O que fazer quando um erro é detectado?
    (considerando apenas erros léxicos e sintáticos?)
  • <2-> Sobreviver, se recuperando da seguinte forma
    • Fazer uma suposição a respeito do erro
    • Continuar a análise confiando na suposição feita

\vfill

  • <3-> Como sobreviver a um erro léxico?
  • <3-> Como sobreviver a um erro sintático?
  • <3-> E sobre erros de geração/otimização de código?

18 Estrutura Geral de um Compilador

./img/fases_compilacao.png

19 Geradores de Compiladores

  • Análise Léxica – flex
  • Análise Sintática – bison
  • Gerador de Código

20 Conclusão da Aula de Hoje

  • Estrutura geral de um compilador
  • Leituras recomendadas
    • Capítulo 1 de Aho et. al. (Dragão Roxo ou Vermelho)
      • Cuidado na versão em português
    • Capítulo 1 de Price & Toscani (2008)
    • http://dinosaur.compilertools.net
      Toda a turma: Lex | Yacc | Flex | Bison
  • Próxima aula
    • Análise Léxica
    • Expressões Regulares