Aula 3 - Análise Léxica

Prévia do material em texto

Prof. Ricardo Mesquita
Análise Léxica
Analisador Léxico
 Scanner
 Função: fazer a leitura do código fonte, caractere a caractere, 
e traduzi-lo para uma sequência de símbolos léxicos 
 Trata-se de um processo de reconhecimento
 Palavras da linguagem = símbolos léxicos = tokens
 A sequência de tokens produzida é utilizada como entrada 
pelo analisador sintático 
02/20Prof. Ricardo Mesquita
Gramática
 É um mecanismo para gerar as sentenças (ou mesmo as 
palavras) de uma linguagem e é definida pela quádrupla:
G = (N, T, P, S)
onde:
N = conjunto dos símbolos não terminais
T = conjunto dos símbolos terminais
P = conjunto das regras de produção (ou regras sintáticas)
S = símbolo inicial da gramática (S  N)
03/20Prof. Ricardo Mesquita
Regras de Produção
 Definem o mecanismo de geração de sentenças da linguagem
 São representadas da forma:
 
Uma sequência de regras da forma 
 1,  2, ... ,  n,
pode ser representada da forma
 1| 2| ... | n,
 A aplicação sucessiva de regras de produção, a partir do símbolo 
inicial da gramática, permite derivar as sentenças válidas da 
linguagem representada pela gramática.
04/20Prof. Ricardo Mesquita
Derivação
 Uma derivação é um par da relação denotada por , com 
domínio em (N T)* e contradomínio em (N T)*, e é 
representado da forma  
 As sequências  e  são chamadas formas sentenciais
 A relação  é definida como:
➢ Para produções da forma S  (sendo S o símbolo inicial de G), tem-se 
que S 
➢ Para todo  , onde  = x y z, se y t é uma regra de P, então 
 x t z,
05/20Prof. Ricardo Mesquita
Derivação
 Portanto, uma derivação é a substituição de uma sequência de 
símbolos numa forma sentencial, de acordo com uma regra 
de produção
 Derivações sucessivas
 + uma ou mais derivações sucessivas
 * zero ou mais derivações sucessivas
06/20Prof. Ricardo Mesquita
Linguagem Gerada
 A Linguagem Gerada por G, denotada por L(G), é o conjunto 
formado por todas as sentenças de símbolos terminais 
deriváveis a partir do símbolo inicial S, ou seja
L(G) = { s | s T* e S + s }
07/20Prof. Ricardo Mesquita
Algumas Convenções
 Representação de terminais, não-terminais e formas sentenciais:
 Terminais:
 Letras minúsculas
 Operadores (+, -, * ...)
 Símbolos de pontuação
 Dígitos
 Cadeias de terminais que representam palavras reservadas (if, else, while etc.)
 Não-terminais:
 Letras maiúsculas
 Qualquer string delimitada por < e >
 Formas sentenciais (sequências de terminais e não-terminais):
 Letras minúsculas do alfabeto grego
08/20Prof. Ricardo Mesquita
Gramática Regular
 Uma gramática que tenha produções exclusivamente da 
forma A  wB ou A  w, onde w T* e A, B  N, é 
classificada como gramática regular
 Uma gramática assim definida é dita gramática linear à direita
 As gramáticas lineares a esquerda, cujas produções são da forma
A  Bw ou A  w, são também regulares
 Exemplo: gramática que gera identificadores
G = (N, T, P, I)
N = {I, R}
T = {l, d}
P = {I  l | lR, R lR |dR | l | d}
09/20Prof. Ricardo Mesquita
Gramática Regular
 No exemplo, “ l ” representa “letra” e “ d ” representa dígito. 
 No contexto da gramática definida no exemplo, temos que
 teste é uma palavra definida pelas regras da gramática
I
l R
t l R
l R
l R
l
e
s
t
e
G = (N, T, P, I)
N = {I, R}
T = {l, d}
P = {I  l | lR
R  lR |dR | l | d}
10/20Prof. Ricardo Mesquita
Autômatos Finitos
 Reconhecem as linguagens regulares
 Linguagens regulares são geradas por gramáticas regulares
 São constituídos basicamente de:
 Uma fita de entrada
 Uma unidade de controle
 Uma função de transição
