4 AnaliseLexica Parte1 - Compiladores CEFET MG

Prévia do material em texto

Compiladores 
Prof.ª Kecia Aline Marques Ferreira 
CEFET-MG 
 
Análise Léxica 
1 
Análise Léxica 
• O papel do analisador léxico 
• Tokens, padrões e lexemas 
• Erros Léxicos 
• Especificação de tokens 
• Reconhecimento de tokens 
– Conversão de AFN para AFD 
 
2 
O papel do Analisador Léxico 
• Análise Léxica é a primeira fase da compilação 
 
• O objetivo do analisador léxico é ler os caracteres do 
programa fonte, agrupá-los em lexemas, identificar o token 
correspondente ao lexema e gerar como saída um sequência 
de tokens. 
 
• O fluxo de tokens identificados na análise léxica é a entrada 
para o analisador sintático. 
 
• O analisador léxico interage com a Tabela de Símbolos 
 
3 
O papel do Analisador Léxico 
4 
Programa 
fonte 
Analisador 
Léxico 
Analisador 
Sintático 
TS (Tabela 
de 
Símbolos) 
getNextToken 
token 
O papel do Analisador Léxico 
• A analisador léxico também: 
 
– é responsável por desconsiderar comentários e separadores (espaço 
em branco, tabulação, quebra de linha) da entrada; 
 
– correlacionar mensagens de erros e números de linha no programa 
fonte. 
 
5 
Tokens, padrões e lexemas 
• Token: 
 
– par <nome, valor do atributo> 
 
– nome é um símbolo abstrato que representa um tipo de unidade léxica 
(por exemplo, identificador, palavra-chave específica, constante 
inteira, operador de atribuição, etc.) 
 
– valor do atributo é uma descrição do lexema representado pelo token 
 
• Lexema: 
 
– É uma sequência de caracteres do programa fonte que casa com o 
padrão de algum token. 
 
 
 
6 
Tokens, padrões e lexemas 
• Padrão: 
 
– especificação da forma que os lexemas de um token podem assumir 
 
– O padrão de uma palavra-chave é a sequência de caracteres que a 
constitui. 
 Exemplo: public e import são palavras-chave de Java. 
 
 
 
7 
Tokens, padrões e lexemas 
Exemplos de token, descrição informal de seus respectivos 
padrões e exemplos de lexemas 
 
8 
Token Descrição Exemplo de Lexema 
if Caracteres i, f if 
public Caracteres p,u,b,l,i,c public 
comparison Um dos seguintes símbolos: < > >= 
<= == != 
<= 
id Letra seguida por letras e/ou dígitos getResult 
intnumber 0 ou um dígito de 1 a 9 seguido de 
dígitos de 0 a 9 
0, 123, 90 
literal qualquer caractere diferente de “, 
cercado do “” 
“Hello, world!” 
Tokens, padrões e lexemas 
• Identificam-se os seguintes tokens para uma linguagem de 
programação: 
 
– Palavras-chave: um token para cada palavra-chave, sendo que o 
padrão de formação do token é a própria palavra-chave. 
 Exemplo: public, void, import, case, while, for 
 
– Operadores: um token genérico para operadores ou um token 
específico para cada operador. 
 Exemplos: 
 
 
 
 
 
 
9 
eq_op: == assign_op: = neq_op: != less_op: < 
le_op: <= ge_op: >= and_op: && or_op: || 
minus_op:- sum_op:+ mul_op: * mod_op: % 
Tokens, padrões e lexemas 
– Identificador: um token que representa identificadores na linguagem. 
Exemplo: id 
 
– Constantes numéricas: um ou mais tokens representando constantes 
numéricas. 
Exemplo: 
intNumber, realNumber, number 
 
– Literais: um token representando cadeias literais (strings) 
 
– Símbolos de pontuação: um token para cada símbolo de pontuação 
(chaves, parênteses, ponto e vírgula, ponto, etc.) 
 
 
 
 
10 
Tokens, padrões e lexemas 
• Em geral, em um programa há várias ocorrências de 
identificadores, constantes numéricas e literais. 
 
