Compiladores: do texto ao código

Prévia do material em texto

Uninorte
1
Revisão da 
Disciplina
Compiladores
MSc. João Oliveira
1
2
O que é um compilador?
Software que traduz o texto que representa um programa para código máquina capaz de ser executado pelo computador
Contudo, um compilador pode ser muito mais do que isso...
2
3
Importância
Papel importante no desenvolvimento de aplicações complexas em tempo útil
Muitas das matérias abordadas são utilizadas por outras ferramentas:
Tradução de linguagens
Interpretação de descrições (ex.: html, postscript, latex, ficheiros word)
Procura de palavras ou frases por motores de busca
3
4
Dilema da Programação
Assembly é fastidioso, erróneo, pouco produtivo, etc.
Embora possa permitir melhor desempenho
Desenho de linguagens de alto-nível
Como implementar a linguagem?
Interpretador
Compilador
4
5
Compilador
Programa em Linguagem Máquina
Código fonte descrito numa linguagem de alto-nível (ex.: C, C++, Pascal, etc.)
Compilador
Ponto de Origem
Ponto de Destino
5
6
Ponto de Origem
Linguagem imperativa (e.g., C/C++, Java, Pascal, etc.)
Estado
Variáveis escalares
Variáveis do tipo array
Registos
Atributos de objectos (linguagens orientadas por objectos)
Computação
Expressões (aritméticas, lógicas, etc.)
Enunciados de atribuição
Fluxo de controlo (if, switch, etc.)
Procedimentos (métodos nas linguagens orientadas por objectos)
Int sum(int A[], int N) {
 Int i, sum = 0;
 For(i=0; i<N; i++) {
 sum = sum + A[i];
 }
 return sum;
}
6
7
Ponto de Destino
Linguagem máquina que descreve o programa com base no ISA (Instruction-Set Architecture) do processador
Estado
Memória
Registos (de estado, de propósito geral, etc.)
Computação
Instruções do ISA (MIPS):
Lw $3, 100($2)
Add $3, $2, $1
Bne $2, $3, label
…
Sum: Addi $t0, $0, 0
 Addi $v0, $0, 0
Loop: beq $t0, $a1, End
 Add $t1, $t0, $t0
 Add $t1, $t1, $t1
 Add $t1, $t1, $a0
 Lw $t2, 0($t1)	
 Add $v0, $v0, $t2	
 Addi $t0, $t0, 1	
 J	 Loop		
