UPE – Caruaru – Sistemas de Informação
Disciplina: Compiladores
Prof.: Paulemir G. Campos
Análise Léxica
(Parte 2)
11/5/2015
Comp - Prof. Paulemir Campos
1
Roteiro da Aula

Expressões Regulares

Autômato Finito

Referências
11/5/2015
Comp - Prof. Paulemir Campos
2
Expressões Regulares
11/5/2015
Comp - Prof. Paulemir Campos
3
Introdução



Uma linguagem é um conjunto de
strings.
Uma string é uma seqüência finita de
símbolos ou caracteres.
Os símbolos ou caracteres fazem parte
do alfabeto finito de uma linguagem.
11/5/2015
Comp - Prof. Paulemir Campos
4
Introdução


No caso de linguagens de programação,
o alfabeto utilizado é o conjunto de
caracteres ASCII.
Para facilitar a especificação de uma
linguagem de programação, utiliza-se a
notação de expressões regulares.
11/5/2015
Comp - Prof. Paulemir Campos
5
Notação de
Expressões Regulares

Caracter: Para cada caracter a no
alfabeto da linguagem, a expressão
regular a indica que a linguagem
contém apenas a string “a”;
11/5/2015
Comp - Prof. Paulemir Campos
6
Notação de
Expressões Regulares

Alternação: Dada duas expressões
regulares M e N, o operador de
alternação “|” permite a construção de
uma nova expressão regular M | N.

11/5/2015
Ex.: A linguagem de a | b contém as duas
string “a” e “b”.
Comp - Prof. Paulemir Campos
7
Notação de
Expressões Regulares

Concatenação: Dada duas expressões
regulares M e N, o operador de
concatenação “.” permite a construção
de uma nova expressão regular M . N.

11/5/2015
Ex.: A expressão regular (a | b). a contém
as duas string “aa” e “ba”.
Comp - Prof. Paulemir Campos
8
Notação de
Expressões Regulares

Epsilon: A expressão regular 
representa uma string vazia.

11/5/2015
Ex.: A expressão regular (a . b) | 
representa a linguagem { “ ”, “ab” }
Comp - Prof. Paulemir Campos
9
Notação de
Expressões Regulares

Repetição: Dada uma expressão
regular M, o fechamento de Kleene é
representado por M*. Uma string está
em M* se é a concatenação de
nenhuma ou mais strings de M.

11/5/2015
Ex.: ((a | b) . a)* representa o conjunto
infinito { “ ”, “aa”, “ba”, “aaaa”, “baba”,
“aaaaaa”, “bababa”, ...}
Comp - Prof. Paulemir Campos
10
Notação de
Expressões Regulares

Com esse conjunto básico de
operadores (caracter, alternação,
concatenação, epsilon e repetição),
pode-se especificar o conjunto de
caracteres ASCII correspondente aos
tokens (símbolos) léxicos de uma
linguagem de programação.
11/5/2015
Comp - Prof. Paulemir Campos
11
Notação de
Expressões Regulares

Na escrita de expressões regulares,
algumas vezes pode-se omitir os
símbolos de concatenação ou .

11/5/2015
Ex.: ab | c indica (a . b) | c
(a |) indica (a | )
Comp - Prof. Paulemir Campos
12
Notação de
Expressões Regulares

Algumas outras abreviações:





11/5/2015
[abcd] indica (a | b | c | d);
[b-g] indica [bcdefg];
[b-gM-Qkr] indica [bcdefgMNOPQkr];
M? indica (M | );
M+ indica (M.M*).
Comp - Prof. Paulemir Campos
13
Notação de
Expressões Regulares

Resumo:





11/5/2015
a indica um caracter “a”
 indica string vazia
espaço em branco também pode
representar a string vazia
M | N indica alternação, escolha de M ou N
M . N indica concatenação, M seguido de N
Comp - Prof. Paulemir Campos
14
Notação de
Expressões Regulares

Resumo (Cont.):





11/5/2015
MN também indica concatenação
M* indica repetição (zero ou mais vezes)
M+ indica repetição (uma ou mais vezes)
M? indica zero ou uma ocorrência de M
[a-zA-Z] indica alternação de conjunto
de caracteres
Comp - Prof. Paulemir Campos
15
Notação de
Expressões Regulares

