Compiladores - Resumão para P1

Aula I

Compilar

Traduzir algo escrito em uma determinada linguagem para uma linguagem de máquina.

Traduz um código fonte (alto nível) para um código objeto binário (baixo nível).

Código fonte -> compilador -> código executável

História

no inicio programas eram escritos em ling de maq

o primeiro compilador foi criado por Grace Hooper em 1952, A-0 System (Univac I)

compilador completo em 1957, FORTAN - John Backus

Componentes

• Análise léxica
• Análise sintática
• Análise semântica
• Geração e otimização de código

Analise léxica

Vai executar os autômatos.

Identificar os elementos do textos, caractere por caractere.

Verificar se a palavra é reservada, constante, variável.

Ignora comentários.

Analise sintática

Identifica as construções válidas da linguagem com base nos elementos léxicos.

Analise semântica

Garante que as construções identificadas façam sentido de acordo com as regras da linguagem.

Verifica se as variáveis usadas foram devidamente declaradas

Gerador de código

Criação de código de baixo nível que reflete os comandos do código fonte.

Otimização dos comandos gerados para uma determinada arquitetura.

Exemplo

soma := soma + 35

Análise léxica

(valor) (classe)

SOMA identificador

:= comando de atribuição

SOMA identificador

• operador numérico de adição

35 constante numérica inteira

Análise sintática

Árvore de execução (desenho).

Caso a análise léxica esteja certa, constrói a árvore e código está certo.

Distribui as expressões, sequencias e operações

Em linguagens formais e autômatos → processo de derivação na linguagem → procurava derivar.

Criava a árvore de derivação → aqui é árvore sintática.

Linguagens formais não seguiam nenhum algoritmo específico → tentava e erro.

Análise semântica

SOMA foi declarada?

SOMA é variável?

Qual o escopo de SOMA?

Qual o tipo de SOMA?

Coloca informações adicionais na árvore

Geração de código

Movimentação de registradores

Código dentro do processador (assembly).

MOV AX, [soma]
ADD AX, 35
MOV [soma], AX

Componentes em detalhes

Compiladores vs Interpretadores

Existência das três analises (léxica, sintática e semântica).

Compilador faz trabalho rápido.

Interpretadores geram código objeto durante a execução.

Interpretadores são mais lentos, porem alterações no código são mais rápidas de serem realizadas.

Bytecode

Presente no Java.

Ao invés de gerar comandos em linguagens de maquina, os comandos são armazenados na forma de códigos binários.

Este código será então interpretado por uma maquina virtual.

Compila até uma parte, depois manda para a máquina virtual.

Bom para rodar em arquitetura diferentes (um código Java feito no Linux pode rodar no Linux, Windows e Mac sem problemas).

Alula 2

O que é gramática?

Gramática é uma ferramenta para descrever uma linguagem.
É a base do analisador léxico e sintático.

Onde autômatos finitos são utilizados?

Autômatos finitos são utilizados na análise lexicográfica para reconhecimento dos programas e na definição de suas estrutras.

O que é um compilador?

É um tradutor entre duas linguagens (L1 e L2) de programação.
Neste caso L1 representa o código fonte e L2 o código de máquina.

Relembrando

Alfabeto: conjunto finito não vazio de símbolos.
Palavra: sequência finita de símbolos do alfabeto.
Comprimento da palavra: número de símbolos que compõem a palavra.
Concatenação ou produto de palavras.

Uma linguagem sobre um alfabeto Σ é um subconjunto de Σ*.

Qual é a regra geral da gramática?

Gramática G=(V,T,P,S), onde:
– V: conjunto de símbolos não terminais
– T: conjunto de símbolos disjuntos de V
– P: conjunto de regras de produção
– S: elemento de V denominado inicial

Exemplo 1

Exemplo 2

Obs: fere regra de produção - símbolos não terminais não podem estar nos dois lados (EOE).

Detecção de erros

Dinâmicos

São erros originados em tempo de execução Ex: input não esperado do usuárui

Estáticos

São erros encontrados durante a compilação

• identificadores ma contruidos (analise lexica).
  Verifica se reconhece os elementos.
  Ex: na seguiu as regras de variaveis