End: jr 	 $ra	
7
8
Tópicos
Estudo das etapas de um compilador
Implementação de algumas dessas etapas
Aulas práticas serão vocacionadas para implementação e realização de alguns exercícios
Construção de um compilador/interpretador simples
8
9
Conteúdo Programático
Aulas Teóricas
Introdução
Análise lexical
Análise Sintáctica
Análise Semântica
Tradução para código intermédio
Geração de código final
Optimização de código
Tópicos avançados
9
10
Viagem
Do texto que representa o programa até ao código máquina
Duas fases:
Análise
Reconhecimento dos enunciados no código fonte e armazenamento em estruturas internas
Síntese
Geração do código assembly a partir das estruturas internas
10
11
Análise Lexical
Lexical Analyzer (Scanner)
Cadeia de Tokens
Programa (cadeia de caracteres)
11
12
Análise Lexical
/* uma expressão simples */
y = b*x +c; // atribui a y
ID(y) EQ ID(b) TIMES ID(x) PLUS ID(c) SEMICOLON EOF
Lexical Analyzer (Scanner)
12
13
Análise Lexical
/* exemplo
Int sum(int A[], int N) {
 Int i, 5sum = 0;
 For(i=0; i<N; i++) {
 sum = sum + A[i];
 }
 return sum;
}
Tratamento de erros
Não é uma palavra reservada nem um identificador
Falta terminar comentário */
13
14
Análise Sintáctica
Syntax Analyzer (Parser)
Árvore sintáctica
Syntax Analyzer (Parser)
Lexical Analyzer (Scanner)
Cadeia de Tokens
Programa (cadeia de caracteres)
14
15
Análise Sintáctica
b
x
*
=
y
<stmt>
<expr>
<ident>
<ident>
<expr>
<ident>
<op>
y = b*x + c
+
<op>
c
<ident>
Árvore Sintáctica (concreta)
15
16
Análise Sintáctica
b
x
y
=
+
*
c
Árvore Sintáctica (abstracta): AST
y = b*x + c
16
17
Análise Sintáctica
Tratamento de erros
Int sum(int A[], int N)) {
 Int i, sum = 0;
 For(i=0; i<N; i++) {
 sum = sum + A[i]
 }
 retur sum;
}
}
Falta ‘;’
“retur” não é palavra reservada: dois identificadores seguidos?
Chaveta a mais
Parêntesis a mais
17
18
Análise Semântica
Semantic Analyzer
Semantic Analyzer
Syntax Analyzer (Parser)
Árvore sintáctica
Syntax Analyzer (Parser)
Lexical Analyzer (Scanner)
Cadeia de Tokens
Programa (cadeia de caracteres)
Representação intermédia
tmp1 = b*x;
tmp2 = tmp1 + c;
18
19
Análise Semântica
Tratamento de erros
boolean sum(int A[], int N) {
 Int i, sum;
 For(i=0; i<N; i++) {
 sum1 = sum + A[i];
 }
 return sum;
}
Não foi atribuído valor inicial a sum
Tipo da variável retornada não confere com a declaração do cabeçalho da função
Variável não declarada
19
20
Optimização de código
Code Optimizer
Code Optimizer
Representação intermédia optimizada
Representação intermédia
Semantic Analyzer
Semantic Analyzer
Syntax Analyzer (Parser)
Árvore sintáctica
Syntax Analyzer (Parser)
Lexical Analyzer (Scanner)
Cadeia de Tokens
Programa (cadeia de caracteres)
20
21
Geração de código assembly
Code Generator
Código Assembly
Code Generator
Code Optimizer
Code Optimizer
Representação intermédia optimizada
Representação intermédia
Semantic Analyzer
Semantic Analyzer
Syntax Analyzer (Parser)
Árvore sintáctica
Syntax Analyzer (Parser)
Lexical Analyzer (Scanner)
Cadeia de Tokens
Programa (cadeia de caracteres)
mult $t4, $t1,$t2;
Add $t4, $t4, $t3;
21
22
TPC
Apresente os resultados de cada etapa de compilação para a expressão:
y = a*x*x+b*x+c;
22
23
Análise Lexical
Compiladores
MSc. João Oliveira
23
24
Linguagens Formais
Linguagem natural
Ambígua 
problema no processamento das linguagens
dependência do contexto permite mensagens mais curtas
Linguagem (artificial) formal
Obedece a regras apresentadas rigorosamente através do recurso a formalismos apropriados
Regras garantem a não ambiguidade da linguagem
24
25
Linguagens formais e definição da linguagem
Necessidade de definir precisamente uma linguagem
Estrutura por camadas na definição da linguagem 
Começar por um conjunto de símbolos da linguagem
Estrutura lexical - identifica “palavras” na linguagem (cada palavra é uma sequência de símbolos)
Estrutura Sintáctica - identifica “frases” na linguagem (cada frase é uma sequência de palavras) 
Semântica – significado do programa (especifica que resultados deverão ser obtidos para as entradas)
25
26
Especificação Formal de Linguagens
Expressões regulares (método generativo)
Existem casos que não se podem descrever por expressões regulares
Autómatos finitos (método por reconhecimento)
Não deterministas (NFAs)
Deterministas (DFAs)
Implementam qualquer expressão regular
26
27
Especificação de Estruturas Lexicais utilizando Expressões regulares
Dado um vocabulário/alfabeto  = conjunto de símbolos
Expressões regulares são construídas com:
 - string vazia
Qualquer símbolo do alfabeto 
r1r2 – expressão regular r1 seguida de r2 (sequência): concatenação (às vezes utiliza-se o .)
r1| r2 – expressão regular r1 ou r2 (selecção)
r* - sequência iterativa ou selecção  | r | rr | …
Parêntesis para indicar precedências
Prioridade: *, ., |
27
28
Expressões regulares
Reescrever a expressão regular até se obter apenas uma sequência de letras (string)
Exemplo
(0 | 1)*”.”(0 | 1)*
(0 | 1)(0 | 1)*”.”(0 | 1)*
1(0 | 1)*”.”(0 | 1)*
1”.”(0 | 1)*
1”.”(0 | 1)(0 | 1)*
1”.”(0 | 1)
1”.”0
Regras gerais
1) r1| r2  r1
2) r1| r2  r2
3) r*  rr*
4) r*  
28
29
Não determinismo na geração
Diferente aplicação de regras pode conduzir a resultados finais diferentes
Exemplo 1
(0 | 1)*”.”(0 | 1)*
(0 | 1)(0 | 1)*”.”(0 | 1)*
1(0 | 1)*”.”(0 | 1)*
1”.”(0 | 1)*
1”.”(0 | 1)(0 | 1)*
1”.”(0 | 1)
1”.”0
Exemplo 2
(0 | 1)*”.”(0 | 1)*
(0 | 1)(0 | 1)*”.”(0 | 1)*
0(0 | 1)*”.”(0 | 1)*
0”.”(0 | 1)*
0”.”(0 | 1)(0 | 1)*
0”.”(0 | 1)
0”.”1
29
30
Linguagem gerada por expressões regulares
Conjunto de todas as strings geradas pela expressão regular é uma linguagem de expressões regulares
Em geral, uma linguagem pode ser infinita
String na linguagem é chamadade token
30
31
Linguagens e Expressões Regulares
Exemplos:
 = {0, 1, “.” }
