The parsnip Reference Manual

Next: , Previous: , Up: (dir)   [Contents][Index]

The parsnip Reference Manual

This is the parsnip Reference Manual, version 0.0.7, generated automatically by Declt version 4.0 beta 2 "William Riker" on Thu Sep 15 05:49:51 2022 GMT+0.

Table of Contents


1 Introduction

Parsnip

builds.sr.ht status

The library brand image: a crudely drawn parsnip surrounded by parentheses

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:

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:

I recognize these as non-breaking changes:

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:

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.


2 Systems

The main system appears first, followed by any subsystem dependency.


Previous: , Up: Systems   [Contents][Index]

2.1 parsnip

Parser combinator library

Author

Samuel Hunter

Contact

~shunter/public-inbox@lists.sr.ht

Home Page

https://sr.ht/~shunter/parsnip/

Source Control

(GIT https://git.sr.ht/~shunter/parsnip)

Bug Tracker

https://todo.sr.ht/~shunter/parsnip

License

BSD 3-Clause

Version

0.0.7

Dependency

alexandria (system).

Source

parsnip.asd.

Child Component

parsnip.lisp (file).


3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp   [Contents][Index]

3.1.1 parsnip/parsnip.asd

Source

parsnip.asd.

Parent Component

parsnip (system).

ASDF Systems

parsnip.


Previous: , Up: Lisp   [Contents][Index]

3.1.2 parsnip/parsnip.lisp

Source

parsnip.asd.

Parent Component

parsnip (system).

Packages

xyz.shunter.parsnip.

Public Interface
Internals

4 Packages

Packages are listed by definition order.


Previous: , Up: Packages   [Contents][Index]

4.1 xyz.shunter.parsnip

Monadic parser combinator library

Source

parsnip.lisp.

Nickname

parsnip

Use List

common-lisp.

Public Interface
Internals

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Public Interface


5.1.1 Macros

Macro: defparser (name () &body form)

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

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Macro: let! ((&rest bindings) &body body)

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

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.


5.1.2 Ordinary functions

Function: char-if (predicate &optional message)

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

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: char-in (charbag &optional message)

Return a parser that consumes a character that’s only in the given charbag.

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: char-of (char &optional message)

Return a parser that consumes the given character.

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: collect (parser)

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

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: collect-into-string (char-parser)

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

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: collect1 (parser)

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

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: digit (&optional radix)

Consume and return the number value of a digit.

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: eof (&optional value)

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

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: fail (expected &optional trace)

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

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: flatmap (function 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.

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: handle (parser handler)

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.

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: handle-rewind (parser handler)

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.

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: natural (&optional radix)

Consume and return a natural number.

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: ok (value)

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

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: or! (&rest parsers)

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

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: parse (parser stream)

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

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: prog1! (first &rest parsers)

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

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: prog2! (first second &rest parsers)

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

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: progn! (&rest parsers)

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

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: reduce! (function parser &key initial-parser)

Return a parser that keeps running until failure, and reduces its results into one value.
If INITIAL-PARSER is supplied, the parser may succeed without calling FUNCTION by returning INITIAL-PARSER’s response.

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: sep (value-parser sep-parser)

Return a parser that accepts a sequence of VALUE-PARSER input separated by SEP-PARSER input; such as values separated by commas.

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: skip (parser)

Parse and pretend no input was consumed.

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: skip-many (parser)

Keep parsing until failure and pretend no input was consumed.

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: string-of (string &optional message)

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

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: try! (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.

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.


5.1.3 Generic functions

Generic Reader: parser-error-column (condition)
Package

xyz.shunter.parsnip.

Methods
Reader Method: parser-error-column ((condition parser-error))
Source

parsnip.lisp.

Target Slot

column.

Generic Reader: parser-error-expected (condition)
Package

xyz.shunter.parsnip.

Methods
Reader Method: parser-error-expected ((condition parser-error))
Source

parsnip.lisp.

Target Slot

expected.

Generic Reader: parser-error-line (condition)
Package

xyz.shunter.parsnip.

Methods
Reader Method: parser-error-line ((condition parser-error))
Source

parsnip.lisp.

Target Slot

line.

Generic Reader: parser-error-return-trace (condition)
Package

xyz.shunter.parsnip.

Methods
Reader Method: parser-error-return-trace ((condition parser-error))
Source

parsnip.lisp.

Target Slot

return-trace.


5.1.4 Conditions

Condition: parser-error

If a parser fails to read text, it signals a parser-error, containing a stream, its expected value, and a return trace of parsers.

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Direct superclasses

stream-error.

Direct methods
Direct slots
Slot: line

The (1-based) line number at which the parser failed

Initargs

:line

Readers

parser-error-line.

Writers

This slot is read-only.

Slot: column

The (0-based) column number at which the parser failed

Initargs

:column

Readers

parser-error-column.

Writers

This slot is read-only.

Slot: expected

An object describing what the parser expected to read

Initargs

:expected

Readers

parser-error-expected.

Writers

This slot is read-only.

Slot: return-trace

A list of (name line column) objects detailing the state of the parser when it failed

Initargs

:return-trace

Readers

parser-error-return-trace.

Writers

This slot is read-only.


5.2 Internals


Next: , Previous: , Up: Internals   [Contents][Index]

5.2.1 Macros

Macro: let@ ((&rest bindings) &body body)

Anaphoric self-callable LET.

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.


Next: , Previous: , Up: Internals   [Contents][Index]

5.2.2 Ordinary functions

Function: advance-pstream (pstream c)

Update the line and column of PSTREAM given the accepted char C and return PSTREAM.

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: consume (pstream)
Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: parse-stream (stream)
Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: peek (pstream)
Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Reader: pstream-column (instance)
Writer: (setf pstream-column) (instance)
Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Target Slot

column.

Reader: pstream-line (instance)
Writer: (setf pstream-line) (instance)
Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Target Slot

line.

Reader: pstream-stream (instance)
Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Target Slot

stream.

Function: rewind (pstream snapshot)

Set the (stream) position, line, and column of PSTREAM with the SNAPSHOT received from SAVE.

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: save (pstream)

Return the position, line, and column of PSTREAM.

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Function: signal-failure (pstream expected return-trace)

Signal an error depending on the given fail.

Package

xyz.shunter.parsnip.

Source

parsnip.lisp.


Next: , Previous: , Up: Internals   [Contents][Index]

5.2.3 Structures

Structure: parse-stream
Package

xyz.shunter.parsnip.

Source

parsnip.lisp.

Direct superclasses

structure-object.

Direct slots
Slot: stream
Package

common-lisp.

Readers

pstream-stream.

Writers

This slot is read-only.

Slot: line
Initform

1

Readers

pstream-line.

Writers

(setf pstream-line).

Slot: column
Initform

0

Readers

pstream-column.

Writers

(setf pstream-column).


Previous: , Up: Internals   [Contents][Index]

5.2.4 Types

Type: function-designator ()
Package

xyz.shunter.parsnip.

Source

parsnip.lisp.


Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts


Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   (  
A   C   D   E   F   G   H   L   M   N   O   P   R   S   T  
Index Entry  Section

(
(setf pstream-column): Private ordinary functions
(setf pstream-line): Private ordinary functions

A
advance-pstream: Private ordinary functions

C
char-if: Public ordinary functions
char-in: Public ordinary functions
char-of: Public ordinary functions
collect: Public ordinary functions
collect-into-string: Public ordinary functions
collect1: Public ordinary functions
consume: Private ordinary functions

D
defparser: Public macros
digit: Public ordinary functions

E
eof: Public ordinary functions

F
fail: Public ordinary functions
flatmap: Public ordinary functions
Function, (setf pstream-column): Private ordinary functions
Function, (setf pstream-line): Private ordinary functions
Function, advance-pstream: Private ordinary functions
Function, char-if: Public ordinary functions
Function, char-in: Public ordinary functions
Function, char-of: Public ordinary functions
Function, collect: Public ordinary functions
Function, collect-into-string: Public ordinary functions
Function, collect1: Public ordinary functions
Function, consume: Private ordinary functions
Function, digit: Public ordinary functions
Function, eof: Public ordinary functions
Function, fail: Public ordinary functions
Function, flatmap: Public ordinary functions
Function, handle: Public ordinary functions
Function, handle-rewind: Public ordinary functions
Function, natural: Public ordinary functions
Function, ok: Public ordinary functions
Function, or!: Public ordinary functions
Function, parse: Public ordinary functions
Function, parse-stream: Private ordinary functions
Function, peek: Private ordinary functions
Function, prog1!: Public ordinary functions
Function, prog2!: Public ordinary functions
Function, progn!: Public ordinary functions
Function, pstream-column: Private ordinary functions
Function, pstream-line: Private ordinary functions
Function, pstream-stream: Private ordinary functions
Function, reduce!: Public ordinary functions
Function, rewind: Private ordinary functions
Function, save: Private ordinary functions
Function, sep: Public ordinary functions
Function, signal-failure: Private ordinary functions
Function, skip: Public ordinary functions
Function, skip-many: Public ordinary functions
Function, string-of: Public ordinary functions
Function, try!: Public ordinary functions

G
Generic Function, parser-error-column: Public generic functions
Generic Function, parser-error-expected: Public generic functions
Generic Function, parser-error-line: Public generic functions
Generic Function, parser-error-return-trace: Public generic functions

H
handle: Public ordinary functions
handle-rewind: Public ordinary functions

L
let!: Public macros
let@: Private macros

M
Macro, defparser: Public macros
Macro, let!: Public macros
Macro, let@: Private macros
Method, parser-error-column: Public generic functions
Method, parser-error-expected: Public generic functions
Method, parser-error-line: Public generic functions
Method, parser-error-return-trace: Public generic functions

N
natural: Public ordinary functions

O
ok: Public ordinary functions
or!: Public ordinary functions

P
parse: Public ordinary functions
parse-stream: Private ordinary functions
parser-error-column: Public generic functions
parser-error-column: Public generic functions
parser-error-expected: Public generic functions
parser-error-expected: Public generic functions
parser-error-line: Public generic functions
parser-error-line: Public generic functions
parser-error-return-trace: Public generic functions
parser-error-return-trace: Public generic functions
peek: Private ordinary functions
prog1!: Public ordinary functions
prog2!: Public ordinary functions
progn!: Public ordinary functions
pstream-column: Private ordinary functions
pstream-line: Private ordinary functions
pstream-stream: Private ordinary functions

R
reduce!: Public ordinary functions
rewind: Private ordinary functions

S
save: Private ordinary functions
sep: Public ordinary functions
signal-failure: Private ordinary functions
skip: Public ordinary functions
skip-many: Public ordinary functions
string-of: Public ordinary functions

T
try!: Public ordinary functions

Jump to:   (  
A   C   D   E   F   G   H   L   M   N   O   P   R   S   T