Resumo (Cont.):


11/5/2015
. indica qualquer caracter (q. c.) único,
exceto símbolo de nova linha
“a.+*” uma string entre aspas duplas
indica a própria string
Comp - Prof. Paulemir Campos
16
Notação de
Expressões Regulares

Exemplos:




11/5/2015
if
retorne(palavra_res, if)
[a-z][a-z0-9]* retorne(identificador, id)
[0-9]+
retorne(inteiro, num_int)
([0-9]+“.”[0-9]*)|([0-9]*“.”[0-9]+)
retorne (real, num_real)
Comp - Prof. Paulemir Campos
17
Notação de
Expressões Regulares

Exemplos (Cont.):


11/5/2015
(“--”[a-z]*“\n”)|(“ ” | “\n” | “\t” )+
* não faça nada *
. ou q.c.
mostre(mensagem_erro)
Comp - Prof. Paulemir Campos
18
Considerações

Deve-se definir o critério para
reconhecimento de caracteres do
analisador léxico:


11/5/2015
Maior Símbolo Possível: Lê a maior cadeia
de caracteres possível que pode bater com
a expressão regular de um símbolo léxico;
Regra de Prioridade: Lê caracteres até
obter-se uma expressão regular de um
símbolo léxico.
Comp - Prof. Paulemir Campos
19
Considerações

Exemplo:

11/5/2015
O símbolo if8 indica um identificador ou
uma palavra reservada?
Resposta: Depende do critério do
analisador léxico. Pelo “Maior Símbolo
Possível”, if8 indica um identificador, mas,
pela “Regra de Prioridade” if indica uma
palavra reservada.
Comp - Prof. Paulemir Campos
20
Autômato Finito
11/5/2015
Comp - Prof. Paulemir Campos
21
Introdução


Apesar de Expressões Regulares serem
convenientes para especificar tokens
léxicos, necessita-se de um formalismo
que possa ser implementado como um
programa de computador;
Um Autômato Finito pode ser utilizado
para esta finalidade.
11/5/2015
Comp - Prof. Paulemir Campos
22
Definição

Um Autômato Finito tem:




11/5/2015
Um conjunto finito de estado;
Arcos ou arestas fazem a ligação de um
estado a outro;
Cada arco é rotulado com um símbolo ou
caracter;
Há um estado inicial e determinados
estados são rotulados de estados finais.
Comp - Prof. Paulemir Campos
23
Exemplos de
Autômatos Finitos
a-z, 0-9
i
f
1
2
a-z
3
1
2
IF
ID
0-9
0-9
.
0-9
0-9
1
0-9
1
2
.
2
3
0-9
0-9
4
Num_Int
5
Num_Real
11/5/2015
Comp - Prof. Paulemir Campos
24
Exemplos de
Autômatos Finitos
a-z
-
1
2
\n
3
4
Comentário
“ ”, \n, \t
“ ”, \n, \t
5
q.c. – (a-z, 0-9, ., -,“ ”)
Espaço_Branco
1
2
Erros
11/5/2015
Comp - Prof. Paulemir Campos
25
Autômato Finito Determinístico

Num Autômato Finito Determinístico
(DFA – Deterministic Finite Automaton)
nenhum dois arcos que saem de um
mesmo estado são rotulados com um
mesmo símbolo ou caracter.
11/5/2015
Comp - Prof. Paulemir Campos
26
Autômato Finito Determinístico


Um DFA pode ser utilizado para aceitar
ou rejeitar strings.
A partir do estado inicial, para cada
caracter da string de entrada igual ao
rótulo do arco de saída, avança-se pro
próximo estado;
11/5/2015
Comp - Prof. Paulemir Campos
27
Autômato Finito Determinístico


Caso atinja-se o estado final de um
símbolo léxico, aceita-se a string;
Caso contrário, ou em algum ponto
houver diferença entre caracter de
entrada e rótulo do arco, rejeita-se a
string.
11/5/2015
Comp - Prof. Paulemir Campos
28
Referências

Appel, A. W. Modern Compiler
Implementation in C. Cambridge
University Press, 1998. (Capítulo 2,
seções 2.2 e 2.3).
11/5/2015
Comp - Prof. Paulemir Campos
29