Análise Léxica

Conversão de Autômatos Finitos Não-Determinísticos (AFND)

para
Autômatos Finitos Determinísticos (AFD)

1
Analisador Léxico: ERs para Tokens

ERs para IF, ID, e NUM

IF = if

ID = [a-z][a-z0-9]*

NUM = [0-9]+

2
 Analisador Léxico: ERs para Autômatos

IF
IF = if i f
1 2 3

a a-z
ID = [a-z][a-z0-9]*
4 .. 5 6 7 8 ID
.
z 0-9

NUM = [0-9]+ 0 0
9 .. 10 11 .. 12 13 NUM
. .
9 9

3
 Analisador Léxico: Autômato Combinado

IF = if

ID = [a-z][a-z0-9]*

NUM = [0-9]+

4
Simulando AFND para “in”
Início (1) -> AFND pode estar em {1,4,9}
Consome i -> AFND pode estar em {2,5,8,6}
Consome n -> AFND pode estar em {7,8,6}

5
 AFND vs AFD
AFDs são facilmente simuláveis por programas de computador

AFNDs são mais complexos, pois o programa teria que “adivinhar” o

melhor caminho em alguns momentos

Outra alternativa seria tentar todas as possibilidades

Convertendo AFND em AFD

Solução:

• Emular o comportamento do um AFND para assim criar um AFD.

• Mapeia-se um conjunto de estados do AFND em um estado de um AFD
• O AFD criado a partir do AFND irá aceitar exatamente a mesma linguagem.

6
 Conversão de AFNDs para AFDs

 = {0,1}

0,1

Início q0 0 q1 1 q2
 Conversão de AFNDs para AFDs

Mapeando as transições do AFND em um AFD:

0,1 0 1
{q0} {q0,q1} {q0}
Início q0 0 q1 1 q2
{q0,q1} {q0,q1} {q0,q2}

*{q0,q2} {q0,q1} {q0}

 Conversão de AFNDs para AFDs

Desenhando o autômato a partir da tabela de transição:

1 0
0 1
{q0} {q0,q1} {q0}
Início q0 0 q0q1
1 q0q2
{q0,q1} {q0,q1} {q0,q2}

*{q0,q2} {q0,q1} {q0}

0

1
 Conversão de AFNDs para AFDs

Renomeando os estados:

1 0 1 0

0 1 0 1
Início q0 q0q1 q0q2
Início A B C

0 0

1 1
 Conversão de AFNDs para AFDs

 = {0,1,2}

0 1 2

0,1 1,2
Início q0 q1 q2

0,1,2
 Conversão de AFNDs para AFDs

0 1 2

0,1 0,2
Início q0 q1 q2

0 1 2

0,1,2 *{q0} {q0,q1,q2} {q1,q2} {q2}

*{q0,q1,q2} {q0,q1,q2} {q1,q2} {q2}

*{q1,q2}  {q1,q2} {q2}

Mapeando as transições do AFND em um AFD: *{q2}   {q2}

 Conversão de AFNDs para AFDs

Desenhando o autômato a partir da tabela de transição:

0
Início

0 1 2 0
q0 q0q1q2

*{q0} {q0,q1,q2} {q1,q2} {q2} 2 1

*{q0,q1,q2} {q0,q1,q2} {q1,q2} {q2}

1 2

*{q1,q2}  {q1,q2} {q2}

q1q2 q2 2
*{q2}   {q2} 1
2
 Conversão de AFNDs para AFDs

Renomeando os estados:
0 0
Início Início

0 0
q0 q0q1q2 A B

2 1 2 1

1 2 1 2

q1q2 q2 2 C D 2
1 1
2 2
 Conversão de AFND-  para AFD

 = {a,b}


 a

 
a b b
 
b


 Conversão de AFND-  para AFD


a
 
 
  a b b
b

a b
{0,1,2,4,7} {1,2,3,4,6,7,8} {1,2,4,5,6,7}

{1,2,3,4,6,7,8} {1,2,3,4,6,7,8} {1,2,4,5,6,7,9}

{1,2,4,5,6,7} {1,2,3,4,6,7,8} {1,2,4,5,6,7}

{1,2,4,5,6,7,9} {1,2,3,4,6,7,8} {1,2,4,5,6,7,10}

Mapeando as transições do AFND- em um AFD: *{1,2,4,5,6,7,10} {1,2,3,4,6,7,8} {1,2,4,5,6,7}

 Conversão de AFND-  para AFD


