Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
This is the parser-combinators Reference Manual, version 0, generated automatically by Declt version 3.0 "Montgomery Scott" on Tue Dec 22 12:38:22 2020 GMT+0.
| • Introduction | What parser-combinators is all about | |
| • Systems | The systems documentation | |
| • Files | The files documentation | |
| • Packages | The packages documentation | |
| • Definitions | The symbols documentation | |
| • Indexes | Concepts, functions, variables and data types |
This is an experimental implementation of parser combinators for Common Lisp. This is mostly inspired by Parsec, but with limited optimizations. Parser combinators are, in theory, an elegant form of constructing parsers for context-free grammars.
The name of the system is parser-combinators, despite the name of the GitHub repository. The library is fairly lightly tested. Any comments or questions on the functionality or performance are welcome.
The test suite has some additional dependencies, all of which are in quicklisp
There is some documentation in the doc directory.
Next: Files, Previous: Introduction, Up: Top [Contents][Index]
The main system appears first, followed by any subsystem dependency.
| • The parser-combinators system |
Jakub Higersberger <ramarren@gmail.com>
Jakub Higersberger <ramarren@gmail.com>
BSD-style
An implementation of parser combinators for Common Lisp
0
parser-combinators.asd (file)
Files are sorted by type and then listed depth-first from the systems components trees.
| • Lisp files |
Next: The parser-combinators/package․lisp file, Previous: Lisp files, Up: Lisp files [Contents][Index]
parser-combinators.asd
parser-combinators (system)
Next: The parser-combinators/queue․lisp file, Previous: The parser-combinators․asd file, Up: Lisp files [Contents][Index]
parser-combinators (system)
package.lisp
Next: The parser-combinators/contexts․lisp file, Previous: The parser-combinators/package․lisp file, Up: Lisp files [Contents][Index]
package.lisp (file)
parser-combinators (system)
queue.lisp
Next: The parser-combinators/lazy․lisp file, Previous: The parser-combinators/queue․lisp file, Up: Lisp files [Contents][Index]
package.lisp (file)
parser-combinators (system)
contexts.lisp
Next: The parser-combinators/cache․lisp file, Previous: The parser-combinators/contexts․lisp file, Up: Lisp files [Contents][Index]
package.lisp (file)
parser-combinators (system)
lazy.lisp
Next: The parser-combinators/basic․lisp file, Previous: The parser-combinators/lazy․lisp file, Up: Lisp files [Contents][Index]
package.lisp (file)
parser-combinators (system)
cache.lisp
*parser-cache* (special variable)
Next: The parser-combinators/ensure-parser․lisp file, Previous: The parser-combinators/cache․lisp file, Up: Lisp files [Contents][Index]
parser-combinators (system)
basic.lisp
Next: The parser-combinators/combinators․lisp file, Previous: The parser-combinators/basic․lisp file, Up: Lisp files [Contents][Index]
parser-combinators (system)
ensure-parser.lisp
Next: The parser-combinators/primitives․lisp file, Previous: The parser-combinators/ensure-parser․lisp file, Up: Lisp files [Contents][Index]
parser-combinators (system)
combinators.lisp
Next: The parser-combinators/parsers․lisp file, Previous: The parser-combinators/combinators․lisp file, Up: Lisp files [Contents][Index]
parser-combinators (system)
primitives.lisp
cut? (function)
Next: The parser-combinators/memoize․lisp file, Previous: The parser-combinators/primitives․lisp file, Up: Lisp files [Contents][Index]
parser-combinators (system)
parsers.lisp
Next: The parser-combinators/recurse․lisp file, Previous: The parser-combinators/parsers․lisp file, Up: Lisp files [Contents][Index]
parser-combinators (system)
memoize.lisp
memoize? (function)
Next: The parser-combinators/greedy․lisp file, Previous: The parser-combinators/memoize․lisp file, Up: Lisp files [Contents][Index]
parser-combinators (system)
recurse.lisp
curtail? (macro)
*curtail* (special variable)
Next: The parser-combinators/token-parsers․lisp file, Previous: The parser-combinators/recurse․lisp file, Up: Lisp files [Contents][Index]
parser-combinators (system)
greedy.lisp
Previous: The parser-combinators/greedy․lisp file, Up: Lisp files [Contents][Index]
parser-combinators (system)
token-parsers.lisp
Next: Definitions, Previous: Files, Up: Top [Contents][Index]
Packages are listed by definition order.
| • The parser-combinators package | ||
| • The parser-combinators-debug package |
Next: The parser-combinators-debug package, Previous: Packages, Up: Packages [Contents][Index]
package.lisp (file)
Previous: The parser-combinators package, Up: Packages [Contents][Index]
package.lisp (file)
Definitions are sorted by export status, category, package, and then by lexicographic order.
| • Exported definitions | ||
| • Internal definitions |
Next: Internal definitions, Previous: Definitions, Up: Definitions [Contents][Index]
| • Exported special variables | ||
| • Exported macros | ||
| • Exported functions | ||
| • Exported generic functions | ||
| • Exported classes |
Next: Exported macros, Previous: Exported definitions, Up: Exported definitions [Contents][Index]
contexts.lisp (file)
Next: Exported functions, Previous: Exported special variables, Up: Exported definitions [Contents][Index]
Parser modifier macro: cache parser as label with argument list equal under equal in global cache.
cache.lisp (file)
Parser modifier macro: cache parser as label in global cache.
cache.lisp (file)
contexts.lisp (file)
Parser modifier: add recursion curtailing to PARSER, naming the curtailed parser NAME. Left recursive parser parser will only be nested once per remaining length of the input string. Note: this is only necessary for a limited class of left recursive parsers. Non-left recursive parsers should be implemented using just ‘named?‘, and most left-recursive parsers using that in combination with ‘chainl1?‘. Also see ‘expression?‘.
recurse.lisp (file)
Define cached parser with arguments.
cache.lisp (file)
Define cached parser of no arguments.
cache.lisp (file)
ensure-parser.lisp (file)
Parser modifier macro: parser will be built when called. This is necessary for left-recursive parsers.
primitives.lisp (file)
Combinator: use do-like notation to sequentially link parsers. (<- name parser) allows capturing of return values.
basic.lisp (file)
Like NAMED-SEQ*, but with MDO syntax: the last element must be a parser.
greedy.lisp (file)
Non-backtracking parser: This is similar to MDO, except that constructed parsers cannot depend on
the results of previous ones and the final form is not used as a parser, but is automatically used
to construct the result. All names bound using the (<- name parser) construct are only available in
that final form.
This parser generator is useful when full generality of MDO is not necessary, as it is implemented non-recursively and has better memory performance.
greedy.lisp (file)
Parser: This is similar to MDO, except that constructed parsers cannot depend on the results of previous ones and the final form is not used as a parser, but is automatically used to construct the result. All names bound using the (<- name parser) construct are only available in that final form.
This parser generator is useful when full generality of MDO is not necessary, as it is implemented non-recursively and has better memory performance.
parsers.lisp (file)
Parser macro: give BODY a NAME, so it can refer to itself without causing generator recursion.
parsers.lisp (file)
Next: Exported generic functions, Previous: Exported macros, Up: Exported definitions [Contents][Index]
Parser: accept alphanumeric character
token-parsers.lisp (file)
Non-backtracking parser: accept as many as possible and at least count of parser
greedy.lisp (file)
Parser: accept at least count expressions accepted by parser
parsers.lisp (file)
Non-backtracking parser: accept as many as possible but at most count of parser
greedy.lisp (file)
Parser: accept at most count expressions accepted by parser
parsers.lisp (file)
Non-backtracking parser: Find a p before q, doesn’t consume q.
greedy.lisp (file)
Non-backtracking parser: find the first, longest chain of expression accepted by parser of length between min and max
greedy.lisp (file)
Parser: accept between min and max expressions accepted by parser
parsers.lisp (file)
Parser: accept parser-center bracketed by parser-open and parser-close
parsers.lisp (file)
Parser: like between? but breadth first (shortest matches first)
parsers.lisp (file)
Non-backtracking parser: like chainl1*, but will return v if no p can be parsed
greedy.lisp (file)
Non-backtracking parser: accept as many as possible, but at least one of p, reduced by result of op with left associativity
greedy.lisp (file)
Parser: accept one or more p reduced by result of op with left associativity
parsers.lisp (file)
Parser: like chainl1?, but will return v if no p can be parsed
parsers.lisp (file)
Non-backtracking parser: like chainr1*, but will return v if no p can be parsed
greedy.lisp (file)
Non-backtracking parser: accept as many as possible, but at least one of p, reduced by result of op with right associativity
greedy.lisp (file)
Parser: accept one or more p reduced by result of op with right associativity
parsers.lisp (file)
Parser: like chainr1?, but will return v if no p can be parsed
parsers.lisp (file)
Parser: accept token eql to argument
ensure-parser.lisp (file)
Combinator: all alternatives from two parsers
combinators.lisp (file)
Combinator: one alternative from two parsers
combinators.lisp (file)
Combinator: all alternatives from multiple parsers
combinators.lisp (file)
Combinator: one alternative from multiple parsers
combinators.lisp (file)
Parser: return result if p matches
parsers.lisp (file)
Parser: return result if p matches, but do no advance
parsers.lisp (file)
Parser: return current context without consuming any input
parsers.lisp (file)
basic.lisp (file)
Parser modifier: add formatted string to tag stack for given parser, suppressing all lower level parsers.
parsers.lisp (file)
Parser: accept digit character
token-parsers.lisp (file)
cache.lisp (file)
Parser: matches end of input, returns t
parsers.lisp (file)
Parser: match p unless q matches.
parsers.lisp (file)
Non-backtracking parser: Reduce a sequence of terms with unary/binary operators with precedence. OPERATORS is a list of (op-parser :left/:right/:unary), where OP-PARSER is a parser consuming an operator and returning a reduction function. Highest precedence first.
greedy.lisp (file)
Parser: Reduce a sequence of terms with unary/binary operators with precedence.
OPERATORS is a list of (op-parser :left/:right/:unary), where OP-PARSER is a parser consuming
an operator and returning a reduction function. Highest precedence first.
parsers.lisp (file)
Non-backtracking parser: Find first q
greedy.lisp (file)
Non-backtracking parser: Find first q after some sequence of p.
greedy.lisp (file)
Non-backtracking parser: Find first q after some sequence of p. Return cons of list of p-results and q
greedy.lisp (file)
Parser: Find q after some sequence of p, earliest match first. Return cons of list of p-results and q
parsers.lisp (file)
Parser: Find q after some sequence of p, earliest matches first.
parsers.lisp (file)
Non-backtracking parser: Find a sequence of p terminated by q, doesn’t consume q.
greedy.lisp (file)
Non-backtracking parser: Find a sequence of p terminated by single token q, which is not consumed.
greedy.lisp (file)
Parser: Find a sequence of p terminated by q, doesn’t consume q.
parsers.lisp (file)
Parser: Find q, earliest match first.
parsers.lisp (file)
Parser modifier: fully realize result from parser
primitives.lisp (file)
Non-backtracking parser: Find a sequence of tokens terminated by single token, which is not consumed.
greedy.lisp (file)
Non-backtracking parser: Find a sequence of tokens terminated by one for which predicate returns true, which is not consumed.
greedy.lisp (file)
Obtain all of the results within PARSE-RESULT, starting with the current one, potentially realising the non-realised ones in the backing store.
basic.lisp (file)
Parser: apply function to result of p
parsers.lisp (file)
Non-backtracking parser: accept integer, consuming as many digits as possible
greedy.lisp (file)
Parser: accept an integer, return as integer.
token-parsers.lisp (file)
Primitive parser: consume item from input and return it.
primitives.lisp (file)
Parser: accept alphabetic character
token-parsers.lisp (file)
Parser: accept lowercase character
token-parsers.lisp (file)
Document all potential results of CONTINUATION as a PARSE-RESULT object.
basic.lisp (file)
Non-backtracking parser: collect as many of first result of parser as possible
greedy.lisp (file)
Non-backtracking parser: accept as many as possible, and at least one, of parser
greedy.lisp (file)
Parser: accept one or more of expression accepted by parser
parsers.lisp (file)
Parser: accept zero or more repetitions of expression accepted by parser
parsers.lisp (file)
Parser modifier: memoizes the parser, which if called again at a given position it will return a result immediately. LABEL is used for memoization key, use explicit one if the parser is used in multiple places.
memoize.lisp (file)
Non-backtracking parser: accept natural number, consuming as many digits as possible
greedy.lisp (file)
Parser: accept natural numbers
token-parsers.lisp (file)
Parser: parse a sequence of p, like between?, but with p possibly nested in brackets.
parsers.lisp (file)
basic.lisp (file)
Non-backtracking parser: result of p or nil
greedy.lisp (file)
Parser: result of p or nil
parsers.lisp (file)
Parse a sequence (where a sequence is any object which implementes CONTEXT interface), return a PARSE-RESULT object. All returned values may share structure.
basic.lisp (file)
Parse a sequence (where a sequence is any object which implementes CONTEXT interface) and
return as multiple values the first result, whether the parse was incomplete, whether it was
successful, the context front and the position frequency table. The context front is an object
containing the context which most advances the input sequence and a list of lists of parser
tags which were current at that point, which allows approximate error reporting. It will be
NIL if the parse is successful and complete. The position frequency table serves profiling
needs and maps sequence positions to the number of times a new context was created at that
position – which should provide a rough hint at how problematic that particular spot is.
If COMPLETE is T, return the first parse to consume the input
completely. If COMPLETE is :FIRST return the first result only when it the whole input was consumed,
or immediately return nil.
basic.lisp (file)
Synonym for parse-sequence. Parse a string, return a PARSE-RESULT object. All returned values may share structure.
basic.lisp (file)
Synonym for parse-sequence*. Parse a string and return as multiple values the first result,
whether the parse was incomplete, whether it was successful, the context front, and the
position frequency table. The context front is an object containing the context which most
advances the input sequence and a list of lists of parser tags which were current at that
point, which allows approximate error reporting. It will be NIL if the parse is successful and
complete. The position frequency table serves profiling needs and maps sequence positions to
the number of times a new context was created at that position – which should provide a rough
hint at how problematic that particular spot is.
If COMPLETE is T, return the first parse to consume the input
completely. If COMPLETE is :FIRST return the first result only when it the whole input was consumed,
or immediately return nil.
basic.lisp (file)
Parser: accept a string of alphabetic characters
greedy.lisp (file)
Parser: accept a string of alphabetic characters
token-parsers.lisp (file)
Parser: accept a string delimited with quote-char, possibly escaped by escape-char, possibly including quotation chars.
token-parsers.lisp (file)
Primitive parser: return v, leaves input unmodified.
primitives.lisp (file)
Parser: return a token satisfying a predicate.
ensure-parser.lisp (file)
Non-backtracking parser: accept as many as possible of parser-item separated by parser-separator.
greedy.lisp (file)
Non-backtracking parser: accept as many as possible of parser-item separated by parser-separator, but at least one.
greedy.lisp (file)
Parser: as sepby1, but returns a list of a result of p and pairs (op p). Mainly a component parser for chains
parsers.lisp (file)
Parser: accept at least one of parser-item separated by parser-separator
parsers.lisp (file)
Parser: accept zero or more of parser-item separated by parser-separator
parsers.lisp (file)
Non-backtracking parser: Return a list of result of PARSERS.
greedy.lisp (file)
Parser: Return a list of results of PARSERS.
parsers.lisp (file)
Non-backtracking parser: accept a sequence of elements with equality tested by TEST.
ensure-parser.lisp (file)
Parser modifier: add formatted string to tag stack for given parser.
parsers.lisp (file)
Parser: accept exactly count expressions accepted by parser
parsers.lisp (file)
Parser: accept uppercase character
token-parsers.lisp (file)
Parser: call validation-function on result of (funcall pre-hook p), fail if it returns nil, otherwhise return it as a result
parsers.lisp (file)
Non-backtracking parser: accept a sequence of whitespace characters.
greedy.lisp (file)
Parser: accept a sequence of whitespace characters.
token-parsers.lisp (file)
Parser: accept a string of alphanumeric characters
greedy.lisp (file)
Parser: accept a string of alphanumeric characters
token-parsers.lisp (file)
Primitive parser: parsing failure
primitives.lisp (file)
Next: Exported classes, Previous: Exported functions, Up: Exported definitions [Contents][Index]
automatically generated reader method
contexts.lisp (file)
automatically generated writer method
contexts.lisp (file)
contexts.lisp (file)
contexts.lisp (file)
automatically generated reader method
contexts.lisp (file)
automatically generated writer method
contexts.lisp (file)
contexts.lisp (file)
Parser gather-if-not* specialized on context type
greedy.lisp (file)
contexts.lisp (file)
contexts.lisp (file)
contexts.lisp (file)
automatically generated reader method
contexts.lisp (file)
automatically generated writer method
contexts.lisp (file)
automatically generated reader method
basic.lisp (file)
automatically generated writer method
basic.lisp (file)
contexts.lisp (file)
automatically generated reader method
contexts.lisp (file)
automatically generated writer method
contexts.lisp (file)
automatically generated reader method
contexts.lisp (file)
automatically generated writer method
contexts.lisp (file)
Implementation of string? specialized on context type. Returns as multiple values result and new context or nil on failure.
ensure-parser.lisp (file)
automatically generated reader method
basic.lisp (file)
automatically generated writer method
basic.lisp (file)
automatically generated reader method
contexts.lisp (file)
automatically generated writer method
contexts.lisp (file)
automatically generated reader method
basic.lisp (file)
automatically generated writer method
basic.lisp (file)
Previous: Exported generic functions, Up: Exported definitions [Contents][Index]
contexts.lisp (file)
context (class)
basic.lisp (file)
standard-object (class)
result-node (class)
:tree
tree-of (generic function)
(setf tree-of) (generic function)
:suffix
suffix-of (generic function)
(setf suffix-of) (generic function)
contexts.lisp (file)
context (class)
Previous: Exported definitions, Up: Definitions [Contents][Index]
| • Internal special variables | ||
| • Internal macros | ||
| • Internal functions | ||
| • Internal generic functions | ||
| • Internal classes |
Next: Internal macros, Previous: Internal definitions, Up: Internal definitions [Contents][Index]
recurse.lisp (file)
parsers.lisp (file)
basic.lisp (file)
cache.lisp (file)
contexts.lisp (file)
Next: Internal functions, Previous: Internal special variables, Up: Internal definitions [Contents][Index]
parsers.lisp (file)
lazy.lisp (file)
ensure-parser.lisp (file)
Next: Internal generic functions, Previous: Internal macros, Up: Internal definitions [Contents][Index]
combinators.lisp (file)
Parser: accept token char-equal to argument
ensure-parser.lisp (file)
basic.lisp (file)
Parser modifier: discard all results but the first
primitives.lisp (file)
basic.lisp (file)
ensure-parser.lisp (file)
combinators.lisp (file)
combinators.lisp (file)
lazy.lisp (file)
Non-backtracking parser: Find a sequence of tokens for which predicate returns true.
greedy.lisp (file)
parsers.lisp (file)
contexts.lisp (file)
queue.lisp (file)
contexts.lisp (file)
queue.lisp (file)
Non-backtracking parser: accept exactly count expressions accepted by parser, without backtracking.
greedy.lisp (file)
Next: Internal classes, Previous: Internal functions, Up: Internal definitions [Contents][Index]
contexts.lisp (file)
automatically generated reader method
contexts.lisp (file)
automatically generated writer method
contexts.lisp (file)
contexts.lisp (file)
contexts.lisp (file)
contexts.lisp (file)
automatically generated reader method
basic.lisp (file)
automatically generated writer method
basic.lisp (file)
automatically generated reader method
parsers.lisp (file)
automatically generated writer method
parsers.lisp (file)
automatically generated reader method
basic.lisp (file)
automatically generated writer method
basic.lisp (file)
automatically generated reader method
basic.lisp (file)
automatically generated writer method
basic.lisp (file)
automatically generated reader method
parsers.lisp (file)
automatically generated writer method
parsers.lisp (file)
True if collection is empty
queue.lisp (file)
contexts.lisp (file)
automatically generated reader method
contexts.lisp (file)
automatically generated writer method
contexts.lisp (file)
automatically generated reader method
queue.lisp (file)
automatically generated writer method
queue.lisp (file)
contexts.lisp (file)
automatically generated reader method
contexts.lisp (file)
automatically generated writer method
contexts.lisp (file)
Attempt to realise all results within PARSE-RESULT-STORE upto and including the N-th one, and return that upon success. Otherwise return NIL.
basic.lisp (file)
Return top element without removing it
queue.lisp (file)
Return value from the back without removing it
queue.lisp (file)
Remove and return value from the front
queue.lisp (file)
Push value to the back
queue.lisp (file)
Push value to the front
queue.lisp (file)
contexts.lisp (file)
automatically generated reader method
contexts.lisp (file)
automatically generated writer method
contexts.lisp (file)
automatically generated reader method
queue.lisp (file)
automatically generated writer method
queue.lisp (file)
automatically generated reader method
basic.lisp (file)
automatically generated writer method
basic.lisp (file)
automatically generated reader method
parsers.lisp (file)
automatically generated writer method
parsers.lisp (file)
automatically generated reader method
queue.lisp (file)
automatically generated writer method
queue.lisp (file)
automatically generated reader method
parsers.lisp (file)
automatically generated writer method
parsers.lisp (file)
contexts.lisp (file)
Previous: Internal generic functions, Up: Internal definitions [Contents][Index]
contexts.lisp (file)
standard-object (class)
:common
common-of (generic function)
(setf common-of) (generic function)
:position
0
position-of (generic function)
(setf position-of) (generic function)
contexts.lisp (file)
standard-object (class)
vector-context-common (class)
:length
0
length-of (generic function)
(setf length-of) (generic function)
:front
(make-instance (quote parser-combinators::context-front))
front-of (generic function)
(setf front-of) (generic function)
:cache
cache-of (generic function)
(setf cache-of) (generic function)
:seen-position
(make-hash-table)
seen-postions-of (generic function)
(setf seen-postions-of) (generic function)
contexts.lisp (file)
standard-object (class)
:context
context-of (generic function)
(setf context-of) (generic function)
:tags
tags-of (generic function)
(setf tags-of) (generic function)
contexts.lisp (file)
context (class)
:storage
storage-of (generic function)
(setf storage-of) (generic function)
Represent a set of parse results, as tracked by STORE, with one of them deemed CURRENT.
basic.lisp (file)
standard-object (class)
:store
store-of (generic function)
(setf store-of) (generic function)
:current
-1
current-of (generic function)
(setf current-of) (generic function)
Track a set of parse results, of which COUNTER are already computed and placed in STORAGE, and an unknown remainder is to be realised by repetitively calling CONTINUATION.
basic.lisp (file)
standard-object (class)
:storage
(make-array 3 :initial-element nil)
storage-of (generic function)
(setf storage-of) (generic function)
:counter
0
counter-of (generic function)
(setf counter-of) (generic function)
:continuation
(constantly nil)
continuation-of (generic function)
(setf continuation-of) (generic function)
lazy.lisp (file)
standard-object (class)
:thunk
thunk-of (generic function)
(setf thunk-of) (generic function)
value-of (generic function)
(setf value-of) (generic function)
queue.lisp (file)
standard-object (class)
head-of (generic function)
(setf head-of) (generic function)
tail-of (generic function)
(setf tail-of) (generic function)
0
size-of (generic function)
(setf size-of) (generic function)
parsers.lisp (file)
parser-possibility (class)
:emit
t
emit-of (generic function)
(setf emit-of) (generic function)
:up
up-of (generic function)
(setf up-of) (generic function)
:count
0
count-of (generic function)
(setf count-of) (generic function)
:suffix-continuation
suffix-continuation-of (generic function)
(setf suffix-continuation-of) (generic function)
contexts.lisp (file)
context-common (class)
:storage
storage-of (generic function)
(setf storage-of) (generic function)
Previous: Definitions, Up: Top [Contents][Index]
| • Concept index | ||
| • Function index | ||
| • Variable index | ||
| • Data type index |
Next: Function index, Previous: Indexes, Up: Indexes [Contents][Index]
| Jump to: | F L P |
|---|
| Jump to: | F L P |
|---|
Next: Variable index, Previous: Concept index, Up: Indexes [Contents][Index]
| Jump to: | %
(
A B C D E F G H I L M N O P Q R S T U V W Z |
|---|
| Jump to: | %
(
A B C D E F G H I L M N O P Q R S T U V W Z |
|---|
Next: Data type index, Previous: Function index, Up: Indexes [Contents][Index]
| Jump to: | *
C E F H L P S T U V |
|---|
| Jump to: | *
C E F H L P S T U V |
|---|
Previous: Variable index, Up: Indexes [Contents][Index]
| Jump to: | C E L P Q R S V |
|---|
| Jump to: | C E L P Q R S V |
|---|