----
title: klipspringer – a combinatorial parser generator
SPDX-FileCopyrightText: 2025 Norman Gray <https://nxg.me.uk>
SPDX-License-Identifier: BSD-2-Clause


This is a simple implementation of a combinatorial parser.

In the type declarations below,

  * `LEXEME?` is whatever lexemes the functions are expected to parse;
     ie, it is whatever `lexeme-source?` returns
  * `LEXEME-SOURCE?` is a function `(-> (or/c lexeme? eof/c))`.
     This consumes the source – that is, each time this function is
     called, it returns a lexeme which it will not return again.
     This function is supplied by the user of the library.
     The function must return `#<eof>` when the list of lexemes is exhausted.
  * `VALUE?` is whatever the results are (eg, xexprs)
  * `PARSER?` is `(input? -> (or/c consumed? empty?)`

This module is an implementation of the
‘parsec’ Haskell library described in [leijen01][],
which in turn expands on the general description of this class of parsers in [hutton96][].
The interface, however, _closely_ follows that of the Racket
implementation of this approach,
[parsack](https://docs.racket-lang.org/parsack/index.html).
There is an alternative Racket implementation called
[megaparsack](https://docs.racket-lang.org/megaparsack/index.html).

The [klipspringer](https://en.wikipedia.org/wiki/Klipspringer)
is a small robust (and unutterably cute) antelope.  That is, it is of the
same bovid family as the bison and the yak.

![A friendly Klipspringer](klipspringer.jpg)

References:

    @techreport{hutton96,
      author = {Graham Hutton and Erik Meijer},
      institution = {University of Nottingham},
      title = {Monadic Parser Combinators},
      url = {https://nottingham-repository.worktribe.com/output/1024440},
      year = 1996}

    @techreport{leijen01,
      author = {Daan Leijen and Erik Meijer},
      institution = {University of Utrecht},
      note = {Cited as 'Electronic Notes in Theoretical Computer Science 41 No. 1 (2001)',
        but that doesn't seem to actually exist. I could find it only at Researchgate},
      title = {Parsec: A Practical Parser Library},
      url = {https://www.researchgate.net/publication/2534571_Parsec_Direct_Style_Monadic_Parser_Combinators_For_The_Real_World},
      year = 2001}

[hutton96]: https://nottingham-repository.worktribe.com/output/1024440
[leijen01]: https://www.researchgate.net/publication/2534571_Parsec_Direct_Style_Monadic_Parser_Combinators_For_The_Real_World

Basic operations
================

**This documentation is _very_ flimsy, so far.**

Right now, the best documentation is the implementation this is based
on, namely [Racket parsack](https://docs.racket-lang.org/parsack/index.html).
I haven't implemented everything there, but the functions I have
implemented, should have the same semantics.

This module is designed for internal use only so far, but I expect to
make it a little more public in time, after it has settled down a bit.

A parser is a function that consumes a sequence of lexemes, and
returns a parse result.  The result is not constrained by the
functions here, but depends on the outputs of the functions bound to
the individual parsers.

    (parse-result
      (>>= (char #\()
           (λ (skip1)
             (>>= $letter
                  (λ (x)
                    (>>= (char #\))
                         (λ (skip2)
                           (return x)))))))
      "(a)")

    => #\a