01 intro Edjan Sobral Verissimo Michiles

Prévia do material em texto

Instrutor: Marcelo d’Amorim
IF688 – Teoria e Implementação de Linguagens Computacionais
(Compiladores)
www.cin.ufpe.br/~if688
Resumo desta aula
Informação administrativa do curso
Introdução
O que são e para que servem compiladores?
Aplicações da tecnologia
Organização de um compilador
2
Informação Administrativa
Avaliação
2 provas
Lista de email
if688-l@cin.ufpe.br
Todo aluno deve se cadastrar! 
Conteúdo
Avisos (e.g., datas e correção de provas)
Esclarecimentos de assuntos de aula e projeto
Por favor, enviem perguntas de interesse geral para lista!
Monitoria
Alunos de graduação que já cursaram a disciplina
Responsabilidade dos monitores:
Ministrar aulas práticas (no laboratório)
Responder dúvidas na lista de discussão
Responder dúvidas de projeto no laboratório
1 vez por semana, no período do projeto
Projeto
Grupos com 4 a 5 participantes
Entrada
Especificação do problema
Casos de teste
Entrega
Apenas 1
Penalidade de 1 ponto por dia de atraso
Aulas de laboratório
Após análise léxica e sintática
Após análise semântica
8
Material
Necessário
Slides, página web, lista de email
Opcional (referências na página)
MIT open courseware (ocw.mit.edu)
Livro do Dragão
Livro do Tigre
www.cin.ufpe.br/~if688
if688-l@cin.ufpe.br
Estrutura do curso
Parte 1 (Análise)
Background
Análise Léxica e Sintática
Análise Semântica
Parte 2 (Síntese)
Geração de código
Análise de dataflow e otimização de código
Análise de dependência
Prova 1
Prova 2
Pré-requisitos informais
Programação
Linguagens formais e autômatos
Lambda-cálculo e combinadores
Teoria dos grafos
INTRODUÇÃO
Definição de um compilador
Tradutor de uma linguagem mais abstrata (origem) para uma mais concreta (destino). Exemplo:
public class HelloWorld {
   public static void main(String[] args) {
       System.out.println("Hello"); }}
public class HelloWorld extends java.lang.Object{
public HelloWorld();
 Code:
  0:   aload_0
  1:   invokespecial   #1; //Method java/lang/Object."<init>":()V
  4:   return
public static void main(java.lang.String[]);
 Code:
  0:   getstatic       #2; //Field java/lang/System.out:Ljava/io/PrintStream;
  3:   ldc     #3; //String Hello
  5:   invokevirtual   #4; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
  8:   return
}
javac
javap
Para que serve um compilador?
...afinal, o programador poderia escrever direto na linguagem destino, mais concreta.
Afinal o programador poderia escrever direto na linguagem destino
14
Para que serve um compilador?
Facilitar programação (abstração)
Checar certos tipos de erros e vulnerabilidades
Gerar código portável
Otimizar código
velocidade, tamanho, energia, etc.
Afinal o programador poderia escrever direto na linguagem destino
15
Para que serve um compilador?
Facilitar programação (abstração)
Checar certos tipos de erros e vulnerabilidades
Gerar código portável
Otimizar código
velocidade, tamanho, energia, etc.
erro de sintaxe
erro léxico
variável não declarada
variável não inicializada
número ou tipo de argumentos inválidos em chamada de função
código inalcançável
Afinal o programador poderia escrever direto na linguagem destino
16
Linguagem Origem
Precisa 
Ambiguidade é indesejável
Expressiva
Pode caracterizar toda função computável (Turing complete)
Alto-nível
Provê abstrações para facilitar programação
Linguagem Destino
Específica: E.g., ARM, x86, MIPS, etc.
Portável: E.g., JVM, CLR, etc.
Tira vantagens de uma arquitetura particular.
18
E onde termina a tradução?
E onde termina a tradução?
Bootstrapping: Processo de tradução para a máquina mais interna/concreta, normalmente interpretada por hardware.
Cada camada representa/caracteriza uma máquina abstrata!
Diagrama T (Tombstone)
Símbolo à esquerda define linguagem origem. Símbolo à direita define linguagem destino e na base a linguagem de implementação.
Labels: C (ling. C) e M (ling. de máquina).
Representações intermediárias
Veremos que o compilador usa internamente outras representações de código representações intermediárias (IRs)
A utilidade da IR varia com a aplicação
Outras aplicações da tecnologia
Linguagens de domínio específico (DSLs)
Checagem de erros (e.g., Coverity)
Ferramentas de inspeção (e.g., Lint, JLint, FindBugs)
Instrumentação de código
Monitoração de eventos (e.g., AspectJ)
Profiling de memória e tempo (e.g., NetBeans)
Histórico
Demanda por linguagens de mais alto nível que linguagem de máquina e assembler
Nos anos 50, compiladores eram programas notadamente difíceis de se escrever
Avanço teórico e de técnicas e ferramentas de implementação tornou possível implementar compiladores com muito mais facilidade
Assemblers no início dos anos 50; Macro Assemblers;
Fortran, na segunda metade dos anos 50, juntamente com Cobol e Lisp.
24
ORGANIZAÇÃO DE UM COMPILADOR
Compilador, Interpretador, e VM
Compilador
Entrada
Pgm. Origem
Interpretador
Pgm. Origem
Entrada
Saída
Saída
Compilador
VM
Entrada
Pgm. Origem
Saída
Pgm. Destino
Pgm. Destino
compilador
pre-processador
assembler
linker-loader
Programa fonte
Programa fonte 
 modificado
