The parseltongue Reference Manual

Table of Contents

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

The parseltongue Reference Manual

This is the parseltongue Reference Manual, version 0.0.1, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 12:22:42 2018 GMT+0.


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

1 Introduction

Copyright 2012, Vincent Toups This program is distributed under the terms of the GNU Lesser General Public License (see license.txt).

Parseltongue

A Parser Combinator Library for CL

This is a parser combinator library for Common Lisp inspired by SMUG, by Drew Crampsie and augmented with improvements inspired by my own usage of this library and other monadic computations in various Lisps.

This library probably has the same functionality as SMUG but migth be more familiar to those used to Haskell's do notation.

Fear not, you needn't understand how monads work in order to make good use of this library. For those uninterested in how the library works, there are only two things you need to know to use it: what parsers are, how to use combinators on them, and how to use the special syntax in the parser and defparser forms.

Parsers

Parsers, in this library, are functions which accept a single parameter, the input, and return either nil, if they cannot parse anything from that input, or a list of parser-pair structs (defined by the library), each of which represents a possible parsing of the input, along with the remainder of the input which was not parsed. For instance, a parser that parses "a" from a string looks like:

(defun =parse-a (input)
 (if (empty? input)
     nil
     (let ((first-char (next input)))
       (if (string= first-char "a")
           (list (parser-pair first-char
                   (rest-of input)))
           nil))))

The function next is a method which fetches the next item from an input. next is defined for lists and strings by default, but can be extended by the user with defmethod. rest-of is its partner, it returns the rest of the input. parser-pair constructs a parser-pair struct instance whose first value is the parsed result, and whose second value is the rest of the input that was not parsed. As indicated above, returning nil means nothing was parsed at all.

Any function which conforms to this type can be treated as a parser by the library. If you want to write you own parsers without ever touching the special syntax in the library, you do so just as we did above. By convention, parsers in the library start with the = character, to distinguish them visually from other functions.

We could have written the above parser with a combinator from the library, =>string, like so:

(defun =parse-a (input) (funcall (=>string "a") input))

=>string is a function which takes a string and returns a parser, which we use to parse the input. Any function which produces a parser begins with => in this library. The simplest such function is the function referred to as the parser return function, =>.