• Ou seja, em um programa pode haver mais de um lexema que 
casa com um padrão de um token. 
 
• É necessário armazenar informações sobre os lexemas 
identificados 
 
• Por exemplo: 
– ao detectar um identificador, é importante armazenar informações 
sobre qual identificador foi encontrado 
– em outras fases da compilação, é importante saber qual o escopo de 
determinado identificador 
 
 
11 
Tokens, padrões e lexemas 
• Essas informações são mantidas na Tabela de Símbolos (TS) 
 
• O analisador léxico, ao encontrar um lexema de determinado 
token (por exemplo, um identificador): 
 
– armazena as informações do lexema na TS 
 
– retorna para o Analisador Sintático o token <nome,valor do atributo>, 
onde valor do atributo é a entrada da TS correspondente ao lexema 
 
 
 
 
 
12 
Tokens, padrões e lexemas 
• Exemplo: 
 
soma = soma + a 
 
<id, entrada na TS para o símbolo soma> 
<assign_op> 
<id, entrada na TS para o símbolo soma> 
<sum_op> 
<id, entrada na TS para o símbolo a> 
 
 
 
 
 
13 
Erros Léxicos 
• Um erro léxico ocorre quando nenhum dos padrões para 
tokens casa com o prefixo da entrada restante. 
 
• Recuperação de erros: o compilador aplica determinada 
estratégia que o possibilita prosseguir a análise 
 
• A estratégia mais simples de recuperação de erro é o “modo 
pânico” (panic mode) 
 
– Desconsideram-se os caracteres até que o analisador léxico possa 
encontrar um token bem formado 
– Isso “confunde” o analisador sintático 
– Porém, para o programador, é interessante verificar erros no restante 
do programa. 
 
 
14 
Especificação de Tokens 
• Expressões regulares são utilizadas para especificar padrões de tokens 
 
• A construção de um analisador léxico baseia-se na conversão de 
expressões regulares em autômatos que realizam o reconhecimento dos 
tokens especificados 
 
• Exemplo: identificadores em C são cadeias de letras, dígitos e sublinhados. 
Eis uma definição regular de identificadores em C. 
 
 letter_ → A | B | ... | Z | a | b | ... | z | _ 
 digit → 0 | 1 | ... | 9 
 id → letter_ (letter_| digit)* 
 
 
15 
Especificação de Tokens 
• Exemplo: em uma linguagem de programação qualquer, números sem 
sinal são definidos da seguinte forma 
 
 digit → 0 | 1 | ... | 9 
 digits → digit digit* 
 optionalFraction → .digits | λ 
 optionalExponent → (E (+|-| λ) digits) | λ 
 number → digits optionalFraction optionalExponent 
 
 Exemplos de cadeias válidas: 123, 0.45, 1.5E+15, 10E3 
 
 
 
16 
Especificação de Tokens 
• Extensões da notação de expressões regulares úteis à especificação de 
tokens: 
 
– +: fecho positivo de Kleene. r+ equivale a rr* 
 
– ?: operador unário que representa “zero ou uma ocorrência”. r? equivale a r|λ 
 
– []: abreviação de sequências de caracteres ou dígitos. 
 
 Por exemplo a|b|c equivale a [abc] 
 a | b | ... | z equivale a [a-z] 
 0 | 1 | ... | 9 equivale a [0-9] 
 
 
 
 
 
17 
Especificação de Tokens 
 
A definição anterior escrita utilizando-se essa notação fica da seguinte forma: 
 
 digit → [0-9] 
 digits → digit+ 
 number → digits (.digits )? (E (+|-| λ) digits) ? 
 
 
 
 
 
18 
Reconhecimento de tokens 
• A construção de um compilador parte da definição da gramática da linguagem 
 
• Desta gramática, identificam-se os tokens que devem ser reconhecidos no 
programa 
 
• Os tokens são os terminais da gramática (escritos em negrito) 
 
• Como exemplo, consideremos o fragmento de gramática a seguir 
 
stmt → if expr then stmt | 
 if expr then stmt else stmt | 
 λ 
expr → term relop term | 
 term 
