PROT ÓTIPO PARA TRANSFORMA ÇÃO DE UMA …dsc.inf.furb.br/arquivos/tccs/apresentacoes/2000-2ronaldglatzap.pdf · ROTEIRO Aqui serão apresentados alguns conceitos ... TABELA DO

1

SAIR

ANTERIOR

RONALD GLATZRONALD GLATZRONALD GLATZ

ROTEIRO

PROTPROTÓÓTIPO PARA TRANSFORMATIPO PARA TRANSFORMAÇÇÃO DE UMA ÃO DE UMA EXPRESSÃO REGULAR PARA UMA FUNEXPRESSÃO REGULAR PARA UMA FUNÇÇÃO ÃO EQUIVALENTE EM PASCAL, UTILIZANDO EQUIVALENTE EM PASCAL, UTILIZANDO

DOIS ALGORITMOS BASEADOS NO TEOREMA DOIS ALGORITMOS BASEADOS NO TEOREMA DE KLEENEDE KLEENE

2

SAIR

ANTERIOR


ROTEIRO

ROTEIROROTEIROROTEIRO�OBJETIVO DESTE TRABALHO

�ALGUNS CONCEITOS BÁSICOS

�ALGORITMO DE [HOP1979]

�ALGORITMO DE [SIL2000]

�TRANSFORMAÇÃO DE UM AFD EM PROGRAMA

�ESPECIFICAÇÃO DOS PROTÓTIPOS

�APRESENTAÇÃO DOS PROTÓTIPOS� [HOP1979]� [SIL2000]

�COMPARAÇÃO DOS ALGORITMOS

3

SAIR

ANTERIOR


ROTEIRO

�PROTÓTIPO DE [SIL2000]

�PROTÓTIPO DE [HOP1979]

�ANEXOS�EQUIVALÊNCIA DE MOORE

�INTERPRETADOR UNIVERSAL DE CADEIAS

�CONCLUSÃO

ROTEIROROTEIROROTEIRO

4

SAIR

ANTERIOR


ROTEIRO

�APRESENTAR A TRANSFORMAÇÃO DE UMA EXPRESSÃO REGULAR EM UM AFD

�SERVIR DE FERRAMENTA DE ENSINO-APRENDIZAGEM

�APRESENTAR UMA COMPARAÇÃO ENTRE AS DIFERENTES FORMAS DE TRANSFORMAÇÃO

OBJETIVOOBJETIVOOBJETIVO

5

SAIR

ANTERIOR


ROTEIRO

�Aqui serão apresentados alguns conceitos mais importantes para este trabalho

�ALFABETO (∑)� {A,B,C,D,E,...,X,Z}� {0,1}� {0,1,2,3,4,5,6,7,8,9}

�PALAVRA SOBRE O NOSSO ALFABETO� Abacate� Livro

BÁSICOBBÁÁSICOSICO

6

SAIR

ANTERIOR


ROTEIRO

�EXPRESSÃO REGULAR (ER)� a(b|c)*ca*|^� a(aa|bb)*� a*� a**

�CONJUNTO REGULAR� {0,1,01,001,011, ...}: cadeias de ∑={0,1}

BÁSICOBBÁÁSICOSICO

7

SAIR

ANTERIOR


ROTEIRO

BÁSICO-AFNDBBÁÁSICOSICO--AFNDAFND1

b

2

b

f03

f04a

a

8

SAIR

ANTERIOR


ROTEIRO

BÁSICO-AFDBBÁÁSICOSICO--AFDAFD

2 3b

1a

4b

b a

a

a

b

9

SAIR

ANTERIOR


ROTEIRO

BÁSICO-AFεBBÁÁSICOSICO--AFAFεε

21^

b a

2

10

SAIR

ANTERIOR


ROTEIRO

BÁSICO-LLCBBÁÁSICOSICO--LLCLLC�LINGUAGEM PARA DEFINIR OUTRAS LINGUAGENS

�LINGUAGENS DE PROGRAMAÇÃO�ANALISADORES LÉXICOS�EDIÇÃO DE TEXTO

11

SAIR

ANTERIOR


ROTEIRO

ALGORITMO DE [HOP1979]FASES

ER

� AFεεεε

� AFND

� AFD

Fase 1

Fase 2

Fase 3

12

SAIR

ANTERIOR


ROTEIRO

GERAÇÃO DO AFε