(=> 'some-value)

=> returns a parser which does nothing to the input, and returns a single parser-pair (in a list), whose return value is some-value.

The whole idea of this library is to construct parsers from simpler parsers.

Special Syntax for Parser Construction and Definition

The library provides syntax to make writing parsers easier. We could have defined =parse-a above like so, for instance:

(defparser =parse-a 
  (x <- =item)
  (if (string= x "a") (=> x) =nil))

Since we often treat parsers as both functions and regular variables, defparser establishes both a variable =parse-a and a function by the same name. This function, as defined above, is equivalent to the previous definitions, but how do we read it?

Within the body of a defparser (or parser form, which is the anonymous version), each expression must be either a parser itself or a "binding expression" of the form

`(variable <- parser-expression)` 

When an expression is just a parser, that parser must succeed or the entire parser being defined will return nil. Subsequent parsers executed in the body will then see only the input not parsed by previous parsers.

When a binding expression is encountered, the parser on the right hand side is to the current input, which may have been parsed down by previous expressions in the body, and, if the parse succeeds, then in the rest of the body, the variable in the left-hand-side is bound to the value in the value-slot of the parser-pairs returned by the parser. Hence, in the above expression, the first form:

(x <- =item)

Sees =item applied to the input of the parser. =item always pulls one item off of the input and only fails when the input is empty. If the input is empty, then the parse fails, and no further forms are executed. If =item succeeds, then we look to the next line. The next line is not a binding form. It is an if statement, which is fine, subject to the constraint that each branch must return a parser. If the item we've parsed from the input is "a", then we use => to create a parser which inserts "a" as its parser-pair's value. If not, we return the =nil parser, which always fails.

If we wanted to parse "a" and then "b", we'd write:

(defparser =parse-ab
 (=>string "a")
 (=>string "b"))

Important Combinators

The =>or combinator produces a parser if any of its input parsers succeed, returning the value of the first success from left to right. For instance, to parser "a" or "b":

(defparser =a-or-b 
 (=>or (=>string "a")
       (=>string "b")))

Then:

(=a-or-b "abc") -> (list (parser-pair "a" "bc"))
(=a-or-b "bbc") -> (list (parser-pair "b" "bc"))

The combinator =>and succeeds only when all of its input parsers succeed in turn, finally returning the result of the last parser:

(funcall (=>and (=>string "a") (=>string "b")) "ab") ->
 (list (parser-pair "b" ""))

The combinator =>items parses n or fewer items from the input, regardless of what they are:

(funcall (=>items 3) "abcd") -> 
 (list (parser-pair (list "a" "b" "c") "d"))

The combinator =>zero-plus-more parsers as many of its input parser as possible and returns them in a list, possibly an empty one:

(funcall (=>zero-plus-more
          (=>string "a"))
         "aaaab") ->
(list (parser-pair (list "a" "a" "a" "a")
                   "b"))

The combinator =>one-plus-more does the same except it fails if there is not at least one parsable object.

Non-determinism

Parseltongue, like SMUG, is actually a non-deterministic library - parsers can parse in multiple ways simultaneously. I'll write some documentation about that later, but if you are using it for regular deterministic parser, you are usually interested in only the first parser-result. Hence, the function parse/first-result is a handy thing:

(parser/first-result (=>string "a") "abc") -> "a"

It returns the first parse result and leaves off the leftover input.

Thanks

I'd like to thank Drew for writing up SMUG, which was critical in developing an understanding of monads in Lisp and obviously in inspiring this library. He also provided some correspondence when I didn't understand aspects of his code.

Other Notes:

If you like this library, it is almost a line for line port of an Elisp parser combinator library I also wrote, available in my emacs-utils repository here on github.



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

2 Systems

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


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

2.1 parseltongue

Maintainer

Vincent Toups

Author

Vincent Toups

License

LGPL

Description

Parseltongue

Long Description

A monadic parser combinator library with Haskell do-like notation.

Version

0.0.1

Dependency

lisp-unit

Source

parseltongue.asd (file)

Components

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

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 files   [Contents][Index]

3.1.1 parseltongue.asd

Location

parseltongue.asd

Systems

parseltongue (system)


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

3.1.2 parseltongue/package.lisp

Parent

parseltongue (system)

Location

package.lisp

Packages

parseltongue


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

3.1.3 parseltongue/parseltongue.lisp

Dependency

package.lisp (file)

Parent

parseltongue (system)

Location

parseltongue.lisp

Exported Definitions
Internal Definitions

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

3.1.4 parseltongue/tests.lisp

Dependency

parseltongue.lisp (file)

Parent

parseltongue (system)

Location

tests.lisp


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

4 Packages

Packages are listed by definition order.


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

4.1 parseltongue

Source

package.lisp (file)

Use List
Exported Definitions
Internal Definitions

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

5 Definitions

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


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

5.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.1 Special variables

Special Variable: =item

A parser

Package

parseltongue

Source

parseltongue.lisp (file)

Special Variable: =rest

A parser

Package

parseltongue

Source

parseltongue.lisp (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.2 Macros

Macro: defparser NAME/ARGS MAYBE-DOC &rest BODY
Package

parseltongue

Source

parseltongue.lisp (file)

Macro: parser &rest FORMS
Package

parseltongue

Source

parseltongue.lisp (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.3 Functions

Function: =>and &rest PS
Package

parseltongue

Source

parseltongue.lisp (file)

Function: =>eq TO
Package

parseltongue

Source

parseltongue.lisp (file)

Function: =>equal TO
Package

parseltongue

Source

parseltongue.lisp (file)

Function: =>items N
Package

parseltongue

Source

parseltongue.lisp (file)

Function: =>items->string N
Package

parseltongue

Source

parseltongue.lisp (file)

Function: =>maybe =P
Package

parseltongue

Source

parseltongue.lisp (file)

Function: =>maybe-alternative =P ALT
Package

parseltongue

Source

parseltongue.lisp (file)

Function: =>one-plus-more =P
Package

parseltongue

Source

parseltongue.lisp (file)

Function: =>or &rest PS
Package

parseltongue

Source

parseltongue.lisp (file)

Function: =>reduce-concat =P
Package

parseltongue

Source

parseltongue.lisp (file)

Function: =>satisfies FUN
Package

parseltongue

Source

parseltongue.lisp (file)

Function: =>string S
Package

parseltongue

Source

parseltongue.lisp (file)

Function: =>zero-plus-more P

Produce a parser which parses P zero or more times and monadically returns the results in a list.

Package

parseltongue

Source

parseltongue.lisp (file)

Function: =item INPUT
Package

parseltongue

Source

parseltongue.lisp (file)

Function: =rest INPUT
Package

parseltongue

Source

parseltongue.lisp (file)

Function: parse/first-result =P INPUT
Package

parseltongue

Source

parseltongue.lisp (file)

Function: parser-bind =P =>P
Package

parseltongue

Source

parseltongue.lisp (file)

Function: parser-pair VALUE INPUT
Package

parseltongue

Source

parseltongue.lisp (file)

Function: parser-return &rest ITEMS
Package

parseltongue

Source

parseltongue.lisp (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.4 Generic functions

Generic Function: empty? LIST
Package

parseltongue

Methods
Method: empty? (STRING string)
Source

parseltongue.lisp (file)

Method: empty? (LIST list)
Source

parseltongue.lisp (file)

Generic Function: next LIST
Package

parseltongue

Methods
Method: next (STRING string)
Source

parseltongue.lisp (file)

Method: next (LIST list)
Source

parseltongue.lisp (file)

Generic Function: rest-of LIST
Package

parseltongue

Methods
Method: rest-of (STRING string)
Source

parseltongue.lisp (file)

Method: rest-of (LIST list)
Source

parseltongue.lisp (file)


Previous: , Up: Exported definitions   [Contents][Index]

5.1.5 Structures

Structure: parser-pair ()
Package

parseltongue

Source

parseltongue.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: value
Readers

parser-pair-value (function)

Writers

(setf parser-pair-value) (function)

Slot: input
Readers

parser-pair-input (function)

Writers

(setf parser-pair-input) (function)


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

5.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.1 Special variables

Special Variable: =nil

A parser

Package

parseltongue

Source

parseltongue.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.2 Macros

Macro: defun/var NAME ARG-LIST &rest BODY
Package

parseltongue

Source

parseltongue.lisp (file)

Macro: named-let NAME BINDINGS &rest BODY
Package

parseltongue

Source

parseltongue.lisp (file)

Macro: parser-helper &rest FORMS
Package

parseltongue

Source

parseltongue.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.3 Functions

Function: => &rest ITEMS
Package

parseltongue

Source

parseltongue.lisp (file)

Function: =>and2 =P1 =P2
Package

parseltongue

Source

parseltongue.lisp (file)

Function: =>list =P
Package

parseltongue

Source

parseltongue.lisp (file)

Function: =>or2 =P1 =P2
Package

parseltongue

Source

parseltongue.lisp (file)

Function: =nil INPUT
Package

parseltongue

Source

parseltongue.lisp (file)

Function: alist A KEY

Return the value at KEY or NIL.

Package

parseltongue

Source

parseltongue.lisp (file)

Function: alist-cons A KEY VAL

CONS VAL onto the LIST held at KEY in the ALIST A.

Package

parseltongue

Source

parseltongue.lisp (file)

Function: bind-form? FORM
Package

parseltongue

Source

parseltongue.lisp (file)

Function: copy-parser-pair INSTANCE
Package

parseltongue

Source

parseltongue.lisp (file)

Function: make-parser-pair &key (VALUE VALUE) (INPUT INPUT)
Package

parseltongue

Source

parseltongue.lisp (file)

Function: mapcar/deal FUN LST

Map FUN over LST. FUN returns a list of two items, the first of which is a key the second of which is a value. The VALUES are accumulated at the KEYS in an ALIST which is returned.

Package

parseltongue

Source

parseltongue.lisp (file)

Function: parser-pair-input INSTANCE
Function: (setf parser-pair-input) VALUE INSTANCE
Package

parseltongue

Source

parseltongue.lisp (file)

Function: parser-pair-p OBJECT
Package

parseltongue

Source

parseltongue.lisp (file)

Function: parser-pair-value INSTANCE
Function: (setf parser-pair-value) VALUE INSTANCE
Package

parseltongue

Source

parseltongue.lisp (file)

Function: parser-plus &rest PS
Package

parseltongue

Source

parseltongue.lisp (file)

Function: reverse-alist-keys A

Reverse the lists held at each key in A.

Package

parseltongue

Source

parseltongue.lisp (file)

Function: strcat &rest S
Package

parseltongue

Source

parseltongue.lisp (file)

Function: zero-plus-more-step SUBSTATE PARSER

Apply PARSER to the CDR of substate. If it succeeds, cons the result onto the list in the CAR of substate and indicate CONTINUE for MAPCAR/DEAL. If PARSER on CDR of substate FAILS, then reverse the CAR of SUBSTATE and return this value consed with the last INPUT state.

Package

parseltongue

Source

parseltongue.lisp (file)


Previous: , Up: Internal definitions   [Contents][Index]

5.2.4 Generic functions

Generic Function: empty-of LIST
Package

parseltongue

Methods
Method: empty-of (STRING string)
Source

parseltongue.lisp (file)

Method: empty-of (LIST list)
Source

parseltongue.lisp (file)

Generic Function: prefix O STRING
Package

parseltongue

Methods
Method: prefix O (LIST list)
Source

parseltongue.lisp (file)

Method: prefix O (STRING string)
Source

parseltongue.lisp (file)


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

Appendix A Indexes


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

A.1 Concepts

Jump to:   F   L   P  
Index Entry  Section

F
File, Lisp, parseltongue.asd: The parseltongue<dot>asd file
File, Lisp, parseltongue/package.lisp: The parseltongue/package<dot>lisp file
File, Lisp, parseltongue/parseltongue.lisp: The parseltongue/parseltongue<dot>lisp file
File, Lisp, parseltongue/tests.lisp: The parseltongue/tests<dot>lisp file

L
Lisp File, parseltongue.asd: The parseltongue<dot>asd file
Lisp File, parseltongue/package.lisp: The parseltongue/package<dot>lisp file
Lisp File, parseltongue/parseltongue.lisp: The parseltongue/parseltongue<dot>lisp file
Lisp File, parseltongue/tests.lisp: The parseltongue/tests<dot>lisp file

P
parseltongue.asd: The parseltongue<dot>asd file
parseltongue/package.lisp: The parseltongue/package<dot>lisp file
parseltongue/parseltongue.lisp: The parseltongue/parseltongue<dot>lisp file
parseltongue/tests.lisp: The parseltongue/tests<dot>lisp file

Jump to:   F   L   P  

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

A.2 Functions

Jump to:   (   =  
A   B   C   D   E   F   G   M   N   P   R   S   Z  
Index Entry  Section

(
(setf parser-pair-input): Internal functions
(setf parser-pair-value): Internal functions

=
=>: Internal functions
=>and: Exported functions
=>and2: Internal functions
=>eq: Exported functions
=>equal: Exported functions
=>items: Exported functions
=>items->string: Exported functions
=>list: Internal functions
=>maybe: Exported functions
=>maybe-alternative: Exported functions
=>one-plus-more: Exported functions
=>or: Exported functions
=>or2: Internal functions
=>reduce-concat: Exported functions
=>satisfies: Exported functions
=>string: Exported functions
=>zero-plus-more: Exported functions
=item: Exported functions
=nil: Internal functions
=rest: Exported functions

A
alist: Internal functions
alist-cons: Internal functions

B
bind-form?: Internal functions

C
copy-parser-pair: Internal functions

D
defparser: Exported macros
defun/var: Internal macros

E
empty-of: Internal generic functions
empty-of: Internal generic functions
empty-of: Internal generic functions
empty?: Exported generic functions
empty?: Exported generic functions
empty?: Exported generic functions

F
Function, (setf parser-pair-input): Internal functions
Function, (setf parser-pair-value): Internal functions
Function, =>: Internal functions
Function, =>and: Exported functions
Function, =>and2: Internal functions
Function, =>eq: Exported functions
Function, =>equal: Exported functions
Function, =>items: Exported functions
Function, =>items->string: Exported functions
Function, =>list: Internal functions
Function, =>maybe: Exported functions
Function, =>maybe-alternative: Exported functions
Function, =>one-plus-more: Exported functions
Function, =>or: Exported functions
Function, =>or2: Internal functions
Function, =>reduce-concat: Exported functions
Function, =>satisfies: Exported functions
Function, =>string: Exported functions
Function, =>zero-plus-more: Exported functions
Function, =item: Exported functions
Function, =nil: Internal functions
Function, =rest: Exported functions
Function, alist: Internal functions
Function, alist-cons: Internal functions
Function, bind-form?: Internal functions
Function, copy-parser-pair: Internal functions
Function, make-parser-pair: Internal functions
Function, mapcar/deal: Internal functions
Function, parse/first-result: Exported functions
Function, parser-bind: Exported functions
Function, parser-pair: Exported functions
Function, parser-pair-input: Internal functions
Function, parser-pair-p: Internal functions
Function, parser-pair-value: Internal functions
Function, parser-plus: Internal functions
Function, parser-return: Exported functions
Function, reverse-alist-keys: Internal functions
Function, strcat: Internal functions
Function, zero-plus-more-step: Internal functions

G
Generic Function, empty-of: Internal generic functions
Generic Function, empty?: Exported generic functions
Generic Function, next: Exported generic functions
Generic Function, prefix: Internal generic functions
Generic Function, rest-of: Exported generic functions

M
Macro, defparser: Exported macros
Macro, defun/var: Internal macros
Macro, named-let: Internal macros
Macro, parser: Exported macros
Macro, parser-helper: Internal macros
make-parser-pair: Internal functions
mapcar/deal: Internal functions
Method, empty-of: Internal generic functions
Method, empty-of: Internal generic functions
Method, empty?: Exported generic functions
Method, empty?: Exported generic functions
Method, next: Exported generic functions
Method, next: Exported generic functions
Method, prefix: Internal generic functions
Method, prefix: Internal generic functions
Method, rest-of: Exported generic functions
Method, rest-of: Exported generic functions

N
named-let: Internal macros
next: Exported generic functions
next: Exported generic functions
next: Exported generic functions

P
parse/first-result: Exported functions
parser: Exported macros
parser-bind: Exported functions
parser-helper: Internal macros
parser-pair: Exported functions
parser-pair-input: Internal functions
parser-pair-p: Internal functions
parser-pair-value: Internal functions
parser-plus: Internal functions
parser-return: Exported functions
prefix: Internal generic functions
prefix: Internal generic functions
prefix: Internal generic functions

R
rest-of: Exported generic functions
rest-of: Exported generic functions
rest-of: Exported generic functions
reverse-alist-keys: Internal functions

S
strcat: Internal functions

Z
zero-plus-more-step: Internal functions

Jump to:   (   =  
A   B   C   D   E   F   G   M   N   P   R   S   Z  

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

A.3 Variables

Jump to:   =  
I   S   V  
Index Entry  Section

=
=item: Exported special variables
=nil: Internal special variables
=rest: Exported special variables

I
input: Exported structures

S
Slot, input: Exported structures
Slot, value: Exported structures
Special Variable, =item: Exported special variables
Special Variable, =nil: Internal special variables
Special Variable, =rest: Exported special variables

V
value: Exported structures

Jump to:   =  
I   S   V  

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

A.4 Data types

Jump to:   P   S  
Index Entry  Section

P
Package, parseltongue: The parseltongue package
parseltongue: The parseltongue system
parseltongue: The parseltongue package
parser-pair: Exported structures

S
Structure, parser-pair: Exported structures
System, parseltongue: The parseltongue system

Jump to:   P   S