Revisão Compiladores – AP1
Prof. Alexandre Monteiro
Baseado em material cedido pelo Prof. Euclides Arcoverde
Recife
‹#›
Contatos

Prof. Guilherme Alexandre Monteiro Reinaldo

Apelido: Alexandre Cordel

E-mail/gtalk: [email protected]
[email protected]

Site: http://www.alexandrecordel.com.br/fbv

Celular: (81) 9801-1878
Objetivo

O principal objetivo é responder à seguinte pergunta:
•Como criar uma linguagem computacional?

Para responder a pergunta, estudaremos:
•Como especificar uma linguagem
•Como construir um compilador para ela
3
História das Linguagens
História das Linguagens

Começaram a surgir outras linguagens mais
elaboradas
• Fortran (1957)
• LISP (1959)
• COBOL (1960)
• BASIC (1964)
• C (1972)
• etc.
5
Linguagens de Alto Nível
Linguagens de Alto Nível

O nome “alto nível” tem o sentido de “alto
nível de abstração”, pois essas linguagens
abstraem detalhes operacionais pouco
relevantes
• Assim, o programador pode (tenta) focar só no
algoritmo

Veremos agora dois exemplos para comparar
as linguagens de nível alto e baixo
7
Exemplo em Baixo Nível

Programa Hello World em assembly x86
DOSSEG
.MODEL SMALL
.DATA
Msg db "Hello World.",13,10,"$"
.CODE
Start:
mov AX, @DATA
mov DS, AX
lea DX, Msg
mov AH, 9
int 21h
mov ah, 4ch
int 21h
END Start
8
Exemplo em Alto Nível

Programa Hello World em C
#include <stdio.h>
int main() {
printf(“Hello World”);
return 0;
}
9
Linguagens de Baixo Nível

Características gerais
• Dependentes de arquitetura
• Oferecem instruções primitivas simples (operações
sobre o hardware)
• Programas extensos e pouco legíveis
• Visam oferecer mais controle sobre o hardware
10
Linguagens de Alto Nível

Características gerais
• Especificadas independentemente de qualquer
arquitetura
• Oferecem comandos mais intuitivos
- Dizem mais “o que” deve ser feito do que “como”
deve ser feito
• Mais fácil de programar e de ler códigos prontos
• Restringem o uso do hardware para evitar bugs
- Controle da alocação de memória em Java
11
Introdução a Compiladores
Compilação x Interpretação

Compilação
código
fonte

compilação
código
de
máquina
execução
resultados
Interpretação
código
fonte
interpretação
resultados
13
O que é um Compilador?

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.
Programa
Fonte
Compilador
Programa
Objeto
14
O que é um Compilador?

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
• 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
15
O que é um Compilador?




A fase de análise normalmente se subdivide em
análise léxica, análise sintática e análise semântica
É 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
16
O que é um Compilador?



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
17
O que é um Compilador?

Um dos modelos possíveis para a construção de
compiladores faz a separação total entre o frontend, encarregado da fase de análise, e o back-end,
encarregado da geração de código, de forma que:
• O front-end e back-end se comunicam apenas através de
uma representação intermediária
• O front-end depende exclusivamente da linguagem fonte
• O back-end depende exclusivamente da linguagem objeto
18
Etapas da Compilação
Análise Léxica
Análise Sintática
Front-End
(Análise)
Analise Semântica
Geração de Código
Intermediário
Geração de Código
Final
Back-End
(Síntese)
19
O que é um Compilador?


Um compilador típico consiste de algumas
fases onde cada uma passa sua saída para as
fases seguintes
As principais fases são:
•análise léxica (ou scanner)
•análise sintática (ou parser)
•análise semântica
•otimização
•gerador de código
•otimização (novamente!)
20
Fases da Compilação
Programa Fonte
Analisador Léxico
Analisador Sintático e
Semântico
Tabela de
Símbolos
Gerador de Código
Intermediário
Manipulador
de erros
Otimizador de Código
Gerador de código
Programa Objeto
21
Análise Léxica

Também chamada de scanner

Agrupa caracteres em símbolos (ou tokens)
• Token: <nome-token, valor-atributo>

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, etc.



Expressões regulares usadas para reconhecimento
Scanner é implementado como uma MEF (Método dos
Elementos Finitos)
22
Lex/Flex (J) são ferramentas para gerar scanners
Análise Léxica

Por exemplo, os caracteres na instrução de
atribuição
position = initial + rate * 60

