Compiladores Aula 05 Funcionamento da construção de Thompson (ER para AFND)

Prévia do material em texto

# Compiladores #
Aula 05 - Construção de Thompson
(ER para AFND)
Prof. Leinylson Fontinele Pereira
Construção de Thompson
❑ Expressão Regular → AFND
❑ Cada ER básica se traduz em um AFND
❑ Pode-se agregar os AFND conforme se 
agregam as ERs
❑ Cada AFND tem exatamente um estado 
de partida e um estado final
18/09/2018 Aula 01 - Introdução 4
Reconhecedores básicos
18/09/2018 Aula 01 - Introdução 5
Reconhecedores básicos
18/09/2018 Aula 01 - Introdução 6
Reconhecedor de Alternativa
18/09/2018 Aula 01 - Introdução 7
Reconhecedor de Concatenação
18/09/2018 Aula 01 - Introdução 8
AFND reconhecedor do Fechamento de Kleene
18/09/2018 Aula 01 - Introdução 9
Qual o problema de AFND?
18/09/2018 Aula 01 - Introdução 10
❑ Pontos positivos
❑ Bastante poderoso para implementar ERs
❑ Aplicação trivial: ERs → AFNDs → Full AFND (léxico)
❑ Pontos negativos (Problema)
❑ ε-transições
❑ Várias transições de saída com o mesmo símbolo
Fácil p/ a fase de projeto, difícil de implementar!
18/09/2018 Aula 01 - Introdução 11
Exercício 1
18/09/2018 Aula 01 - Introdução 12
Construir um AFND que reconheça (a|b)*abb
Estrutura de um Compilador em etapas
18/09/2018 Aula 01 - Introdução 13
Próxima aula...
❑ Algoritmo de Subconjuntos
❑ AFND para AFD
18/09/2018 Aula 01 - Introdução 14
Aula disponível no SlideShare!
https://pt.slideshare.net/leinylson/presentations