a
 
 
  a b b
b

a b
A {0,1,2,4,7} {1,2,3,4,6,7,8} B {1,2,4,5,6,7} C

B {1,2,3,4,6,7,8} {1,2,3,4,6,7,8} B {1,2,4,5,6,7,9} D

C {1,2,4,5,6,7} {1,2,3,4,6,7,8} B {1,2,4,5,6,7} C

D {1,2,4,5,6,7,9} {1,2,3,4,6,7,8} B {1,2,4,5,6,7,10} E

Renomeando os estados: E *{1,2,4,5,6,7,10} {1,2,3,4,6,7,8} B {1,2,4,5,6,7} C

 Conversão de AFND-  para AFD

a b
A {0,1,2,4,7} {1,2,3,4,6,7,8} B {1,2,4,5,6,7} C

B {1,2,3,4,6,7,8} {1,2,3,4,6,7,8} B {1,2,4,5,6,7,9} D

C {1,2,4,5,6,7} {1,2,3,4,6,7,8} B {1,2,4,5,6,7} C

b
D {1,2,4,5,6,7,9} {1,2,3,4,6,7,8} B {1,2,4,5,6,7,10} E
b
E *{1,2,4,5,6,7,10} {1,2,3,4,6,7,8} B {1,2,4,5,6,7} C
C a
b
a
a
A B D E
a b b

a
Desenhando o autômato a partir da tabela de transição:
 Conversão de AFND-  para AFD
 = {a,b} 

 a

 
a b b
 
b


b
b
C a
b
a
a
A B D E
a b b

a
19
 Conversão de AFND-  para AFD → ANTES

IF = if ERs para IF, ID, e NUM

ID = [a-z][a-z0-9]*

NUM = [0-9]+

20
 Conversão de AFND-  para AFD → DEPOIS

IF = if

ID = [a-z][a-z0-9]*
a-e,g-z,0-9
NUM = [0-9]+
2,5,6,8
f 3,6,7,8
a-z
i 0-9

a-h 5,6,8 a-z 6,7,8

j-z 0-9 a-z
1,4,9 0-9
0-9
10,11,13 11,12,13 0-9
0-9

21
 Conversão de AFND-  para AFD → ANTES

IF = if ERs para IF, ID, e NUM

ID = [a-z][a-z0-9]*

NUM = [0-9]+

22
 Conversão de AFND-  para AFD → DEPOIS

IF = if

ID = [a-z][a-z0-9]*
a-e,g-z,0-9
NUM = [0-9]+
2,5,6,8
f 3,6,7,8
a-z
i 0-9

a-h 5,6,8 a-z 6,7,8

j-z 0-9 a-z
1,4,9 0-9
0-9
IF = 3 10,11,13 11,12,13 0-9
0-9
ID = 8

NUM = 13
23
 Conversão de AFND-  para AFD → DEPOIS

IF = if

ID = [a-z][a-z0-9]*
a-e,g-z,0-9
NUM = [0-9]+
2,5,6,8
f 3,6,7,8
a-z
i 0-9

a-h 5,6,8 a-z 6,7,8

j-z 0-9 a-z
1,4,9 0-9
NUM
0-9
IF = 3 10,11,13 11,12,13 0-9
0-9
ID = 8
NUM
NUM = 13
24
 Conversão de AFND-  para AFD → DEPOIS

IF = if

ID = [a-z][a-z0-9]*
ID a-e,g-z,0-9
NUM = [0-9]+
2,5,6,8
f 3,6,7,8
a-z
i 0-9
ID ID
a-h 5,6,8 a-z 6,7,8
j-z 0-9 a-z
1,4,9 0-9
NUM
0-9
IF = 3 10,11,13 11,12,13 0-9
0-9
ID = 8
NUM
NUM = 13
25
 Conversão de AFND-  para AFD → DEPOIS

IF = if

ID = [a-z][a-z0-9]*
ID a-e,g-z,0-9
NUM = [0-9]+
2,5,6,8 IF
f 3,6,7,8
a-z
i 0-9
ID ID
a-h 5,6,8 a-z 6,7,8
j-z 0-9 a-z
1,4,9 0-9
NUM
0-9
IF = 3 10,11,13 11,12,13 0-9
0-9
ID = 8
NUM
NUM = 13
26
Lista de Exercícios

Lista 3

• Exercícios Teóricos

27