Programa em assembler
Código objeto (relocável)
Código objeto (executável)
Bibliotecas /
código objeto
Processo de compilação
Linker resolve endereços de nomes externos não resolvidos dentro do próprio módulo; 
Loader carrega o programa na memória
27
compilador
pre-processador
assembler
linker-loader
Processo de compilação
origem
destino
Linker resolve endereços de nomes externos não resolvidos dentro do próprio módulo; 
Loader carrega o programa na memória
28
Duas etapas
Análise (front-end)
Cria representações intermediárias do programa
Verifica presença de certos tipos de erro
Síntese (back-end)
Constrói o programa destino a partir de representações intermediárias
C
x86
Front-end
ARM
código intermediário
MIPS
.NET
Back-end
Back-end
Back-end
Back-end
Front-end
Front-end
Front-end
C#
Pascal
Fortran
Separação entre front-end e back-end 
para criação de múltiplos compiladores
30
Duas etapas
Análise (front-end)
Cria representações intermediárias do programa
Verificação da presença de certos tipos de erro
Síntese (back-end)
Constrói o programa destino a partir de representações intermediárias.
Análise do programa fonte
Análise léxica
Organiza caracteres de entrada em grupos, chamados tokens
Análise sintática 
Organiza tokens em uma estrutura hierárquica
Análise semântica 
Checa se o programa respeita regras básicas de consistência
Análise Léxica (ou Scanning)
Lê os caracteres de entrada e os agrupa em sequências chamadas lexemas (tokens) 
Os tokens são consumidos na fase seguinte (parsing)
Exemplo
position = initial + rate * 60
<identificador, 1>, <=>, <identificador, 2>, <+>, <identificador, 3>, <*>, <number, 60>
nome
tipo
…
1
position
-
2
initial
-
3
rate
-
…
Tabela de Símbolos
Analisador 
Léxico
Exemplo
Analisador 
Léxico
O projetista do compilador caracteriza o analisador léxico através de expressões regulares (ERs).
Exemplo
Analisador 
Léxico
A geração do analisador léxico é automática a partir da definição das ERs. Ver: FLEX, JLex, etc.
Tabela de Símbolos
Estrutura de dados usada para guardar identificadores e informações sobre eles. 
Por exemplo:
tipo do identificador
escopo: onde o identificador é válido no programa
se for um procedimento ou função: número e tipo dos argumentos, forma de passagem dos parâmetros e tipo do resultado.
Tabela de Símbolos
nome
tipo
…
1
position
-
2
initial
-
3
rate
-
…
Usada e atualizada em várias etapas da compilação.
Análise sintática (ou Parsing)
A partir dos tokens cria uma estrutura em árvore (árvore sintática) que representa a estrutura gramatical do programa
Exemplo
<identificador, 1>, <=>, <identificador, 2>, <+>, <identificador, 3>, <*>, <number, 60>
Analisador 
Sintático
<id,2>
<id,3>
*
+
=
<id,1>
60
Exemplo
AnalisadorSintático
<id,2>
<id,3>
*
+
=
<id,1>
60
Gramática livre de contexto (BNF) caracteriza a linguagem.
<identificador, 1>, <=>, <identificador, 2>, <+>, <identificador, 3>, <*>, <number, 60>
Exemplo
<id,2>
<id,3>
*
+
=
<id,1>
60
<identificador, 1>, <=>, <identificador, 2>, <+>, <identificador, 3>, <*>, <number, 60>
Analisador 
Sintático
Gramática livre de contexto (BNF) caracteriza a linguagem.
A geração do parser a partir de uma BNF é automática. Ver Bison, JCup, yacc, etc.
Exemplo
<id,2>
<id,3>
*
+
=
<id,1>
60
<identificador, 1>, <=>, <identificador, 2>, <+>, <identificador, 3>, <*>, <number, 60>
Analisador 
Sintático
Gramática livre de contexto (BNF) caracteriza a linguagem.
A geração do parser a partir de uma BNF é automática. Ver Bison, JCup, yacc, etc.
Para cada classe gramatical da BNF haverá uma estrutura de dados correspondente.
Exemplo
<id,2>
<id,3>
*
+
=
<id,1>
60
<identificador, 1>, <=>, <identificador, 2>, <+>, <identificador, 3>, <*>, <number, 60>
Analisador 
Sintático
Gramática livre de contexto (BNF) caracteriza a linguagem.
A geração do parser a partir de uma BNF é automática. Ver Bison, JCup, yacc, etc.
Para cada classe gramatical da BNF haverá uma estrutura de dados correspondente.
Visitors são usados para percorrer a árvore e coletar informação.
Lexer + Parser hoje
Foo.lex
Foo.jcup
Bar.foo
JLex
JCup
FooLexer.
java
FooParser.java
FooLexer.class
FooParser.class
Análise semântica
Procura possíveis erros semânticos e guarda informações contextuais adicionais
Exemplo: verificação de tipos
A expressão 
		 x = x + 3.0
