In a classic 1968 paper, Ken Thompson showed how to translate regular expressions into non-deterministic finite automata, and how to implement the automata using machine-level programming on the IBM 7094.  His implementation uses two dynamic lists -- or sets, really -- of subroutine calls, one related to active states for the current character of input, and another related to the next character.

Koen Claessen, in a 2004 functional pearl, describes a set of parser combinators that explore alternatives in parallel rather than using backtracking, and read the input token by token.  More than a mere toy, this set of combinators performs with acceptable efficiency in the presence of non-determinism and supports incremental reading of the input without needing to rely on lazy streams, making it useful in many practical settings.

Claessen implements the combinators in terms of a free monad of parsing actions, with some combinators interpreting the language of actions.  I shall show that there is an alternative implementation in terms of continuations (different from the partially continuation-based implementation considered by Claessen) that is purely applicative, and can be related by data refinement with the implementation based on a free monad.  A step of defunctionalisation produces an implementation that maintains explicit lists of alternatives to be explored for the current token and for the next, reflecting in an appealing way Thompson's matcher for regexps.

[1] Ken Thompson, "Programming Techniques: Regular expression search algorithm," CACM 11, 6 (June 1968), pp. 419--22.

[2] Koen Classen, "Functional Pearl: Parallel parsing processes," JFP 14, 6 (2004), pp. 741--57.