Aula 02 - COMPILADORES - Estácio

Prévia do material em texto

COMPILADORES
AULA 02
COMPILADORES
Aula 02
COMPILADORES
AULA 02
Apresentação da Disciplina
Professor: Marcus Pantoja da Silva
E-mail: marcus.pantoja@estacio.br
mailto:marcus.pantoja@estacio.br
COMPILADORES
AULA 02
Na aula passada ...
Analisador 
Léxico
(scanner)
Analisador 
sintático 
(parser)
Programa 
fonte
token
GetToken()
Para análise 
sintática
Tabela de Símbolos
(identificadores e 
constantes)
COMPILADORES
AULA 02
Análise Léxica (AL)
• O objetivo do Analisador Léxico é analisar a entrada dada
(programa fonte) e dividi-la em sequencias considerando
os tokens da linguagem, definidos por expressões
regulares.
• Cada token é normalmente formado por seu tipo (se é um
operador lógico, um identificador, um número inteiro, etc.)
e pelo seu valor e outros atributos. Este valor vai depender
do tipo de token e normalmente corresponde à sequência
de caracteres realmente lida da entrada.
COMPILADORES
AULA 02
Análise Léxica (AL)
• O AL fornece tokens para o analisador sintático (AS),
desconsiderando espaços, comentários e quebra de linha
Símbolos simples, palavras
reservadas, tipos de dados,
constantes...
COMPILADORES
AULA 02
Análise Léxica (AL) tokens, padrões e lexemas
Token: dupla formada pelo nome e valor de atributo
• Nome do token: símbolo abstrato que representa um tipo
de unidade léxica.
• Também é um símbolo de entrada para o analisador
sintático
Padrões: Descrição da forma que os lexemas de um token podem
assumir:
• Palavra-chave como token
• Casamento de sequências de caracteres
Lexemas: Sequência de caracteres no programa-fonte que casa
com o padrão de um token
• Identificado como instância desse token
COMPILADORES
AULA 02
Regras de tokens
1. Um token para cada palavra-chave. O padrão para palavra-
chave é ela mesma;
2. Tokens para operadores, seja individualmente ou em classes;
3. Um token para todos os identificadores;
4. Um ou mais tokens representando constantes;
5. Tokens para cada símbolo de pontuação.
COMPILADORES
AULA 02
Atributos de tokens
• É possível mais de um lexema casar com o padrão;
Ex.: Token number casa com 0 e 1;
• O analisador léxico pode passar para o sintático o nome do
token e um valor de atributo que descreve o lexema;
• O nome do token influencia as decisões da análise
sintática;
• O valor do token influencia a tradução dos tokens;
• O valor de atributo para um identificador aponta para sua
entrada na tabela de símbolos..
COMPILADORES
AULA 02
Exemplo para FORTRAN
COMPILADORES
AULA 02
Análise Léxica (AL)
• Analisador léxico: lê o fluxo de caracteres e agrupa em
sequências significativas;
• As sequências significativas são chamadas lexemas;
• Para cada lexema, o analisador léxico produz como saída
um token;
<nome_token, valor_atributo>
• O token é enviado para a etapa seguinte, a análise
sintática.
COMPILADORES
AULA 02
Análise Léxica (AL)
position = initial + rate*60
position Mapeado para o token <id,1>
id Símbolo abstrato que significa identificador
1 Entrada na tabela de símbolos onde está o position
= Mapeado para o token <=>. Por não exigir um valor de atributo,
omitimos o segundo componente
initial Mapeado para o token <id, 2>;
+ Mapeado para o token <+>;
rate Mapeado para o token <id, 3>;
Mapeado para o token <∗>;
60 Mapeado para o token <60>
COMPILADORES
AULA 02
Análise Léxica (AL)
❑ Tarefa Principal:
▪ Ler o arquivo onde se encontra o programa fonte;
▪ Produzir como saída uma sequência de tokens com
seus respectivos códigos que o Analisador Sintático
usará para validar as regras da gramática.
COMPILADORES
AULA 02
Análise Léxica (AL)
❑ Classes de tokens mais comuns:
▪ Identificadores
▪ Palavras reservadas
▪ Números inteiros sem sinal
▪ Número reais
▪ Cadeias de caracteres
▪ Sinais de pontuação e operação
▪ Caracteres especiais
▪ Símbolos compostos de dois ou mais caracteres especiais
▪ Comentários
▪ Etc.
COMPILADORES
AULA 02
Eliminação de comentários
❑ O analisador léxico desconsidera o trecho de código fonte que
encontra-se entre delimitadores de comentários
❑ Além disso, ele desconsidera espaços em branco colocados pelos
programadores a fim de melhorar a legibilidade do código fonte
(endentação).
COMPILADORES
AULA 02
Analisador Léxico
❑ Exemplos de tokens que podem ser reconhecidos em uma
linguagem de programação como C:
Palavras reservadas
identificadores
Operadores relacionais
Operadores aritméticos
Operadores lógicos
Operador de atribuição
delimitadores
Caracteres especias
If else do while
< > <= > = == !=
+ - * /
& | ! ...
=
; ,
() [] {}
COMPILADORES
AULA 02
Analisador Léxico
❑ A interação é normalmente implementada fazendo o AL como
uma subrotina do analisador sintático.
❑ Quando o AS ativa a subrotina
❑ O AL lê caracteres do arquivo até que ele possa identificar o
próximo token e o devolve com seu código.
COMPILADORES
AULA 02
Analisador Léxico
x = y * 4;
❑ Exemplo de funcionamento de um AL
Lexema Token
x id
= simb_atrib
Y id
* simb_mult
4 num
; simb_pv
COMPILADORES
AULA 02
Analisador Léxico – outro exemplo
public void p (int x){
while(x<3){
x = x+1;
}
}
Lexema Token
public id
void simb_atrib
p id
( simb_mult
) num
int simb_pv
x id
< simb_menor
3 num
while simb_while
; sim_pv
COMPILADORES
AULA 02
Analisador Léxico
❑ O Analisador Léxico simplesmente varre a entrada (arquivo
fonte) em busca de padrões pertencentes a uma linguagem.
❑ Tratamento de erros durante o processo do AL:
• Tamanho do identificador maior que o permitido
• Fim de arquivo inesperado: comentário não fechado
• Símbolo não pertencente a linguagem: @
• Inteiros/reais longos: 1349939993937737
• String mal formada: `a, `olá mundo
• Número mal formado: 2a.4
❑ São limitados os erros detectáveis nessa etapa
❑ Visão local do programa-fonte, sem contexto
fi (a>b){ ...
COMPILADORES
AULA 02
Analisador Léxico
Especificação precisa dos tokens
❑ Devemos usar notações formais para especificar a estrutura
precisa dos tokens para construir um AL sem erros:
❑ Por exemplo, mesmo a definição simples de cadeias de caracteres pode
ser definida erroneamente se nada for dito sobre os caracteres
permitidos.
<string> ::=`<caractere> {<caractere>}´
COMPILADORES
AULA 02
O Scanner - Exemplo
❑ O scanner lê o programa fonte caractere por caractere, juntado-
os em unidades atômicas chamadas de itens léxicos ou lexema.
❑ Há dois tipos de itens:
• Cadeias específicas tal com IF ou ‘;’
• Classes de cadeias tal como identificadores, números ou
rótulos.
COMPILADORES
AULA 02
O Scanner - Exemplo
❑ Para tratar os dois casos, vamos considerar um item como um
par consistindo de 2 partes:
• O tipo de item e o valor do item. Por conveniência, um item
consistindo de uma cadeia específica tal como ‘;’, será
tratado como tendo um tipo (própria cadeia), mas nenhum
valor
• Um item tal como um identificador, M, tem um tipo
(identificador) e um valor consistindo da cadeia ‘M’.
COMPILADORES
AULA 02
O Scanner - Exemplo
❑ Exemplo
Lexama
( lido)
Token
(representa)
Valor Linha Coluna 
inicial
Coluna 
final
...
if <palavra_res
ervada_if>
- Linha 
correspond
ente.
Coluna 
inicial 
correspond
ente.
Coluna 
final 
correspond
ete.
COMPILADORES
AULA 02
Análise Léxica – tratamento de erros
❑ Na ocorrência de erros, o AL pode parar ou entrar em loop
infinito. A modalidade de pânico pode ser usada para recuperar
erros léxicos ignorando os caracteres inválidos até encontrar um
que pertença ao alfabeto ou ao fim do arquivo.
❑ Outras formas de recuperar erros:
1. Remover caracteres estranhos
2. Inserir caracteres que faltam
3. Substituir caracteres incorretos por corretos
4. Trocar dois caracteres adjacentes
COMPILADORES
AULA 02
Análise Léxica – especificação de tokens
❑ Tokens são padrões que podem ser especificados através de
expressões regulares.
❑ Um alfabeto determina o conjunto de todos os caracteres
válidos para a formação de cadeias, sentenças ou palavras.
❑ Cadeias são sequências finitas de caracteres. Algumas operações
podemser aplicadas a alfabetos para ajudar na definição de
cadeias: concatenação, união e fechamento.
COMPILADORES
AULA 02
Análise Léxica – especificação de tokens
❑ As regras para definir expressões regulares sobre um alfabeto
são:
1. ε é a expressão regular para a cadeia vazia
2. a é a expressão regular para um símbolo do alfabeto {a}
3. Se a e b são expressões regulares, também são expressões
regulares
a) a | b
b) ab
c) a*
d) a+
COMPILADORES
AULA 02
Análise Léxica – especificação de tokens
❑ Expressões regulares podem receber um nome (definição
regular), formando o token de um analisador léxico.
❑ Algumas convenções podem facilitar a formação de expressões
regulares:
• Uma ou mais ocorrências de (+)
• Zero ou mais ocorrências de (*)
• Zero ou mais ocorrências de (?)
• Classes de caracteres [a-z]=a|b|c|...|z|
COMPILADORES
AULA 02
Análise Léxica – especificação de tokens
❑ São definições regulares
▪ letra -> [A-Z][a-z]
▪ dígito -> [0-9]
▪ dígitos -> dígitodígito*
▪ identificador -> letra[letra | dígito]*
▪ fração_opc -> .dígito | ε
▪ exp_opc -> E[+ | - | ε ]dígitos | ε
▪ num -> dígitos fração_opc exp_opc
▪ delim -> branco | tabulação | avanço de linha
COMPILADORES
AULA 02
Análise Léxica – reconhecimento de tokens
❑ Tokens podem ser reconhecidos por meio de autômatos finitos,
sendo que o estado final dispara o reconhecimento de um token
específico e/ou um procedimento específico (inserir na tabela de
símbolo, por exemplo).
❑ Normalmente constrói-se um diagrama de transição para
representar o reconhecimento de tokens.
COMPILADORES
AULA 02
Análise Léxica – reconhecimento de tokens
❑ Diagramas de transição
• Considerando que os Diagramas de Transição sejam
determinísticos, isto é, o mesmo símbolo não pode figurar como
rótulo em dois lados diferentes que deixam um estado.
• O estados (representados por círculos) são conectados por setas,
cujos rótulos indicam as possíveis sequências de caracteres.
• O rótulo indica qualquer caractere que não apareça como
esperado em um dado estado
COMPILADORES
AULA 02
Análise Léxica – reconhecimento de tokens
❑ Diagramas de transição
• Estados podem ter ações associadas, que são executadas
quando atingidos pelo fluxo de controle
• Círculos duplos indicam a aceitação de uma cadeia
COMPILADORES
AULA 02
Análise Léxica – reconhecimento de tokens
• Como são reconhecidos os identificadores e as palavras
reservadas?
• Como um compilador sabe o que é uma palavra reservada?
• Há linguagem que permitem usar palavras reservadas como
identificadores. Normalmente isto não acontece, mas o
reconhecimento de identificadores e palavras reservadas é
idêntico. É a tabelas de símbolos que trata de identificar as
palavras reservadas.
COMPILADORES
AULA 02
Análise Léxica – reconhecimento de tokens
• Em geral a tabela de símbolos é inicializada com o registro das
palavras reservadas da linguagem.
• O compilador sempre insere identificadores na tabela de
símbolo? Isto é necessário?
❖ Não, os identificadores são armazenados apenas uma vez,
mas seus atributos podem ser alterados ao longo da análise
do programa.
• int a;
• a = 10;
COMPILADORES
AULA 02
Análise Léxica – reconhecimento de tokens
❑ Exemplo: AF para reconhecer operadores relacionais
COMPILADORES
AULA 02
Análise Léxica – reconhecimento de tokens
❑ Exemplo: AF para reconhecer identificadores
COMPILADORES
AULA 02
Análise Léxica – reconhecimento de tokens
❑ Exemplo de implementação de um AF
COMPILADORES
AULA 02
Exercícios
COMPILADORES
AULA 02
Bibliografia Básica 
AHO, Alfred V.; SETHI, Ravi; ULLMAN, Jeffrey D. Compiladores: princípios, 
técnicas e ferramentas. Rio de Janeiro: LTC, 2008. MENEZES, Paulo Fernando 
Blauth. 
Linguagens Formais e Autômatos. 4. ed. Porto Alegre: Bookman, 2002. PRICE, Ana 
Maria; TOSCANI, Simão Sirineo. Implementação de Linguagens de Programação: 
Compiladores. 2. ed. Porto Alegre: Sagra-Luzzato - Instituto de Informática da 
UFRGS, 2001.
COMPILADORES
AULA 02
Bibliografia Complementar 
LEWIS, Harry; PAPADIMITRIOU, Christos. Elementos de Teoria da Computação. 2 
ed. Porto Alegre: Bookman, 2004;
DIVERIO,Tiaraju Asmuz; MENEZES,Paulo Blauth. Teoria da Computação: Máquinas 
Universais e Computabilidade . 3ª Ed. Vol. 5. Rio de Janeiro: Bookman, 2011. 
GRUNE, Dick. Projeto moderno de compiladores: implementação e aplicações. Rio 
de Janeiro: Campus, 2001. 
JOSÉ NETO, João. Introdução à compilação. Rio de Janeiro: LTC, 1987. DELAMARO, 
Márcio E. Como construir um compilador utilizando ferramentas Java. São Paulo: 
Novatec, 2004 
Aho, A., Lam, M., Sethi, R., and Ullman, J. (2007). CompiladoresPrincpios Técnicas 
e Ferramentas. Pearson, 2a. edition
COMPILADORES
AULA 02
AVANCE PARA FINALIZAR 
A APRESENTAÇÃO.