seriam agrupados nos seguintes tokens:
• O identificador position
• O símbolo de atribuição =
• O identificador initial
• O símbolo de adição +
• O identificador rate
• O símbolo de multiplicação *
• O número 60
<id, 1> <=> <id, 2> <+> <id, 3> <*> <60>
23
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 de árvore sintática do programa
Gramática livre de contexto é usada para definir a
estrutura do programa reconhecida por um parser
Yacc/Bison (J) são ferramentas para gerar parsers
24
Análise Sintática

Regras sintáticas (1)
• Qualquer identificador é uma expressão
• Qualquer número é uma expressão
• Se expressão1 e expressão2 são expressões, então
também são expressões
- expressão1 + expressão2
- expressão1 * expressão2
- ( expressão1 )
25
Análise Sintática

Regras sintáticas (2)
• Se identificador1 é um identificador e expressão2 é
uma expressão, então
identificador1 = expressão2
é um comando (statement)
• Se expressão1 é uma expressão e statement2 é um
comando (statement), então
while ( expressão1 ) { statement2 }
if ( expressão1 ) { statement2 }
são comandos (statements)
26
Análise Sintática
position = initial + rate * 60
comando de atribuição
identificador
position
=
expressão
identificador
initial
expressão
+
expressão
expressão *
expressão
identificador
número
rate
60
27
Gerador de Código Intermediário


Usa as estruturas produzidas pelo analisador
sintático e verificadas pelo analisador
semântico para criar uma sequência de
instruções simples (código intermediário)
Está entre a linguagem de alto nível e a
linguagem de baixo nível
28
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:
29
Gerador de Código Intermediário
30
Gerador de Código Intermediário

O comando de atribuição
x := a + b * c

Gera o código
Load
b
Mult
c
{ t1 := b * c }
Store t1
Load
a
Add
t1
{ t2 := a + t1 }
Store t2
Load
t2
{ x := t2 }
Store x
31
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
32
Otimizador de Código
Otimizador por sub-expressões comuns
33
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.

Projetar um gerador de código que produza
programas objeto eficientes é uma das tarefas
mais difíceis no projeto de um compilador
34
Gerador de Código

Várias considerações têm que ser feitas:
• Há vários tipos de instruções correspondendo a
vários tipos de dados e a vários modos de
endereçamento
• Há instruções de soma específicas, por exemplo
para incrementar/decrementar de 1
• Algumas somas não foram especificadas
explicitamente
- Cálculo de endereço de posições em vetores
• Incremento/decremento registrador de topo pilha
• Local onde armazenar variáveis
• Alocação de registradores
35
Gerador de Código
temp1 = id3 * 60.0
id1
= id2 + temp1
MOVF
MULF
MOVF
ADDF
MOVF
id3, R2
#60.0, R2
id2, R1
R2, R1
R1, id1
36
Tabela de Símbolos

É uma estrutura de dados usada para
guardar informações a respeito de todos
os nomes usados pelo programa e
registrar informações importantes
associadas a cada um, tais como seu tipo
(inteiro, real, etc.), tamanho, escopo,
etc.
37
Manipulador de Erros


É ativado sempre que for detectado um erro
no programa fonte
Deve avisar o programador da ocorrência do
erro emitindo uma mensagem, e ajustar-se
novamente à informação sendo passada de
fase a fase de modo a poder completar o
processo de compilação
• Mesmo que não seja mais possível gerar código
objeto, a análise léxica e sintática deve prosseguir
até o fim
38
Bibliografia

AHO, A., LAM, M. S., SETHI, R., ULLMAN, J. D.,
Compiladores: princípios, técnicas e ferramentas. Ed.
Addison Wesley. 2a Edição, 2008 (Capítulo 1)
39
Adiantando...


Lexema: sequência de caracteres com
significado interligado
Token: classificação dada ao lexema
• Geralmente retornado junto com o próprio lexema
ou outro atributo, como um ponteiro

Padrão: é uma descrição da forma que os
lexemas de um token podem tomar.
•Ex. sequência de caracteres que
formam palavra-chave como um token.
40
Exemplos
41
Especificando Tokens


Geralmente são especificados com expressões regulares
Cada token é associado a uma expressão regular que
representa seus lexemas válidos
•Padrão que representa várias palavras
(dizemos que as palavras “casam” com o
padrão)
42
Especificando Tokens