• Desrespeito a gramatica - “syntaxa error” (analise sintatica).
• Desrespeita a política de tipos, visibilidade de identificadores, passagem de parâmetros, etc (análisesemântica).

Qual a função da análise léxica?

Sua função é ler o arquivo fonte e “etiquetar” os elementos significativos.
Estes elementos significativos são chamados de tokens

O que são tokens?

Tokens são os significados dos padrões de caracteres em um código fonte.

O processo de varredura é um caso especial de casamento de padrões.
Métodos utilizados: Expressão regular (ER) e autômatos finitos.
A velocidade do processamento é um ponto crítico.

O que é lexema?

Lexema é a sequência de caracteres na fonte que se associa a um padrão e então a um token - instância do token.

Simplificando

Lexema -> variavel / operação encontrado no codigo (if, sum, …)
Token -> como é representada |(numero, literal, …)

A palavra léxico faz referencia ao conjunto teoricamente infinito de todas as palavras já realizadas e potenciais de uma língua
Em linguagem de programação, palavras são objetos como nomes de variáveis, números, keywords.
Estas palavras são chamadas de tokens.

Entenda VALOR como Lexema e CLASSE como Token.

Input: letras individuais das palavras.
Output: strings divididas em tokens.
Descarta espaços em branco (espaços, quebra de linha e etc) e comentários.

Qual o objetivo da análise léxica?

Facilitar o trabalho do analisador sintático.

Por que separar o analisador léxico do analisador sintático?

Pois é mais eficiente, modular e tradicional.

O que faz um gerador léxico?

Transforma especificações de tokens e espaços em branco (em linguagem humana compreensível) em programas eficientes.

Especificações léxicas são geralmente escritas usando expressões regulares.
ER: notação algébrica para descrever um conjunto de caracteres.
Assim, os gerados léxicos são descritos como autômatos finitos.

Análise léxica - ER

Estrutura léxica - MiniJava

Análise léxica - ER (continuação)

Exercício 1

Respostas

a) 0*
42

b) 0∗
([0−9] |
[1−3][0−9] |
4[0−1] |
4[3−9] |
[5−9][0−9] |
[1−9][0−9][0−9]+)

c) 0∗ (4[3−9] |
[5−9][0−9] |
[1−9][0−9][0−9]+)

Qual é o melhor autômato para reconhecer as palavras?

É p autômato finito deterministico com o minimo de estados.

Vamos estudar 3 etapas

• ER para Autômato Finito Não Deterministico (AFN).
• Autômato Finito Não Deterministico (AFN) para Autômato Finito Deterministico (AFD).
• Minimização de estado do Deterministico (AFD).

Análise léxica - ER para AFN

Utilização de fragmentos.
Colar os diversos fragmentos para construir o autômato completo.

Exercício 1

(a|b)*ac
Qual é o AFN?

Aula III

Exercício II

Análise léxica - AFN para AFD

Simula todos os caminhos de um AFN simultaneamente.
Criação de diversos “estados” de operação.
Cada estado se tornará um único AFD.

Epsilon-states

Sempre que estivermos em um estado AFN, nós sempre poderemos ler um símbolo vazio.
Assim, nos podemos usar uma transição vazia sem ler nenhum símbolo.

algoritmo

Exemplo 1

Passar o AFN do exercício 1 anterior para AFD.

(a	b)*ac -> AFD.

E = {a,b,c}
s’0 = {1,2,5,6,7}
s’1 = {3,8,1,2,5,6,7}
s’2 = {8,1,2,5,6,7}
s’3 = {4}

(s’0,a) = {3,8} U {1,2,5,6,7}
s’1 = {3,8,1,2,5,6,7}

(s’0,b) = {8} U {1,2,5,6,7}
s’2 = {8,1,2,5,6,7}

(s’0,c) = {∅} U {∅}
∅

(s’1,a) = {3,8} U {1,2,5,6,7}
(s’1,a) = {3,8,1,2,5,6,7} = s’1

(s’1,b) = {8} U {1,2,5,6,7}
(s’1,b) = {8,1,2,5,6,7} = s’2

