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

Examensarbete för masterexamen

Använd denna länk för att citera eller länka till detta dokument:
Ladda ner:
Fil Beskrivning StorlekFormat 
185016.pdfFulltext911.29 kBAdobe PDFVisa
Typ: Examensarbete för masterexamen
Master Thesis
Titel: An Agda proof of the correctness of Valiant’s algorithm for context free parsing
Författare: Bååth Sjöblom, Thomas
Sammanfattning: 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: Data- och informationsvetenskap;Computer and Information Science
Utgivningsdatum: 2013
Utgivare: Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)
Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)
Samling:Examensarbeten för masterexamen // Master Theses

Materialet i Chalmers öppna arkiv är upphovsrättsligt skyddat och får ej användas i kommersiellt syfte!