6 7^

5 8a a

10 11^

9 12b b

13 14

^

^

^

^

1 2

^

a3 4

^ ^

^

^ 14

�a*(aa|bb)

13

SAIR

ANTERIOR


ROTEIRO

GERAÇÃO DO AFε

6 7^

5 8a a

10 11^

9 12b b

13 14

^

^

^

^

1 2

^

a3 4

^ ^

^

^ 14

�a*(aa|bb)

14

SAIR

ANTERIOR


ROTEIRO

GERAÇÃO DO AFε

6 7^

5 8a a

10 11^

9 12b b

13 14

^

^

^

^

1 2

^

a3 4

^ ^

^

^ 14

�a*(aa|bb)

15

SAIR

ANTERIOR


ROTEIRO

GERAÇÃO DO AFε

6 7^

5 8a a

10 11^

9 12b b

13 14

^

^

^

^

1 2

^

a3 4

^ ^

^

^ 14

�a*(aa|bb)

16

SAIR

ANTERIOR


ROTEIRO

GERAÇÃO DO AFε

6 7^

5 8a a

10 11^

9 12b b

13 14

^

^

^

^

1 2

^

a3 4

^ ^

^

^ 14

�a*(aa|bb)

17

SAIR

ANTERIOR


ROTEIRO

GERAÇÃO DO AFε

6 7^

5 8a a

10 11^

9 12b b

13 14

^

^

^

^

1 2

^

a3 4

^ ^

^

^ 14

�a*(aa|bb)

18

SAIR

ANTERIOR


ROTEIRO

GERAÇÃO DO AFND A PARTIR DO AFε

�Consiste em gerar um AFND equivalente a partir do AFε da fase 1

�AFND M=(∑,Q,δ’,q0,F)� ∑ = {a,b}� Q = {1,2,3,4, ..., 13, 14}� δ’ = Fε(δ’’(δ’’’(q,^),x))� F = Conjunto de Estados Finais

19

SAIR

ANTERIOR


ROTEIRO

GERAÇÃO DO AFND A PARTIR DO AFεConjunto de Estados Finais

� O conjunto de estados finais do AFND é formado pelo estado final do AFε e todos os estados que atingem o estado final com o símbolo vazio (^) (direta ou indiretamente) no AFε.

� F={8,12,14}

6 7^

5 8a a

10 11^

9 12b b

13 14

^

^

^

^

1 2

^

a3 4

^ ^

^

^ 14

20

SAIR

ANTERIOR


ROTEIRO

GERAÇÃO DO AFND A PARTIR DO AFεGeração das Transições do AFND

� A geração das transições do AFND é realizada através da função de transição δ’ = Fε(δ’’(δ’’’(q,^),x))

� Esta função é dividida nas seguintes etapas:� δ’’’(q,^) = gera conjuntos de cada estado do AFND de todos os estados atingidos pelo símbolo vazio (^). O estado que gerou o conjunto também faz parte do conjunto – ETAPA 1

� δ’’(δ’’’(q,^),x) = para cada estado dos conjuntos da ETAPA 1 gera-se o conjunto de todos os estados atingidos pelos símbolos do alfabeto – ETAPA 2

� Fε(δ’’(δ’’’(q,^),x)) = para todos os estados atingidos na ETAPA 2 gera-se o conjunto de todos os estados atingidos (direta ou indiretamente) pelo símbolo vazio (^) – ETAPA 3

21

SAIR

ANTERIOR


ROTEIRO

GERAÇÃO DO AFND A PARTIR DO AFεδ’ = Fε(δ’’(δ’’’(q,^),x))

�Sendo q = 1 aplicado sobre δ’’’(q,^)temos:� δ’’’(1,^) = {1}

6 7^

5 8a a

10 11^

9 12b b

13 14

^

^

^

^

1 2

^

a3 4

^ ^

^

^ 14

22

SAIR

ANTERIOR


ROTEIRO


�Sendo q = 2 aplicado sobre δ’’’(q,^)temos:� δ’’’(2,^) = {1,2,4,5,9,13}

6 7^

5 8a a

10 11^

9 12b b

13 14

^

^

^

^

1 2

^

a3 4

^ ^

^

^ 14

23

SAIR

ANTERIOR


ROTEIRO


�Sendo q = 3 aplicado sobre δ’’’(q,^)temos:� δ’’’(3,^) = {1,3,4,5,9,13}

