In English

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

Thomas Bååth Sjöblom
Göteborg : Chalmers tekniska högskola, 2013. 71 s.
[Examensarbete på avancerad nivå]

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.

Nyckelord: Dependently typed programming, Formal proof, Agda, Valiant, Parallel parsing, Transitive closure, Nonassociative multiplication, Algebra



Publikationen registrerades 2013-10-09. Den ändrades senast 2013-10-09

CPL ID: 185016

Detta är en tjänst från Chalmers bibliotek