Parsnip

Monadic parser combinator library.

Conventional parsers are modeled as a two-stage process: a scanner that takes characters and produce tokens, and a parser that takes tokens and produce syntax trees. Monadic parsers instead model parsers as smaller parsers that can compose together, much like the procedures of a conventional program.

Other parser combinator libraries I've found for Common Lisp are either too macro-heavy for me, or warn that they are not production-ready. I don't trust third-party libraries that don't trust themselves, and so I've made my own, going for a simple interface targeted for public consumption.

Parsnip targets user-facing compilers, interpreters, or other readers of character-based languages, where programs would like to recover from or give insight about parser errors. Parsnip does not target performance-intensive or byte-based decoders, such as those used in network stacks, or JSON/XML decoders for request data for high-performance web applications.

Contributions

Any comments, questions, issues, or patches are greatly appreciated! I do my main development on Sourcehut, with a mailing list and issue tracker.

Usage

Parsnip is available on Quicklisp:

(ql:quickload :parsnip)

Parsnip can also be installed locally. Make sure to also install the sole dependency Alexandria:

$ cd ~/common-lisp/ # Or wherever you store your definitions
$ git clone https://git.sr.ht/~shunter/parsnip

(require :parsnip)
(use-package :parsnip)

;; digit := [0-9]
(defparser one-digit ()
  (char-if #'digit-char-p))

(defparser digits ()
  (collect1 'one-digit))

;; whole-part := digit+
(defparser whole-part ()
  (let! ((digits 'digits))
    (ok (parse-integer (coerce digits 'string)))))

;; decimal-part := '.' [0-9]+
(defparser decimal-part ()
  (let! ((digits (progn! (char-of #\.) 'digits)))
    (ok (/ (parse-integer (coerce digits 'string))
           (expt 10 (length digits))))))

;; number := whole-part [ decimal-part ]
(defparser decimal-number ()
  (let! ((whole-value 'whole-part)
         (decimal-value (or! 'decimal-part (ok 0))))
    (ok (+ whole-value decimal-value))))

(defun parse-from-string (parser string)
  (with-input-from-string (stream string)
    (parse parser stream)))

(parse-from-string 'decimal-number "123.47") ;; => 12347/100

Parsnip aims to provide rich information for parsers aimed at end-users:

(use-package :xyz.shunter.parsnip.examples.json)

;; bad.json: [10,20,,]
(with-open-file (s "/tmp/bad.json")
  (decode-json s))
/tmp/bad.json:1:7: Expected (#\f #\n #\t #\{ #\[
                             (:integer . 10) #\") on #<STREAM>
[Condition of type PARSER-ERROR]

(with-open-file (s "/tmp/bad.json")
  (handler-case (decode-json s)
    (parser-error (c)
      (values (parser-error-line c)
              (parser-error-column c)))))
=> 1
   7

(handler-case (decode-json-from-string "[10,20,{\"foo\":\"bar\",}]")
  (parser-error (c)
    (format t "~A~%" c)
    (parser-error-return-trace c)))
NIL:1:20: Expected #\" on #<STRING-INPUT-STREAM>
((xyz.shunter.parsnip.examples.json::value 1 0)
 (xyz.shunter.parsnip.examples.json::json-array 1 0)
 (xyz.shunter.parsnip.examples.json::value 1 7)
 (xyz.shunter.parsnip.examples.json::json-object 1 7)
 (xyz.shunter.parsnip.examples.json::json-string 1 20))

The test suite shows how each function works, and how it's expected to perform.

Is this Production-ready?

After a couple months of working on this project in my spare time, I believe it is ready for public use. However, you may have certain requirements for your own project which would hold you off from using this library over something else:

• API Stability. I've tried and switched through a few different methods for parsing data, including value-based evaluation and continuations. Through experimentation, I've found that the external API remains largely the same. I'll feel confident enough in this when I create my own decoder on-top of this library.
• Robustness. I've targeted at least 95% coverage reported by sb-cover while developing this API, to limit erroneous behavior stemming from edge cases. Every release includes a code coverage report, and every push to the repository triggers an automated system test.
• Development Speed. Something similar to the example json decoder can be reasonably written within an afternoon. During anothe one of my projects, I was able to write a parser that describes notes, durations, note dots, pitches, beams, chords, and measure bars, within a similar amount of time. I've designed the API to match CL's standard library as closely as possible to make it as learnable as possible.
• Maturity. The best solution for this that I can think of is Time * Exposure. I also appreciate multiple eyes looking at this project. Any comments, questions, and suggestions are well appreciated :)

Breaking Changes

When the library reaches 1.0, I need to consider what parts of the library to solidify. I recognize these as breaking changes:

• Removing functions or macros
• Removing parameters from a function or macro.
• Changing a function to a macro, or vice-versa.
• Changing the specified behavior of a pre-existing function or macro, given the same parameters.
• Changing, adding, or removing any package names or nicknames.

I recognize these as non-breaking changes:

• Extending functions or macros with on-required parameters. The default behavior should still match
• Adding new external functions, macros, or other symbols to the package.
• Changing the behavior of pre-existing function or macro, if the original behavior was a bug.
• Adding new dependencies to the system (though I hardly foresee this happening).

Examples

The JSON example matches close to the grammar notation of the RFC8259 JSON specification. Outside of a couple outliers (e.g. the value definition is moved to the end), the code is laid out nearly section-by-section as stated in the RFC.

The Tiny C example is an extremely bare-bones subset of C, with a single primitive integer type and limited mechanisms. It demonstrates an example of what patterns can be used to parse C-family grammars with parser combinators.

Concepts

Parsers are given four "tracks" of continuations: success/failure with consumed input, and "empty" success/failure (that is, without consumed output). Most combinators that handle failures, only handle empty failures. The two exceptions are handle-rewind and try!, which saves the input stream's position and rewinds to an "empty" state before handling the failure. A consumed success only matters to retrack all future empty continuations to consumed continuations (so a consumed success followed by an empty failure counts as a consumed failure).

This model is used by Haskell's parsec and megaparsec libraries. I tried to use a simple ok/fail model, but after writing the example JSON and Tiny C files, found that this model works best.

API

[Function] ok value => parser

Return a parser that consumes nothing and returns the given value:

(with-input-from-string (s "abc123")
  (list (parse (ok :hello) s)
        (alexandria:read-stream-content-into-string)))

=> (:hello "abc123")

[Function] fail expected &optional trace => parser

Return a parser that consumes nothing and fails, reporting the expected value.

[Function] char-if predicate &optional message => char-parser

Return a parser that consumes a character that satisfies the given predicate.

[Function] char-of char &optional message => char-parser

Return a parser that consumes the given character.

[Function] char-in charbag &optional message => char-parser

Return a parser that consumes a character in the given character bag.

[Function] string-of string &optional message => string-parser

Return a parser that consumes the given simple string. This parser may have consumed input on a failure.

[Function] eof &optional value => parser

Return a parser that consumes nothing and returns the given value (or nil) if the input stream is exhausted.

[Function] flatmap function parser => parser

Return a new parser that applies the given function to the parser's result, and then runs the parser the function returns. This function forms the basis of stringing multiple parsers together.

[Macro] let! (&rest bindings) &body body => parser

Return a parser that runs all given parsers, binds them all to their variables, evaluates the body, and then runs the parser the body returns.

[Function] handle parser handler => parser

Return a new parser that, on failure, applies the handler function to the parser's expected value and parse trace (as a list), and then runs the parser the handler returns.

handle does not handle partial-parse failures, which can be recovered from via handle-rewind.

[Function] handle-rewind parser handler => parser

Return a new parser that saves the stream's current position and, on failure, rewinds the stream, applies the handler function to the parser's expected value and parse trace (as a list), and then runs the parser the handler returns.

handle-rewind only works when the parser is given a seekable stream.

[Function] try! parser => parser

Return a new parser that saves the stream's current position and, on failure, rewinds the stream before passing the failure down.

try! only works when the parser is given a seekable stream.

[Function] progn! &rest parsers => parser

Return a parser that strings together all given parsers and returns the last parser's result.

[Function] prog1! first &rest parsers => parser

Return a parser that strings together all given parsers and returns the first parser's result.

[Function] prog2! first second &rest parsers => parser

Return a parser that strings together all given parsers and returns the second parser's result.

[Function] or! &rest parsers => parser

Return a parser that tries each given parser in order (until a partial-parse failure) and returns the result of the first successful parse.

If all parsers fail, then the parser error accumulates a list of all possible expected values.

[Function] collect parser => list-parser

Return a parser that runs the given parser until failure, and collects all results into a list.

[Function] collect1 parser => list-parser

Return a parser that runs the given parser once, keeps parsing until failure, and then collects all results into a list.

[Function] collect-into-string char-parser => string-parser

Return a parser that runs the given character parser until failure, and collects all characters into a string.

[Function] sep value-parser sep-parser => value-list-parser

Return a parser that accepts a sequence of value-parser input separated by sep-parser input; such as values separated by commas.

[Function] reduce! function parser &key initial-parser => parser

Return a parser that keeps running until failure, and reduces its result into one value.

If initial-parser is supplied, the parser may succeed without calling FUNCTION by returning INITIAL-PARSER's response.

[Function] skip parser => parser

Parse and pretend no input was consumed.

[Function] skip-many parser => parser

Keep parsing until failure, discard the results, and pretend no input was consumed.

[Function] digit &optional (radix 10) => integer-parser

Consume and return the number value of a digit.

[Function] natural &optional (radix 10) => integer-parser

Consume and return a natural number.

[Macro] defparser name () &body (form) => symbol

Define a parser as a function. It can then be referenced as a function designator.

[Function] parse parser stream => object

Run a parser through a given stream and raise any failures as a parser-error.

[Condition] parser-error (stream-error)

Parser errors are raised by parse when a parser cannot recover from an error. Parser error readers provide the line and column a parser ended at, the return-trace of defparser-defined parsers and the lines and columns each parser started at, and an object that describes what the parser expected:

• stream-error-stream stream-error => stream
• parser-error-line parser-error => number
• parser-error-column parser-error => number
• parser-error-expected parser-error => object
• parser-error-return-trace parser-error => return-trace

A return-trace is a list of (parser-name line column)-structured objects detailing the state of the composite parser when it failed.

For both the parser-error and return-trace, lines start at 1 and columns start at 0, and is initialized per parse call.