In a strict language, where creating the entire input list of tokens in one shot may be infeasible, we can use a lazy "callback" kind of architecture instead. The lexer returns a single token at a time, together with a continuation. The next parser is responsible for pulling on the token stream, applying the continuation where necessary.

This Parser datatype is a specialised parsing monad with error reporting. This version is specialised to pre-lexed String input, where the lexer has been written to yield a LexReturn.

A return type like Either, that distinguishes not only between right and wrong answers, but also has commitment, so that a failure cannot be undone. This should only be used for writing very primitive parsers - really it is an internal detail of the library. The z type is the remaining unconsumed input.

Apply a parser to an input token sequence.

Simply return the next token in the input tokenstream.

Succeed if the end of file/input has been reached, fail otherwise.

Return the next token if it satisfies the given predicate.

p onFail q means parse p, unless p fails, in which case parse q instead. Can be chained together to give multiple attempts to parse something. (Note that q could itself be a failing parser, e.g. to change the error message from that defined in p to something different.) However, a severe failure in p cannot be ignored.

Push some tokens back onto the front of the input stream and reparse. This is useful e.g. for recursively expanding macros. When the user-parser recognises a macro use, it can lookup the macro expansion from the parse state, lex it, and then stuff the lexed expansion back down into the parser.