# klipspringer – a combinatorial parser generator

Parser generator

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. There is an alternative Racket implementation called megaparsack.

The 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

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}

# Basic operations

This documentation is very flimsy, so far.

Right now, the best documentation is the implementation this is based on, namely Racket parsack. 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

## Functions

Index:

- $alphaNum
- $any
- $digit
- $eof
- $eol
- $err
- $letter
- $newline
- $space
- $spaces
- $spaces1
- $tab
- $wordbreak
- $wordbreak1
- <!>
- <any>
- <or>
- >>
- >>=
- between
- char
- get-parser-description
- lexeme-source?
- lookAhead
- many
- many/n
- many1
- noneOf
- oneOf
- parse-result
- parse-result2
- parser-compose
- parser-input?
- parser-one
- parser-seq
- return
- satisfy
- satisfy/char
- sepBy
- sepBy1
- set-parser-description!
- skipMany
- skipMany1
- string
- string/ci
- try

### $alphaNum

Parses an alphabetic character, or a digit

### $any

Matches any lexeme, and returns it.

### $digit

Parses a digit.

### $eof

Parses end-of-file

### $eol

Parses end of line. `$eol` succeeds on "n", "r", "rn", or "nr". See also `$newline`.

### $err

$err : a parser that always returns an error

### $letter

Parses an alphabetic character.

### $newline

Parses newline char. This is the singular # character. See also $eol.

### $space

Parses a single space

### $spaces

Parses zero or more spaces

### $spaces1

Parses one or more spaces

### $tab

Parses the tab character.

### $wordbreak

Matches zero or more ‘word break’ codepoints. This is almost the same as `$spaces`, except that it excludes non-breaking spaces. This matches the Unicode/ICU `u_isWhitespace()` function, and (thus) the Java `Character.isWhitespace()` function.

### $wordbreak1

Matches one or more ‘word break’ codepoints. This is almost the same as `$spaces`, See `$wordbreak`.

### <!>

`(<!> p [q])` : Creates a parser that errors if `p` successfully parses input, otherwise parses with `q`. The parser `q` defaults to `$any`.

### <any>

`(<any> p ...)` : Creates a parser that tries the given parsers in order, returning with the result of the first successful parse, even if no input is consumed. Produces an error if it not given at least one parser. See `<or>` for a related, alternative parser.

Example:

     > (parse-result (<any> $letter $digit) "1")
     #\1

Notes:

- `<any>` immediately returns when it encounters a successful parse, even if the parse consumed no input.

  Example:

  > (parse-result (`any` (return null) $digit) "1") '()

- See also `<or>`, a related parser that continues to try subsequent parsers so long as each of the previous parsers consumes no input, even if one of the previous parsers returns successfully.

  Example:

  > (parse-result (`or` (return null) $digit) "1") #1

### <or>

`(<or> p ...)`: Creates a parser that tries the given parsers in order, returning with the result of the first parser that consumes input.

If no parsers consume input, then `<or>` backtracks to return the result of the first success.

### >>

`(>> p q)` : Equivalent to `(>>= p (λ (x) q))` where x is not in q. Creates a parser that first parses with p, and if successful, ignores the result, then parses with q.

Example:

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

### >>=

`(>>= p f)` : (parser? (value? -> parser?) -> parser?). This is the monadic bind operator for parsers.

Creates a parser that first parses with `p`; If `p` fails, the error result is returned.

Otherwise, the parse result is passed to `f`, and we continue parsing with the parser created from applying `f`.

That is, in `(>>= p f)`, `p` is a parser : `(parser-input? -> result?)`; `f` is a function : `(value? -> parser?)`, which acts on the value parsed by `p`, to produce a parser.

Example:

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

    => #\a

### between

`(between open close p)` :Creates a parser that parses with p only if it’s surrounded by open and close. Only the result of p is returned.

### char

`(char c)` : creates a parser that parses and returns char c.

### get-parser-description

`(get-parser-description p)` : given a parser `p`, retrieve its self-description. This is used in error messages, but might be useful for other debugging tasks.

### lexeme-source?

`(lexeme-source? x)` : True if the argument is a procedure which can be called with zero arguments, returning a lexeme at a time. When the source of lexemes is exhausted, the function should return `#<eof>`.

The lexemes here are whatever the parser expects to consume. The parsers predefined in this module expect to process characters or Unicode codepoints, but the framework is not restricted to that.

A `lexeme-source?` is `(-> lexeme?)`, but we permit it to have optional arguments, eg, for debugging. If the function can be given an argument `'location`, upon which it will return a string indicative of a current location, then that will be used when reporting errors.

### lookAhead

`(lookAhead p)` : Creates a parser that parses with p and returns its result, but consumes no input.

### many