está sintaticamente correta, mas pode estar semanticamente errada, dependendo do tipo de x.
Duas etapas
Análise (front-end)
Cria representações intermediárias do programa
Verificação da presença de certos tipos de erro
Síntese (back-end)
Constrói o programa destino a partir de representações intermediárias.
Código intermediário (IR)
Representações intermediárias de código facilitam análise e transformação
Exemplos
3 endereços: cada instrução usa não mais que três operandos
SSA: cada uso de variável está associado a apenas uma definição
Pilha: operandos são acessíveis apenas a partir da pilha
Exemplo: 3 endereços
id1 = id2 + id3 * inttofloat(60)
Como esta representação de código pode ajudar?
t1 = inttofloat(60)
t2 = id3 * t1
t3 = id2 + t2
id1 = t3
Otimização de código
Realiza transformações no código com objetivo de melhorar algum aspecto relevante
tempo de execução, consumo de memória, tamanho do código executável, etc.
Pode ser específico de arquitetura ou geral
Register allocation (específico)
Constant propagation (geral)
Exemplo: Constant propagation
	
t1 = inttofloat(60)
t2 = id3 * t1
t3 = id2 + t2
id1 = t3
t2 = id3 * 60.0
id1 = id2 + t2
Geração de código
Traduz código intermediário para a linguagem-destino
	LDF R2, id3
MULF R2, R2, #60.0
LDF R1, id2
ADDF R1, R1, R2
STF id1, R1
t2 = id3 * 60.0
id1 = id2 + t2
Gerador de
 código
...
Resumo desta aula
Informação administrativa do curso
Introdução
O que são e para que servem compiladores?
Aplicações da tecnologia
Organização de um compilador
54