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.

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

Parses an alphabetic character, or a digit

Matches any lexeme, and returns it.

Parses a digit.

Parses end-of-file

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

$err : a parser that always returns an error

Parses an alphabetic character.

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

Parses a single space

Parses zero or more spaces

Parses one or more spaces

Parses the tab character.

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.

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> 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> 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 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 c) : creates a parser that parses and returns char c.

(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? 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 p) : Creates a parser that parses with p and returns its result, but consumes no input.

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

(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 p) : like (many p), but creates a parser that parses with p one or more times.

(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 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 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 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? | (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? any): returns #t if the argument is an input, returned by make-input/source*.

(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 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 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 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.

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.

Like sepBy1, but parses zero or more times.

(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! 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 p) : creates a parser that parses with p multiple times, but returns only ().

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

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

(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 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>)