Journal of Functional Programming



Functional pearls

FUNCTIONAL PEARL Parallel Parsing Processes


KOEN CLAESSEN a1
a1 Department of Computing Science, Chalmers University of Technology, Gothenburg, Sweden (email: koen@cs.chalmers.se)

Article author query
claessen k   [Google Scholar] 
 

Abstract

We derive a combinator library for non-deterministic parsers with a monadic interface, by means of successive refinements starting from a specification. The choice operator of the parser implements a breadth-first search rather than the more common depth-first search, and can be seen as a parallel composition between two parsing processes. The resulting library is simple and efficient for “almost deterministic” grammars, which are typical for programming languages and other computing science applications.