6 7^

5 8a a

10 11^

9 12b b

13 14

^

^

^

^

1 2

^

a3 4

^ ^

^

^ 14

24

SAIR

ANTERIOR


ROTEIRO

GERAÇÃO DO AFND A PARTIR DO AFεδ’ = Fε(δ’’(δ’’’(q,^),x)) –

conjuntos obtidos:� δ’’’(1,^) = {1}� δ’’’(2,^) = {1,2,4,5,9,13}

� δ’’’(3,^) = {1,3,4,5,9,13}

� δ’’’(4,^) = {4,5,9,13}� δ’’’(5,^) = {5}� δ’’’(6,^) = {6,7}� δ’’’(7,^) = {7}

� δ’’’(8,^) = {8,14}� δ’’’(9,^) = {9}� δ’’’(10,^) = {10,11}� δ’’’(11,^) = {11}� δ’’’(12,^) = {12,14}� δ’’’(13,^) = {5,9,13}� δ’’’(14,^) = {14}

25

SAIR

ANTERIOR


ROTEIRO


� Elementos da ETAPA 2:� δ’’(δ’’’(q,^),x))� ∑={a,b}� x = símbolo do ∑� Conjunto de cada estado da ETAPA 1

6 7^

5 8a a

10 11^

9 12b b

13 14

^

^

^

^

1 2

^

a3 4

^ ^

^

^ 14

26

SAIR

ANTERIOR


ROTEIRO


� ∑={a,b}� δ’’’(1,^) = {1} - ETAPA 1� x=“a”� δ’’({1},”a”)) = {2}� x=“b”� δ’’({1},”b”)) = {}

6 7^

5 8a a

10 11^

9 12b b

13 14

^

^

^

^

1 2

^

a3 4

^ ^

^

^ 14

27

SAIR

ANTERIOR


ROTEIRO


� ∑={a,b}� δ’’’(2,^) = {1,2,4,5,9,13} - ETAPA 1� x=“a”� δ’’({1,2,4,5,9,13},”a”)) = {2,6}� x=“b”� δ’’({1,2,4,5,9,13},”b”)) = {10}

6 7^

5 8a a

10 11^

9 12b b

13 14

^

^

^

^

1 2

^

a3 4

^ ^

^

^ 14

28

SAIR

ANTERIOR


ROTEIRO


� ∑={a,b}� δ’’’(3,^) = {1,3,4,5,9,13} - ETAPA 1� x=“a”� δ’’({1,3,4,5,9,13},”a”)) = {2,6}� x=“b”� δ’’({1,3,4,5,9,13},”b”)) = {10}

6 7^

5 8a a

10 11^

9 12b b

13 14

^

^

^

^

1 2

^

a3 4

^ ^

^

^ 14

29

SAIR

ANTERIOR


ROTEIRO


RESULTADOS DA ETAPA 2 PARA ∑∑∑∑={a,b}� δ’’({1},”a”) = {2} (Estado 1)� δ’’({1},”b”) = {}� δ’’({1,2,4,5,9,13},”a”) = {2,6} (Estado 2)� δ’’({1,2,4,5,9,13},”b”) = {10}� δ’’({1,3,4,5,9,13},”a”) = {2,6} (Estado 3)� δ’’({1,3,4,5,9,13},”b”) = {10}� δ’’({4,5,9,13} ,”a”) = {6} (Estado 4)� δ’’({4,5,9,13} ,”b”) = {10}...� δ’’({14} ,”a”) = {} (Estado 14)� δ’’({14} ,”b”) = {}

30

SAIR

ANTERIOR


ROTEIRO


� Elementos da ETAPA 3:� ∑={a,b}� Fε(δ’’(δ’’’(q,^),x)) onde Fε=δ(q,^)� Conjunto de cada estado da ETAPA 2

6 7^

5 8a a

10 11^

9 12b b

13 14

^

^

^

^

1 2

^

a3 4

^ ^

^

^ 14

31

SAIR

ANTERIOR


ROTEIRO


TRANSIÇÕES DO ESTADO 1� ∑={a,b}� δ’’({1},”a”) = {2} (Estado 1)� δ’’({1},”b”) = {}� Fε({2}) = {1,2,4,5,9,13} (símbolo “a” do ∑)� Fε({}) = {} (símbolo “b” do ∑)

