PPGCC - Programa de Pós-graduação em Ciência da Computação

URI permanente desta comunidadehttp://www.hml.repositorio.ufop.br/handle/123456789/596

Navegar

Filtros

20181

Configurações

Autor: search.filters.author.Lopes, Raul Felipe PimentaTem arquivos: Sim

Resultados da Pesquisa

Agora exibindo 1 - 1 de 1
  • Nenhuma Miniatura Disponível
    Item
    Certified derivative-based parsing of regular expressions.
    (2018) Lopes, Raul Felipe Pimenta; Ribeiro, Rodrigo Geraldo; Figueiredo, Carlos Camarão de; Malaquias, José Romildo; Reis, Leonardo Vieira dos Santos; Ribeiro, Rodrigo Geraldo
    Parsing is pervasive in computing and fundamental in several software artifacts. This dissertation reports the rst step in our ultimate goal: a formally veri ed toolset for parsing regular and context free languages based on derivatives. Speci cally, we describe the formalization of Brzozowski and Antimirov derivative based algorithms for regular expression parsing, in the dependently typed language Agda. The formalization produces a proof that either an input string matches a given regular expression or that no matching exists. A tool for regular expression based search in the style of the well known GNU Grep has been developed using the certi ed algorithms. Practical experiments conducted using this tool are reported.