term → id | 
 number 
 
 
 
 
19 
Reconhecimento de tokens 
• Nesta linguagem, são tokens: if, then, else, relop, id e number• if, then e else são palavras-chave e também são palavras reservadas 
 
• Palavra reservada: indica que nenhum identificador pode ter formação 
igual a ela 
 
• O analisador léxico também é responsável por reconhecer os espaços em 
branco, denotados pelo token delimiter. 
 
• São considerados como espaços em branco: branco, tabulação e quebra 
de linha (blank, tab e newline) 
 
• Espaços em branco são reconhecidos pelo analisador léxico, mas não são 
passados para o analisador sintático. 
 
 
 
20 
Reconhecimento de tokens 
• Os padrões para os tokens desta linguagem são descritos pelas seguintes 
definições regulares 
 
 digit → [0-9] 
 digits → digit+ 
 number → digits (.digits )? (E (+|-| λ) digits) ? 
 letter → [A-Za-z] 
 id → letter(letter| digit)* 
 if → if 
 then → then 
 else → else 
 relop → > | < | <> | = | >= | <= 
 delimiter→ (blank | tab | newline)+ 
 
 
 
21 
Reconhecimento de tokens 
• O papel do analisador léxico é reconhecer os tokens e retorná-los para o 
analisador sintático conforme a seguinte tabela 
 
 
 
 
 
22 
Lexemas Nome do token Valor do atributo 
Qualquer delimitador - - 
if if - 
then then - 
else else - 
Qualquer id id entrada da tabela 
Qualquer number number valor da constante 
< relop LT 
<= relop LE 
= relop EQ 
<> relop NE 
> relop GT 
>= relop GE 
Reconhecimento de tokens – 
 Diagramas de Transição 
• Os padrões especificados para os tokens são convertidos em diagramas de 
transição 
 
• Os diagramas de transição correspondem a AFD com as seguintes 
características: 
– Um estado representa uma condição que poderia ocorrer durante a leitura do 
arquivo buscando um lexema a ser reconhecido 
 
– Arestas são rotuladas com um símbolo ou conjunto de símbolos passíveis de 
serem lidos na entrada a partir de determinado estado 
 
• A partir de um estado s, se o próximo símbolo da entrada for a e houver 
uma aresta saindo de s rotulada por a: 
 
– Avança-se a leitura do arquivo em um caractere 
 
– Entra-se no estado ao qual a aresta leva 
 
 
 
23 
Reconhecimento de tokens – 
 Diagramas de Transição 
 
– Um estado final indica que um lexema foi encontrado 
 
• Ações a serem tomadas no reconhecimento de um lexema são indicadas no 
respectivo estado final 
 
• Se o lexema não inclui o símbolo que levou ao estado final, deve-se recolocar o 
caractere lido na entrada. Isso é indicado por um * no estado final. 
 
• Se houver necessidade de recolocar n caracteres na entrada, utiliza-se a notação 
n* 
 
– Um único estado é inicial 
 
• O diagrama de transição sempre começa no estado inicial antes que qualquer 
símbolo da entrada tenha sido lido 
 
 
 
 
 
24 
Reconhecimento de tokens – 
 Diagramas de Transição 
 
 
 
 
 
 
25 
0 1 2 
3 
4 
5 
6 7 
8 
< = 
> 
= 
> 
= 
outro 
outro 
return (relop, LE) 
return (relop, NE) 
return (relop, LT) 
return (relop, GE) 
return (relop, GT) 
return (relop, EQ) 
* 
* 
Reconhecimento de relop 
Reconhecimento de tokens – 
 Diagramas de Transição 
 
• Reconhecimento de identificadores X palavras-chave 
 
• Há duas formas de diferenciar se uma sequência é um identificador ou 
uma palavra-chave: 
 
1. Instalar previamente as palavras reservadas na TS 
• Um campo da TS indica a qual token refere-se a palavra reservada 
 
• instalID(): método da TS que instala um símbolo na TS caso ele não esteja lá, e 
devolve a posição da TS na qual o símbolo está instalado. 
 