(0 | 1)*”.”(0 | 1)* - números binários de vírgula flutuante
(00)* - strings de zeros com comprimento par
(1*01*01*)* - strings com um número par de zeros
 = {a, b, c, 0, 1, 2 }
(a | b | c)(a | b | c | 0 | 1 | 2)* - identificadores alfanuméricos
(0|1|2)* - números ternários
31
32
Expressões Regulares
Outras construções:
r+ - uma ou mais ocorrências de r: r | rr | rrr ...
Equivalente a: r.r*
r? – zero ou uma ocorrência de r: (r | )
[ ] – classes de símbolos: 
[ac] o mesmo que: (a | c)
[a-c] o mesmo que: (a | b | c)
32
33
Expressões Regulares
Especifique a linguagem de Inteiros
Especifique a linguagem de identificadores (uma letra seguida de sequências de letras e algarismos)
Enumere propriedades algébricas das expressões regulares
Dê exemplos de linguagens que não podem ser especificadas por expressões regulares
33
34
Análise Lexical
Compiladores
MSc. João Oliveira
34
35
Especificação Formal de Linguagens
Expressões regulares (método generativo)
Existem casos que não se podem descrever por expressões regulares
Autómatos finitos (método por reconhecimento)
Não deterministas (NFAs)
Deterministas (DFAs)
Implementam qualquer expressão regular
35
36
Autómatos Finitos
Conjunto de estados
1 estado de Entrada
1 ou mais estados terminais (ou estados de aceitação)
Alfabeto de símbolos:  (inclui o símbolo de string de tamanho zero: )
Transições entre estados despoletadas pela ocorrência de um determinado símbolo do alfabeto
Transições rotuladas com símbolos
36
37
Autómatos Finitos
Exemplo
Estado de início
Estado de aceitação
1
0
1
0
(0 | 1)*”.”(0 | 1)*
37
38
Aceitação de string pelo autómato
Reconhecimento através da execução do autómato
Começar com o estado de início e com o primeiro símbolo da string
Guardar estado corrente e o símbolo corrente da string
Em cada passo, fazer corresponder símbolo corrente com a transição rotulada com esse símbolo
Continuar até ao fim da string ou até que a correspondência falhe
Se o estado final é estado de aceitação, então o autómato aceita a string
Linguagem do autómato é constituída pelo conjunto de strings que ele aceita
38
39
Exemplo
11.0
Símbolo corrente
Estado de início
Estado de aceitação
1
0
1
0
39
40
Exemplo
11.0
Símbolo corrente
Estado de início
Estado de aceitação
1
0
1
0
40
41
Exemplo
11.0
Símbolo corrente
Estado de início
Estado de aceitação
1
0
1
0
41
42
Exemplo
11.0
Símbolo corrente
Estado de início
Estado de aceitação
1
0
1
0
42
43
Exemplo
11.0
Símbolo corrente
Estado de início
Estado de aceitação
1
0
1
0
43
44
Exemplo
11.0
Símbolo corrente
String aceite!
Estado de início
Estado de aceitação
1
0
1
0
44
45
Autómatos Finitos
NFA: Autómato Finito não Determinista
De um determinado estado, a mesma ocorrência pode conduzir a estados distintos
DFA
O mesmo que NFA com a seguinte ressalva:
De um determinado estado, a ocorrência de um símbolo não pode ter mais do que um laço, e por isso não pode levar a estados diferentes.
45
46
NFA vs DFA
DFA
Sem transições 
No máximo uma transição de cada estado para cada símbolo
NFA – nenhuma destas restrições
a
a
a
b
OK
NOT
OK
46
47
Autómatos Finitos
Autómatos Finitos Deterministas (DFAs)
Implementações mais rápidas do que para os NFAs, mas
Maior complexidade do autómato
47
48
Generativo vs Reconhecimento
Expressões regulares são um mecanismo para gerar as Strings da linguagem
Autómatos são um mecanismo para reconhecer se uma String específica pertence à linguagem
Abordagem standard
Usar expressões regulares aquando da definição da linguagem
Tradução automática para autómatos para a implementação da analisador lexical
48