`(many p)` : Creates a parser that parses with p zero or more times. It returns a list of objects parsed by `p`.

### many/n

`(many/n p n [:max max])` : like `(many p)`, but creates a parser that parses with `p` at least `n` times. If `:max` is present, then this sets a maximum number of matches.

### many1

`(many1 p)` : like `(many p)`, but creates a parser that parses with p one or more times.

### noneOf

`(noneOf str)` : Creates a parser that consumes and returns one character if the character does not appear in str. `str` may be a UTF-8 string, and the arguments may be characters or (integer) codepoints.

### oneOf

`(oneOf str)` : Creates a parser that consumes and returns one character if the character appears in str. `str` may be a UTF-8 string, and the arguments may be characters or (integer) codepoints.

### parse-result

`(parse-result p src [:on-error handler])`: parses the given source with parser `p`, and returns the successful result.

The `src` may be a `string?` or a `lexeme-source?`. The `lexeme-source?` argument is as documented in the predicate function. The function `make-unicode-reader/file` is an example of such a function.

If the parse fails, then this procedure raises an exception with subtag `klipspringer`. If instead the keyword `:on-error` is present and provides a handler procedure, then this procedure returns, instead of the result of the parse, the result of applying the handler procedure to three arguments, namely a description of the parser that failed, an error message, and an indication of the failure location in the input.

### parse-result2

`(parse-result2 p src [:on-error handler]) -> <any> input?` : parses the given source, and returns, as multiple values, the successful result and a new input object which represents the current state of the input.

If the parse fails, then this procedure raises an exception with subtag `klipspringer`. If instead the keyword `:on-error` is present and provides a handler procedure, then this procedure returns, as multiple values, `#f`, and the result of applying the handler procedure to three arguments, namely a description of the parser that failed, an error message, and an indication of the failure location in the input.

Otherwise, see `parse-result`.

### parser-compose

`(parser? | (var '<- parser?)) ... -> parser?` : Compose a sequence of parsers with `>>=`. Parsers wrapped in `var <- parser` will bind the parse result to the given variable. For example,

    (parser-compose (char #\[)
                    (x <- $letter)
                    (y <- $letter)
                    (char #\])
                    (return (list x y)))

parses `"[ab]"` to `'(#\a #\b)`.

### parser-input?

`(parser-input? any)`: returns `#t` if the argument is an input, returned by `make-input/source*`.

### parser-one

`(parser-one p ...)` where `p` is either a parser or `(~> parser?)` : Combines parsers but only return the result of the parser wrapped with `~>`. Precisely one parser must be wrapped with `~>`.

### parser-seq

`(parser-seq p q)` is syntactically equivalent to `(parser-compose (x <- p) (y <- q) (return (list x y)))`. Any parser wrapped in `(~ ...)` doesn't pass on the result to the final list.

If the keyword `:combine-with` is present, then its value specifies a function which is applied to the list of results, instead of `list`.

If the keyword `:description` is present, then its value gives a brief name for the parser, used in error messages.

### return

`(return v [:new-input proc])` : creates a parser that consumes no input and always succeeds, returning `v`.

If `new-input` is present, then it is a function which, given an `input?`, returns a new `input?`, which is the one subsequently used.

### satisfy

`(satisfy pred? [description])` : creates a parser which consumes and returns one lexeme if it satisfies `pred?`. For example, `$letter` is equivalent to `(satisfy char-alphabetic?)`.

If the argument `description` is present, then it is a compact description of the parser, for use in error messages.

### satisfy/char

Like `satisfy`, except that the lexeme is additionally required to be a char or integer. The predicate must accept both chars and integers as argument.

### sepBy

Like sepBy1, but parses zero or more times.

### sepBy1

`(sepBy1 p sep)` : creates a parser that repeatedly parses with p one or more times, where each parse of p is separated with a parse of sep. Only the results of p are returned.

### set-parser-description!

`(set-parser-description! parser? string?)` : Sets a parser's self-description. It may be useful to set this, since the framework may use this when generating error messages.

### skipMany

`(skipMany p)` : creates a parser that parses with `p` multiple times, but returns only `()`.

### skipMany1

`(skipMany1 p)` : creates a parser that parses with `p` at least once, but returns only `()`.

### string

`(string str)` : Creates a parser that parses and returns `str` as a list of codepoints.

### string/ci

`(string/ci str)` : Creates a parser that parses and returns `str` as a list of chars. The comparison is done case-insensitively, and it is the lowercased codepoints of the input string that are returned.

### try

`(try p)` : lookahead function. Creates a parser that tries to parse with `p` but does not consume input if `p` fails.

For example:

    > (parse-result (string "ab") (open-input-string "ac"))
    (consumed #<error>)
    > ((try (string "ab")) (open-input-string "ac"))
    (empty #<error>)

Norman
2026 August 02