6 7^

5 8a a

10 11^

9 12b b

13 14

^

^

^

^

1 2

^

a3 4

^ ^

^

^ 14

32

SAIR

ANTERIOR


ROTEIRO


TRANSIÇÕES DO ESTADO 2� ∑={a,b}� δ’’({1,2,4,5,9,13},”a”) = {2,6} (Estado 2)� δ’’({1,2,4,5,9,13},”b”) = {10}� Fε({2,6}) = {1,2,4,5,7,9,13} (símbolo “a” do ∑)� Fε({10}) = {10,11} (símbolo “b” do ∑)

6 7^

5 8a a

10 11^

9 12b b

13 14

^

^

^

^

1 2

^

a3 4

^ ^

^

^ 14

33

SAIR

ANTERIOR


ROTEIRO


TRANSIÇÕES DO ESTADO 3� ∑={a,b}� δ’’({1,3,4,5,9,13},”a”) = {2,6} (Estado 3)� δ’’({1,3,4,5,9,13},”b”) = {10}� Fε({2,6}) = {1,2,4,5,7,9,13} (símbolo “a” do ∑)� Fε({10}) = {10,11} (símbolo “b” do ∑)

6 7^

5 8a a

10 11^

9 12b b

13 14

^

^

^

^

1 2

^

a3 4

^ ^

^

^ 14

34

SAIR

ANTERIOR


ROTEIRO

GERAÇÃO DO AFND A PARTIR DO AFεAFND RESULTANTE

1 2a 3 6 75 8 10 119 124

a

a

13

a

a

a

a

a

b

a

aa

a

b

a

a

a

a

a

a

a

a

a

b

b

a

a

b

b

a

a a

14

a

a

a

b

b

b

b

b

b

a

a

bb

a 8 12 14

35

SAIR

ANTERIOR


ROTEIRO

ALGORITMO DE [SIL2000]FASES

ER

� EXPRESSÃO PÓS-FIXADA

� TABELA DO DESMONTE

� AFD

Fase 1

Fase 2

Fase 3 � GRAFO DE TRANSIÇÕES

Fase 4

36

SAIR

ANTERIOR


ROTEIRO

GERAÇÃO DA EXPRESSÃO PÓS-FIXADA

� A EXPRESSÃO PÓS-FIXADA É GERADA ATRAVÉS DE UMA DEFINIÇÃO LLC DESCRITA EM [SIL2000].

a.(b+c)*|c.a*|^

abc+*.ca*.+^+

ER

EXPRESSÃOPÓS-FIXADA

37

SAIR

ANTERIOR


ROTEIRO

EXPRESSÃO PÓS-FIXADALLC DE [SIL2000]

^ → símbolo vazioR → expressão regularSR → simples expressão regularRR → resto da expressão regular

R → SR RR;RR → '+' SR | '.' SR | ^;SR → T SR1;SR1 → '+' T SR1 | ^; {EMITIR '+'}T → F T1;T1 → '.' F T1 | ^; {EMITIR '.'}F → '(' R ')' F1 | #S F1; {EMITIR Símbolo S}F1 → '*' F1 | ^; {EMITIR '*'}

38

SAIR

ANTERIOR


ROTEIRO

EXPRESSÃO PÓS-FIXADAGeração pela LLC

�DADA A EXPRESSÃO REGULAR:�a.(b+c)*+c.a*+^

�PROCESSO: LER TODOS OS SÍMBOLOS DA EXPRESSÃO REGULAR DA ESQUERDA PARA A DIREITA E SUBMETÊ-LOS A DEFINIÇÃO EM LLC APRESENTADA POR [SIL2000]

�VEJA PROCESSO

39

SAIR

ANTERIOR


ROTEIRO

TABELA DO DESMONTE

� CONSISTE EM GERAR UMA TABELA A PARTIR DA EXPRESSÃO PÓS-FIXADA OBTIDA NA FASE 1

� A EXPRESSÃO PÓS-FIXADA É SUBMETIDA A UM CONJUNTO DE OPERAÇÕES QUE DARÃO ORIGEM A TABELA

� A EXPRESSÃO PÓS-FIXADA É PROCESSADA SÍMBOLO A SIMBOLO DA DIREITA PARA A ESQUERDA. CADA SÍMBOLO É SUBMETIDO AO CONJUNTO DE PASSOS QUE FORMARÃO A TABELA DO DESMONTE.