(s’1,c) = {4} U {∅}
s’3 = {4} -> como possui 4, s’3 é um estado final.

(s’2,a) = {3,8} U {1,2,5,6,7}
(s’2,a) = {3,8,1,2,5,6,7} = s’1

(s’2,b) = {8} U {1,2,5,6,7}
(s’2,b) = {8,1,2,5,6,7} = s’2

(s’2,c) = {∅} U {∅}
∅

(s’3,a) = {∅} U {∅}
∅

(s’3,b) = {∅} U {∅}
∅

(s’3,c) = {∅} U {∅}
∅

Meu desenho:

CORREÇÃO DO PROFESSOR

AFN e AFD

Aula IV

Exercíco 1

E = {a,b}
s’0 = {1,2,3,4,5}
s’1 = {1,6,2,3,4,5}
s’2 = {6}
s’3 = {7,1,6,2,3,4,5}
s’4 = {7}
s’5 = {8,7,1,6,2,3,4,5}
s’6 = {8}

---

(s’0,a) = {1,6} U {2,3,4,5}
s’1 = {1,6,2,3,4,5}
entenda como:
s’0 percorrendo ‘a’ da {1,6}
{1,6} percorrendo vazio da {2,3,4,5}
Depois união de todos
{1,6,2,3,4,5}.

(s’0,b) = {6} U {∅}
s’2 = {6}
entenda como:
s’0 percorrendo ‘b’ da {6}
{6} percorrendo vazio da {∅}
Depois união de todos
{6}.

(s’1,a) = {7,1,6} U {2,3,4,5}
s’3 = {7,1,6,2,3,4,5}
entenda como:
s’1 percorrendo ‘a’ da {7,1,6}
{7,1,6} percorrendo vazio da {2,3,4,5}
Depois união de todos
{7,1,6,2,3,4,5}.

(s’1,b) = {6} U {∅}
s’1,b = {6} = s’2
entenda como:
s’1 percorrendo ‘b’ da {6}
{6} percorrendo vazio da {∅}
Depois união de todos
{6}.

(s’2,a) = {7} U {∅}
s’4 = {7}

(s’2,b) = {∅} U {∅}
∅

(s’3,a) = {8,7,1,6} U {2,3,4,5}
s’5 = {8,7,1,6,2,3,4,5} -> como possui 8 e 8 é estado final no AFN, s’5 é um estado final.

(s’3,b) = {6} U {∅}
s’3,b = {6} = s’2

(s’4,a) = {8} U {∅}
s’6 = {8} -> como possui 8, s’6 é um estado final.

(s’4,b) = {∅} U {∅}
∅

(s’5,a) = {8,7,1,6} U {2,3,4,5}
s’5,a = {8,7,1,6,2,3,4,5} = s’5

(s’5,b) = {6} U {∅}
s’5,b = {6} = s’2

---

Meu desenho:

---

CORREÇÃO DO PROFESSOR

Exercíco 2

q0 percorrendo 0 vai para q0 (loop).
q0 percorrendo 1 vai para q1.

q1 percorrendo 1 vai para q1 (loop).
q1 percorrendo 0 vai para q1 e q2 (criamos um estado q1q2).

Obs: Podemos fazer operação de união como no slide:
q1 percorre 0 -> {q1,q2}
q2 percorre 0 -> {q2}
União dos dois
{q1,q2}

q2 percorrendo 0 vai para q2 - para não criar novo estado deixamos q1q2 (loop).
q2 percorrendo 1 vai para q1q2 (loop)

q1 percorre 1 -> {q1}
q2 percorre 1 -> {q1,q2}
União dos dois
{q1,q2}

Exercíco 3

q0 percorrendo 0 vai para q0 e q1 (criamos um estado q0q1).
q0 percorrendo 1 vai para q1.

q0q1 percorrendo 0 vai para q0q1 (loop).

q0 percorre 0 -> {q0,q1}
q1 percorre 0 -> {∅}
União dos dois
{q0,q1}

q0q1 percorrendo 1 vai para q0q1 (loop).

q0 percorre 1 -> {q1}
q1 percorre 1 -> {q1,q0}
União dos dois
{q0,q1}

