A Combinator based, certifiable, parsing framework

Abstract

Parsers are ubiquitous software, much more common than one would normally take notice. Parsing spreads from simple command line functionalities to natural languages pro- cessing, to language composition. Parsing is also somewhat regarded as a solved problem in computation. However, that does not translate into reality, especially when consider- ing their implementations, which can be complex and difficult to maintain. In the last decades, multiple tools have surged aiming to improve the process of parsing, from the now well established parser generators to recent interactive parsing frameworks, which try to reduce the knowledge requirements for the specification of parsers. Although these tools have their own merits, very little effort was put into their standardization and formal reliability. We try to address these issues by implementing a reliable and flexible parsing framework that is composed of a small and extensible library of parser combinators, and a reliable, easily verifiable, parser generator based on the standardized meta-syntax of the extended Backus-Naur notation.We also provide valuable insight into the implementation of the General LL parsing technique in a purely functional setup.