11/20Prof. Ricardo Mesquita
Autômatos Finitos
 Um autômato finito M sobre um alfabeto  é uma 5-upla 
( K, , , e0, F ), onde:
 K é um conjunto finito de estados
  é um alfabeto dos símbolos da linguagem
 : K   K é a função de transição de estados
 e0 é o estado inicial
 F é o conjunto de estados finais
Obs:  é uma função parcial, ou seja, não precisa estar definida 
para todos os pares K  
12/20Prof. Ricardo Mesquita
Autômatos Finitos
 Formas de representação:
 Por listagem
 Por tabela de transição
 Por grafo de estados
13/20Prof. Ricardo Mesquita
Autômato Finito
 Exemplo: vamos considerar uma gramática simples capaz de gerar 
números inteiros e números reais:
G = (N, T, P, S)
N = {I, J, R}
T = {. , d}
P = {I  –dI | +dI | J
J  dJ | .dR | 
R  dR |  }
14/20Prof. Ricardo Mesquita
Autômatos Finitos
 Exemplo: vamos considerar uma gramática simples capaz de gerar 
números inteiros e números reais:
G = (N, T, P, S)
N = {I, J, R}
T = {. , d}
P = {I  –dI | +dI | J
J  dJ | .dR | 
R  dR |  }
e0 e1
e2
e3 e4
d
d d
d
d+ | –
.
Grafo de Estados
Listagem:
(e0, d) = e1,
(e0, +) = e2,
(e0, –) = e2,
(e2, d) = e1,
(e1, d) = e1,
(e1, .) = e3,
(e3, d) = e4,
(e4, d) = e4,
 d . + –
e0 e1 e2 e2
e1 e1 e3
e2 e1
e3 e4
e4 e4
Tabela de Transições
15/20
Expressões Regulares
 Uma expressão regular r, sobre um conjunto de símbolos T, 
representa uma linguagem L(r), a qual pode ser definida 
indutivamente a partir de expressões básicas, como segue:
  representa a linguagem vazia (com zero palavras)
 {  } representa a linguagem cuja única palavra é a palavra vazia
 { x | x T } representa a linguagem cuja única palavra é x
 Se r1 e r2 são expressões regulares definindo as linguagens L(r1) 
e L(r2), tem-se que:
 r1 | r2 é a linguagem { vw | v  L(r1) e w  L(r2) }, isto é, a linguagem 
cujas palavras são formadas pela concatenação de uma palavra de L(r1) 
com uma palavra de L(r2), nesta ordem
 r1* representa o conjunto L
*(r1), isto é, o conjunto de palavras que 
podem ser formadas concatenando-se zero ou mais palavras de L(r1)
16/20Prof. Ricardo Mesquita
Expressões Regulares
 Exemplos de expressões regulares:
 d(d)*  representa o conjunto dos números naturais
 [+|]d(d)*  representa o conjunto dos números inteiros
 [+|]d(d)*.d(d)*  representa o conjunto dos números reais
 l(l|d)*  representa o conjunto dos identificadores de uma LP
17/20Prof. Ricardo Mesquita
Tokens
 São símbolos léxicos (palavras da linguagem)
 São as unidades básicas do texto de um programa
 Carregam três informações:
 Classe do token
 Valor do token
 Posição do token
18/20Prof. Ricardo Mesquita
Tabela de Símbolos
 Estrutura de dados gerada pelo compilador com o objetivo 
de armazenar informações sobre os nomes definidos no 
programa fonte.
 Associa atributos aos nomes definidos pelo programador.
 Começa a ser construída na Análise Léxica.
 Cada entrada na tabela de símbolos está relacionada com a 
declaração de um nome.
19/20Prof. Ricardo Mesquita
Exercício
 Defina um autômato finito e a gramática regular equivalente 
que reconheça/gere constantes numéricas em Pascal, cujo 
formato é:
[ + | – ] d( d )* [ . d( d )* ] [ E [ + | – ] d( d )* ] 
Onde:
d : representa um dígito {0, 1, ..., 8, 9}
[ x ] : significa que x é opcional
| : significa alternativa
20/20Prof. Ricardo Mesquita
Dúvidas?