An Agda proof of the correctness of Valiant’s algorithm for context free parsing

Abstract

Parsing is an important problem with applications ranging from compilers to bioinformatics. To perform the parsing more quickly, it would be desirable to be able to parse in parallel. Valiant’s algorithm [Valiant, 1975] is a divide and conquer algorithm for parsing and can be used to perform a large part of the work in parallel. It is fairly easy to implement in a functional programming languages, using pattern matching. Agda is a dependently typed functional programming language that doubles as a proof assistant and is hence very suitable for implementing and proving the correctness of Valiant’s algorithm. In this thesis, we provide a very natural specification for the parsing problem and prove that it is equivalent to the specification of the transitive closure used in [Valiant, 1975], that is further removed from both parsing and proving. We compare the two specifications and use our specification to derive Valiant’s algorithm. We then implement it in Agda and prove our implementation correct (we prove that it satisfies our specification). We also give short introductions to parsing, programming and proving with Agda and to using algebraic structures in Agda.