Seminário de Qualificação de Mestrado de Raul Lopes, dia 15/05/17, as 13:30 no DECOM.

Seminário de Qualificação de Mestrado de Raul Felipe Pimenta Lopes, dia 15/05/17, as 13:30 no DECOM.

Titulo: Verificação formal de algoritmos de parsing baseados em derivadas de expressões regulares.

Resumo:
Apresentamos a formalização, na linguagem Agda, de algoritmos para parsing de expressões regulares baseados nas derivadas de Brzozowski e Antimirov. Os algoritmos formalizados produzem como resultado uma prova de que a string de entrada é aceita ou não pela expressão regular em questão. Uma ferramenta para casamento de padrão usando expressões regulares, similar ao conhecido GNU grep, foi desenvolvida a partir dos algoritmos verificados e submetida a testes para verificar a eficiência da mesma frente a soluções conhecidas na literatura.