40

SAIR

ANTERIOR


ROTEIRO

TABELA DO DESMONTE

�ESTADO INICIAL: 1�ESTADO FINAL: 6

�abc+*.ca*.+^+�1 PARA ESTADO INICIAL�1 PARA ESTADO FINAL�2 PARA O OPERADOR DE CONCATENAÇÃO�2 PARA O OPERADOR DE FECHAMENTO

41

SAIR

ANTERIOR


ROTEIRO

TABELA DO DESMONTEabc+*.ca*.+^+

.........

2c1

6.1

6.1

6^1

6+1

6+1

CHEGADA:SÍMBOLO:SAÍDA:

�VEJA PROCESSO

42

SAIR

ANTERIOR


ROTEIRO

GRAFO DE TRANSIÇÕES (GT)Geração a partir da FASE 2

�É GERADO INICIALMENTE UMA NOVA TABELA A PARTIR DA TABELA DO DESMONTE

�NESTA NOVA TABELA ESTÃO ELIMINADAS TODAS AS LINHAS QUE CONTÉM OPERADORES DE UNIÃO, FECHAMENTO E CONCATENAÇÃO

�A NOVA TABELA RESULTA NO GRAFO DE TRANSIÇÕES.

43

SAIR

ANTERIOR


ROTEIRO


.........

3a3

6^3

3^2

CHEGADA:SÍMBOLO:SAÍDA:

6^1

2c1

44

SAIR

ANTERIOR


ROTEIRO


2

6

3

1

4 5

^

ca ^

^^

^

b

c

a

6

45

SAIR

ANTERIOR


ROTEIRO

TABELA DE TRANSIÇÕES DO AFD

� CONSISTE NA GERAÇÃO DE UMA TABELA DE TRANSIÇÕES A PARTIR DO GT

� ESTADO INICIAL: ESTADOS INICIAIS DO GT E TODOS OS ESTADOS ATINGIDOS A PARTIR DOS ESTADOS INICIAIS PELO SÍMBOLO VAZIO (^)

� O PROCESSO DE GERAÇÃO DA TABELA DE TRANSIÇÕES A PARTIR DO GT É IDÊNTICO AO PROCESSO DE GERAÇÃO DA TABELA DE TRANSIÇÕES A PARTIR DO AFND NO ALGORITMO DE [HOP1979]

� O GT É UMA REPRESENTAÇÃO GRÁFICA DO MODELO MATEMÁTICO AUTÔMATO FINITO

46

SAIR

ANTERIOR


ROTEIRO


�ESTADOS FINAIS: CONJUNTO DE ESTADOS FORMADOS A PARTIR DO GT E QUE CONTÉM ALGUM DOS ESTADOS FINAIS DO GT

�PROCESSAMENTO DOS SÍMBOLOS ALFABETO COM OS ESTADOS DO GT E SUAS TRANSIÇÕES DE ACORDO COM O ALGORITMO APRESENTADO POR [MAN1974]

�UMA EXPLICAÇÃO DETALHADA DOS PASSOS DO ALGORITMO DESCRITO POR [MAN1974] PODE SER ENCONTRADO NA MONOGRAFIA

47

SAIR

ANTERIOR


ROTEIRO


Mj

{}{}{3,6}{3,6}5 (+)

{5,6}{5,6}{}{5,6}4 (+)

{}{}{3,6}{2,3,6}3 (+)

{5,6}{5,6}{}{4,5,6}2 (+)

{2,3,6}{}{4,5,6}{1,6}1 (-/+)

cbaMi

ESTADOS DO AFD

48

SAIR

ANTERIOR


ROTEIRO

AFD OBTIDO A PARTIR DA TABELA DE TRANSIÇÕES

1a

3

c

f02

f05

a

a

b

f04

cc

b

3

1

49

SAIR

ANTERIOR


ROTEIRO

TRANSFORMAÇÃO DE UM AFD EM PROGRAMA

�CONSISTE EM TRANFORMAR UM AFD EM UM PROGRAMA

�A IMPLEMENTAÇÃO DE UM AFD EM UM COMPUTADOR SEGUE DUAS LINHAS:�IMPLEMENTAÇÃO POR CÓDIGO DIRETO�CONTROLE DE TABELA DE TRANSIÇÕES

50

SAIR

ANTERIOR