• getToken(): método que examina a entrada da TS e retorna o nome do token 
correspondente ao lexema encontrado (id ou o token correspondente à palavra 
reservada) 
 
 
 
26 
Reconhecimento de tokens – 
 Diagramas de Transição 
 
 
 
 
 
 
27 
Reconhecimento de id 
9 10 11 
letter 
letter | digit 
outro 
return (getToken(), instalID()) 
* 
Reconhecimento de tokens – 
 Diagramas de Transição 
 
2. Criar diagramas de transição de estados para cada palavra chave 
• Essa abordagem é menos flexível do que a anterior 
 
 
 
 
28 
t h e n 
Diferente de letra e dígito * 
... reconhecimento de id 
return (then) 
Reconhecimento de tokens – 
 Diagramas de Transição 
 
 
 
 
 
 
29 
Reconhecimento de number 
12 13 19 
digit 
digit digit 
14 15 16 17 18 
. digit 
digit 
E + | - digit outro 
21 20 
E digit 
outro outro 
* * 
* 
return(number, valor) 
return(number, entrada tabela) 
return(number, entrada tabela) 
Reconhecimento de tokens – 
 Diagramas de Transição 
 
 
 
 
 
 
30 
Reconhecimento de delim 
22 23 24 
delim 
delim 
outro * 
Conversão de AFN para um AFD 
 
• Para que possa ser implementado, um autômato deve ser determinístico 
 
• Em alguns casos, a obtenção de um autômato não determinístico é mais 
fácil do que a de um determinístico 
 
• Nestes casos, define-se um AFN e ele deve ser convertido para um AFD 
 
• Exemplo: em uma linguagem de programação, nomes de identificadores 
são definidos por letter (letter | digit)* letter 
 
 
 
 
31 
1 2 3 
letter letter 
letter , digit 
Conversão de AFN para um AFD 
 
Algoritmo para conversão de AFN para AFD 
 
Dado o AFN M = (Q, Σ, δ, I, F), o seu AFD equivalente é M’ = (Q’, Σ, δ’, q0’, F’). 
 Q é o conjunto de estados do autômato, Σ é o alfabeto, δ é a função de transições do 
autômato, I é o conjunto de estados iniciais e F é conjunto de estados finais. 
 
A construção de M’ segue os seguintes passos: 
 
Crie o estado q0’ igual à união dos estados pertencentes a I e o insira em Q’ 
 
Para cada novo estado X de Q’ faça 
Para cada símbolo a de Σ faça 
Crie o estado Y = U δ (qi, a), qi  X, e o insira em Q’ 
 Crie a transição δ’ (X, a) = Y 
 
Inclua em F’ todo estado de Q’ que possuir um estado de F. 
 
 
 
 
 
32 
Conversão de AFN para um AFD 
• Exemplo 1: 
 
 
33 
1 2 3 
letter letter 
δ letter digit 
1 2 - 
2 2,3 2 
3 - - 
letter , digit 
δ' letter digit 
{1} {2} - 
{2} {2,3} {2} 
{2,3} {2,3} {2} 
{1} {2} {2,3} 
letter 
digit 
letter 
digit 
letter 
Conversão de AFN para um AFD 
• Exemplo 2: 
 
 
34 
2 3 5 
1 
δ 0 1 
1 2 - 
2 3 - 
3 - 4 
4 - 3,5 
5 - - 
0 
δ' 0 1 
{1,2} {2,3} - 
{2,3} {3} {4} 
{3} - {4} 
{4} - {3,5} 
{3,5} - {4} 
1 4 
0 
1 
1 
{2,3} {3} {3,5} 
0 
{1,2} {4} 
0 
1 
1 1 
1 
Referência Bibliográfica 
Compiladores – Princípios, técnicas e ferramentas. 
 Alfred V. Aho, Monica S. Lam, Ravi Sethi e Jeffrey D. Ullman. 2ª 
edição. Addison Wesley. 
Capítulo 3 
 
 Introdução aos Fundamentos da Computação – Linguagens e 
Máquinas 
Newton José Vieira – Ed. Thompson 
Seção 2.3 
 
35