Expressões Regulares
• Formalismo utilizado para definir o conjunto de aceitação de
uma linguagem
• Principais operadores utilizados pelas ERs
Expressão
Reconhece
ε
A cadeia de caractedes vazia “”
“str”
A string “str”
A|B
Todas as cadeias reconhecidas por A ou B
A.B
Cadeias formadas pela concatenação das
cadeias reconhecidas por A e B
A+
Reconhece cadeias formadas pela concatenação
de um número finito de cadeias reconhecidas
43
por A
Especificando Tokens

Operadores derivados
Expressão
Equivale a
(A)
Agrupamento de operadores
A*
A+ | ε
A?
A|ε
[A-Z]
A | B | ... | Y | Z
A{N}
A . A . A ... } N vezes
A{M,N}
A . A . A ... } entre M e N vezes
AB
A.B
abc
String “abc”
44

Especificando Tokens
Exercícios
•Defina expressões para expressar:
-
Número IP: \d{3}.\d{3} .\d{3} .\d{3}
Números naturais (e inteiros): \d{n} ou [0-9]{n}
Números de telefone (com DDD opcional): \([0-9]{2}\).[0-9]{4}. [0-9]{4}
Horas: [012]\d:[0-5]\d
E-mails: [a-zA-Z0-9\._-]@[A-Za-z]+\\.[A-Za-z]+
Placa de Carro: [A-Z]{3}-\d{4}
CEP: \d{5}-\d{3} ou \d\d\d\d\d
URLs:
- Com http - (http|https)://([\w-]+\.)+[\w-]+(/[\w- ./?%&=]*)?
- Sem http - ([\w-]+\.)+[\w-]+(/[\w- ./?%&=]*)?
45
Análise Sintática

Alguns autores consideram que a análise sintática envolve
tudo que diz respeito à verificação do formato do código
fonte
•Inclui a análise léxica como subfase
•Visão mais coerente, porém o livro texto
que usamos tem outra visão...
46
Análise Sintática

Entenderemos análise sintática como sendo
apenas a segunda fase dessa verificação de
formato:
• “É a fase que analisa os tokens para descobrir a
estrutura gramatical do código fonte”
• Também chamada “Reconhecimento” (Parsing)
• Porém, um nome melhor seria “Análise Gramatical”
47
Gramáticas


São usadas para organizar os tokens em “frases” de sentido
lógico
Definem regras de formação recursivas
expressão → CTE_INT
| ID
| expressão + expressão
48
Gramáticas

As gramáticas livres de contexto possuem quatro
elementos:
•Símbolos terminais
•Símbolos não-terminais
•Símbolo inicial
•Produções! ou Regras de Produção!
49
Gramáticas

Elementos das gramáticas livres de contexto:
•Símbolos terminais:
- Símbolos assumidos como atômicos, indivisíveis
- Em compiladores, são os tokens (int, +, -, /, identificador, valores
literais, etc)
•Símbolos não-terminais:
- Usados para organizar os tokens em “frases”
- Representam elementos abstratos do programa (expressões, termos,
etc)
50
Gramáticas

Elementos das gramáticas livres de contexto:
• Símbolo inicial:
- Não-terminal a partir do qual são derivadas “cadeias” de
símbolos terminais
- Geralmente é um não-terminal chamado programa
• Produções:
- São as regras de formação
- Definem as “frases” de terminais válidas na linguagem
51
Derivação

Seja a gramática BNF anterior
• Derivar a cadeia “i+i+x”
<expressao>
 <termo> + <expressao>
 i
+ <expressao>
 i
+ <termo> + <expressao>
 i
+ i
+ <expressao>
 i
+ i
+ <termo>
 i
+ i
+ x
• Consideremos que esta é uma derivação mais à
esquerda
52
Derivação

Seja a gramática BNF mostrada antes
•Agora a Derivação mais à direita da cadeia
“i+i+x”
<expressao>
 <termo> + <expressao>
 <termo> + <termo> + <expressao>
 <termo> + <termo> + <termo>
 <termo> + <termo> + x
 <termo> + i
+ x
 i
+ i
+ x
53
Derivação

O processo de derivação consiste em substituir
cada ocorrência de um não-terminal pelo lado
direito (corpo) de alguma de suas produções
• Derivação mais à esquerda: substituir sempre o nãoterminal mais à esquerda
• Derivação mais à direita: análogo