ROTEIRO


�IMPLEMENTAÇÃO POR CÓDIGO DIRETO: cada estado e suas transições são implementadas diretamente no programa

�CONTROLE DE TABELA DE TRANSIÇÕES: um interpretador universal interpreta a Tabela de Transições do AFD

�VEJA O INTERPRETADOR UNIVERSAL DE TABELAS

51

SAIR

ANTERIOR


ROTEIRO


� Os algoritmos vistos neste trabalho realizam a transformação de uma ER em um AFD. Como parte complementar, foi implementada a transformação do AFD resultante em uma função na linguagem de programação Pascal. Estas transformação éequivalente nos dois protótipos que implementam os algoritmos.

� A função é gerada para uma unit da linguagem de programação Pascal e esta unit poderá ser utilizada em um programa desta linguagem

�EXEMPLO DE PROGRAMA QUE DECLARA FUNÇÃO

52

SAIR

ANTERIOR


ROTEIRO

ESPECIFICAÇÃO DOS PROTÓTIPOS

�PROTÓTIPO DE [HOP1979]�PROTÓTIPO DE [SIL2000]

�OS ALGORITMOS FORAM IMPLEMENTADOS SEPARADAMENTE COM O OBJETIVO DE SIMPLIFICAR O ENTENDIMENTO DE CADA UM.

53

SAIR

ANTERIOR


ROTEIRO

ESPECIFICAÇÃO DOS PROTÓTIPOS – HOP1979

ENTRADA DE DADOS

APLICAÇÃO DO ALGORITMO DE [HOP1979]

GERAÇÃO DA FUNÇÃO PASCAL

54

SAIR

ANTERIOR


ROTEIRO

ESPECIFICAÇÃO DOS PROTÓTIPOS – HOP1979

Entrada do Alfabeto e daER

Geração do AFε

Geração do AFND

Geração do AFD

Função Pascal

FASE 1

FASE 2

FASE 3

FASE 4

FASE 5

55

SAIR

ANTERIOR


ROTEIRO

ESPECIFICAÇÃO DOS PROTÓTIPOS – SIL2000

ENTRADA DE DADOS

APLICAÇÃO DO ALGORITMO DE [SIL2000]

GERAÇÃO DA FUNÇÃO PASCAL

56

SAIR

ANTERIOR


ROTEIRO

ESPECIFICAÇÃO DOS PROTÓTIPOS SIL2000

Entrada do Alfabeto e da ER

Geração da expressão pós-fixadaatravés da LLC

Geração da "Tabela doDesmonte"

Geração do GT

Geração do AFD

Função Pascal

FASE 1

FASE 2

FASE 3

FASE 4

FASE 5

FASE 6

57

SAIR

ANTERIOR


ROTEIRO

APRESENTAÇÃO DOS PROTÓTIPOSTELA PRINCIPAL ([HOP1979])

58

SAIR

ANTERIOR


ROTEIRO

APRESENTAÇÃO DOS PROTÓTIPOSENTRADA DE DADOS

59

SAIR

ANTERIOR


ROTEIRO

APRESENTAÇÃO DOS PROTÓTIPOSPROCESSAR EXPRESSÃO REGULAR

60

SAIR

ANTERIOR


ROTEIRO

APRESENTAÇÃO DOS PROTÓTIPOSVISUALIZAR FUNÇÃO

61

SAIR

ANTERIOR


ROTEIRO

APRESENTAÇÃO DOS PROTÓTIPOSFUNÇÃO PASCAL

62

SAIR

ANTERIOR


ROTEIRO

APRESENTAÇÃO DOS PROTÓTIPOSAFε

63

SAIR

ANTERIOR


ROTEIRO

APRESENTAÇÃO DOS PROTÓTIPOSAFND

64

SAIR

ANTERIOR


ROTEIRO

APRESENTAÇÃO DOS PROTÓTIPOSAFND – FASES DA δ

65

SAIR

ANTERIOR


ROTEIRO

APRESENTAÇÃO DOS PROTÓTIPOSAFD

66

SAIR

ANTERIOR


ROTEIRO

APRESENTAÇÃO DOS PROTÓTIPOSTABELA DE TRANSIÇÕES DO AFD

67

SAIR

ANTERIOR


ROTEIRO

APRESENTAÇÃO DOS PROTÓTIPOSTELA PRINCIPAL ([SIL2000])

