Journal of Functional Programming

Functional pearls

FUNCTIONAL PEARL Parallel Parsing Processes

a1 Department of Computing Science, Chalmers University of Technology, Gothenburg, Sweden (email:

Article author query
claessen k   [Google Scholar] 


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.