q1 percorrendo 1 vai para q0 (podemos aproveitar o estado q0q1 já que o q1 faz parte do loop).

Aula V

Último exercício de AFN para AFD.

ER = a(a

bc)*

AFN =

AFD =

AFD: E = {a,b,c}
s’0 = {1}
s’1 = {2,3,4,5,8}
s’2 = {7,2,3,4,5,8}
s’3 = {6}

s’0 = {1} U {1}
s’0 = {1}

(s’0,a) = {2} U {3,4,5,8}
s’1 = {2,3,4,5,8} -> tem 8, estado final

(s’0,b) = {∅} U {∅}
∅

(s’0,c) = {∅} U {∅}
∅

(s’1,a) = {7} U {2,3,4,5,8}
s’2 = {7,2,3,4,5,8} -> tem 8, estado final

(s’1,b) = {6} U {∅}
s’3 = {6}

(s’1,c) = {∅} U {∅}
∅

(s’2,a) = {7} U {2,3,4,5,8}
(s’2,a) = {7,2,3,4,5,8} = s’2

(s’2,b) = {6} U {∅}
(s’2,b) = {6} = s’3

(s’2,c) = {∅} U {∅}
∅

(s’3,a) = {∅} U {∅}
∅

(s’3,b) = {∅} U {∅}
∅

(s’3,c) = {7} U {2,3,4,5,8}
(s’3,c) = {7,2,3,4,5,8} = s’2

Vídeo Auxiliar: Assista

Flex/Lex

É uma linaguagem de analisador léxico.

Existem 3 maneiras de construir um analisador léxico:

• Utilizar um gerador automático de analisadores léxicos.
• Escrever um analisador léxico utilizando uma linguagem de programação convencional.
• Escrever um analisador léxico utilizando uma linguagem de montagem.

Linguagem Lex

Gerador automático de analisadores léxicos.

Também conhecida como Flex em uma implementação mais recente.

Função:

• Diferenciar os diversos tipos de tokens através de ER
• Não verifica se todos as partes estão presentes
• Decidir como sub-dividir os tokens

Estrutura de um programa Lex:

[definições]
%%
(expressão_regular [ação])*
[%%
funções auxiliares em C]

Exemplos

Tente fazer

Resposta

Exercícios

Exercício 1

Exercício 2

Exercício 3

Exercíco 4

Exercíco 5

Exercíco 6

Exemplos de Análise Léxica

Exercícios

Exercício 1

Código:

while indice < 10 do
 indice:= total + indice;

Sequência de tokens:
<while,> <id,7> «,> <numero,10> <do,> <id,7> <:=,> <id,12> <+,> <id,7> <;, >

Exercício 2

Código:

position = initial + rate * 60

Sequência de tokens:
<id, 1> <=, > <id, 2> <+, > <id, 3> <*, > <numero, 60>

Exercício 3

Código:

a[index] = 4 + 2

Sequência de tokens:
<id, 1> <[,> <id, 2> <],> <=,> <numero, 4> <+,> <numero, 2>

Exercício 4

Código:

position = initial + rate * 60

Sequência de tokens:
<id, 1> <=, > <id, 2> <+, > <id, 3> <*, > <numero, 60>

Extra

Código:

const a[book] = 5;
contador = 11;
while contador > 1 do {
	contador =- 1;
	if (contador <= 5) {
		a[contador] = contador + 2;
		print("numero inferior");
	}
}
contador *= 60;

Sequência de tokens:
<const, > <id, 1> <[, > <id, 2} <], > <=, > <numero, 5> <;, >
<id, 3> <=, > <numero, 11> <;, >
<while, > <id, 3> <>, > <numero, 1> <> <do, > <{, >
<id, 3> <=-, > <numero, 1> <;, >
<if, > <(, > <id, 1> «=,> <numero, 5> <), > <{, >
<id, 1> <[, > <id, 1> <], > <=, > <id, 3> <+, > <numero, 2> <;, >
<print, > <(, > <literal, “numero inferior”> <), > <;, >
<}, >
<}, >
<id, 3> <*=, > <numero, 60> <;, >