68

SAIR

ANTERIOR


ROTEIRO

APRESENTAÇÃO DOS PROTÓTIPOSENTRADA DE DADOS

69

SAIR

ANTERIOR


ROTEIRO

APRESENTAÇÃO DOS PROTÓTIPOSPROCESSAR EXPRESSÃO

70

SAIR

ANTERIOR


ROTEIRO

APRESENTAÇÃO DOS PROTÓTIPOSEXPRESSÃO PÓS-FIXADA

71

SAIR

ANTERIOR


ROTEIRO

APRESENTAÇÃO DOS PROTÓTIPOSVISUALIZAR FUNÇÃO GERADA

72

SAIR

ANTERIOR


ROTEIRO

APRESENTAÇÃO DOS PROTÓTIPOS FUNÇÃO PASCAL

73

SAIR

ANTERIOR


ROTEIRO

APRESENTAÇÃO DOS PROTÓTIPOSTABELA DO DESMONTE

74

SAIR

ANTERIOR


ROTEIRO

APRESENTAÇÃO DOS PROTÓTIPOSGT

75

SAIR

ANTERIOR


ROTEIRO

APRESENTAÇÃO DOS PROTÓTIPOSAFD

76

SAIR

ANTERIOR


ROTEIRO

APRESENTAÇÃO DOS PROTÓTIPOSTABELA DE TRANSIÇÕES DO AFD

77

SAIR

ANTERIOR


ROTEIRO

COMPARAÇÃO DOS ALGORITMOS

�CRITÉRIOS UTILIZADOS:� TEMPO DE EXECUÇÃO (% DE EFICIÊNCIA DE UM ALGORITMO EM RELAÇÃO AO OUTRO)

� UTILIZAÇÃO DE MEMÓRIA (% DE EFICIÊNCIA DE UM ALGORITMO EM RELAÇÃO AO OUTRO)

� OTIMIZAÇÃO DE RESULTADOS

78

SAIR

ANTERIOR


ROTEIRO

COMPARAÇÃO DOS ALGORITMOSTEMPO DE EXECUÇÃO

% d e Ef ic ê n c ia

0 ,0 0 %

1 0 0 ,0 0 %

2 0 0 ,0 0 %

3 0 0 ,0 0 %

4 0 0 ,0 0 %

5 0 0 ,0 0 %

6 0 0 ,0 0 %

1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 1 2 2

Ex p r e s s õ e s Re g u la r e s

%

S IL 2 0 0 0

HO P1 9 7 9

79

SAIR

ANTERIOR


ROTEIRO

0102030405060708090

100

TESTE 1 TESTE 2 TESTE 3 MÉDIA

[HOP1979][SIL2000]

COMPARAÇÃO DOS ALGORITMOSUTILIZAÇÃO DE MEMÓRIA

80

SAIR

ANTERIOR


ROTEIRO

05

1015202530354045

TESTE1

TESTE3

TESTE5

TESTE7

[HOP1979][SIL2000]

COMPARAÇÃO DOS ALGORITMOSOTIMIZAÇÃO DE RESULTADOS

MENOR

MAIOR

81

SAIR

ANTERIOR


ROTEIRO

COMPARAÇÃO DOS ALGORITMOS

�Para o critério TEMPO DE EXECUÇÃO, o algoritmo de [SIL2000] mostrou-se amplamente superior ao algoritmo de [HOP1979]

�Idem para o critério UTILIZAÇÃO DE MEMÓRIA

�No critério OTIMIZAÇÃO DE RESULTADOS foi utilizada a contagem dos estados do AFD resultante. Na quase totalidade dos testes o algoritmo de [SIL2000] se mostrou superior.

82

SAIR

ANTERIOR


ROTEIRO

�Durante este trabalho foram vistos alguns conceitos e técnicas para transformação de uma ER em AFD

�Também foram vistos os algoritmos de [HOP1979] e [SIL2000]

�Foram feitas considerações sobre cada algoritmo e comparações entre eles

CONCLUSÃOCONCLUSÃOCONCLUSÃO

Documents

PROT ÓTIPO PARA TRANSFORMA ÇÃO DE UMA …dsc.inf.furb.br/arquivos/tccs/apresentacoes/2000-2ronaldglatzap.pdf · ROTEIRO Aqui serão apresentados alguns conceitos ... TABELA DO