A derivação pára quando sobrarem apenas
terminais e o resultado é a cadeia
54
Árvore de Derivação

A árvore dos exemplos anteriores
expressao
termo
i
+
expressao
termo
+
expressao
i
termo
a cadeia gerada pode ser percebida nas
folhas, analisando-as da esquerda para a
direita
55
x
Árvore de Derivação

A mesma árvore reorganizada
expressao
termo
expressao
termo
expressao
termo
i
+
i
+
a seqüência de terminais (cadeia) gerada
x
56
Gramáticas Ambíguas


Uma gramática é dita ambígua se ela puder gerar duas
árvores de derivação distintas para uma mesma cadeia
Veremos uma gramática equivalente à anterior, porém
ambígua...
57
Gramáticas Ambíguas

Exemplo
<expressao> ::= <expressao> "+" <expressao>
| "x"
| "i"
•Mostrar duas árvores de derivação para
“i+i+x”
58
Gramáticas Ambíguas

Gramáticas ambíguas são, em geral, inadequadas para uso
em compiladores
•Dificultam a construção do analisador
sintático

Em alguns casos, são usadas gramáticas ambíguas junto com
restrições adicionais
•Exemplo: precedência e associatividade
59
Tratando Ambiguidades

A seguinte de definição de comando apresenta ambigüidade
cmd ::= if ( expr ) cmd else cmd
| if ( expr ) cmd
| outro
expr ::= x

Exemplo: “if (x) if (x) outro else outro”
•A qual “if” está ligado o “else”?
60
Tratando Ambiguidades

Solução
cmd ::= matched-cmd
| open-cmd
matched-cmd ::=
| if ( expr ) matched-cmd else matched-cmd
| outro
open-cmd ::=
| if ( expr ) cmd
| if ( expr ) matched-cmd else open-cmd
61
Análise de Descida Recursiva


É uma análise sintática top-down ou
descendente
É um parser LL(1)
• Left-to-right – a ordem de leitura dos tokens é da
esquerda para a direita
• Leftmost derivation – segue a ordem típica de uma
derivação mais à esquerda
• Só olha 1 token por vez
62
Análise de Descida Recursiva


É útil para construir parsers manualmente, por ser
fácil de implementar
Princípio Básico
• Se eu quero produzir um não-terminal e sei qual o terminal
corrente eu devo saber que regra deve ser aplicada.

Porém, requer uma gramática muito bem ajustada
• Veremos os ajustes necessários

Mostraremos como usar a técnica, assumindo que o
parser final será uma classe Java
63
Exemplo de Reconhecedor

Gramática:
Terminais = {a,b,c}
Não-terminais = {S, X}
Produções = {
SaXb
SbXa
Sc
a
b
c
S
aXb
bXa
c
X
a
bX
Error
XbX
Xa
}
Não-terminal inicial = S
64
Conjunto FIRST

FIRST(α)
•Aplicado a cadeias α quaisquer

É o conjunto de terminais que podem iniciar a cadeia α
dada
•Se a cadeia derivar vazio, também inclui ε

Como calcular?
65
Conjunto FIRST

Se α for a cadeia vazia (α = ε)
•FIRST(ε) = { ε }

Se for um terminal a qualquer
•FIRST(a) = { a }

Se for um não-terminal N com as produções N → α | β
•FIRST(N) = FIRST(α)  FIRST(β)
66
Conjunto FIRST

Se for uma cadeia de símbolos α = X1X2...Xk
• Depende de X1

Se X1 não pode gerar vazio
• FIRST (X1X2...Xk) = FIRST(X1)

Se X1 pode gerar vazio
• FIRST (X1X2...Xk) = FIRST(X1)  FIRST(X2...Xk)
• Calcula para X1 e continua o cálculo recursivamente
para o restante da cadeia
67
Múltiplas Produções

Calculando o FIRST para as duas produções de comando ...
•comando ::= atribuição | declaração
FIRST(atribuição) = FIRST(IDENTIFICADOR = <expressao> ;)
= { IDENTIFICADOR }
FIRST(declaração) = FIRST(tipo IDENTIFICADOR ;)
= FIRST(tipo)
= { int , char, float }
68
Eliminação de Fatoração

Direta:

Xab
XYc
Yad
Xabc
Xade

Sem fatoração:
XaY
Ybc
Yde
Indireta

Elimina-se a indireção:
Xab
Xadc
Yad

Sem fatoração:
XaZ
Yad
Zb
Zdc
69