The Design of a Verified Derivative-Based Parsing Tool for Regular Expressions
Elton M. Cardoso, Maycon Amaro, Samuel da Silva Feitosa, Leonardo Vieira dos Santos Reis, André Rauber Du Bois, Rodrigo Geraldo Ribeiro · CLEI electronic journal · 2021
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 with the certified algorithms. Practical experiments conducted with this tool are reported.