Common Lisp Package: PARSER-COMBINATORS

README:

FUNCTION

Public

ALPHANUM?

Parser: accept alphanumeric character

ATLEAST* (PARSER COUNT)

Non-backtracking parser: accept as many as possible and at least count of parser

ATLEAST? (PARSER COUNT)

Parser: accept at least count expressions accepted by parser

ATMOST* (PARSER COUNT)

Non-backtracking parser: accept as many as possible but at most count of parser

ATMOST? (PARSER COUNT)

Parser: accept at most count expressions accepted by parser

BETWEEN* (PARSER MIN MAX &OPTIONAL (RESULT-TYPE 'LIST))

Non-backtracking parser: find the first, longest chain of expression accepted by parser of length between min and max

BETWEEN? (PARSER MIN MAX &OPTIONAL (RESULT-TYPE 'LIST))

Parser: accept between min and max expressions accepted by parser

BRACKET? (PARSER-OPEN PARSER-CENTER PARSER-CLOSE)

Parser: accept parser-center bracketed by parser-open and parser-close

BREADTH? (PARSER MIN MAX &OPTIONAL (RESULT-TYPE 'LIST))

Parser: like between? but breadth first (shortest matches first)

CHAINL* (P OP V)

Non-backtracking parser: like chainl1*, but will return v if no p can be parsed

CHAINL1* (P OP)

Non-backtracking parser: accept as many as possible, but at least one of p, reduced by result of op with left associativity

CHAINL1? (P OP)

Parser: accept one or more p reduced by result of op with left associativity

CHAINL? (P OP V)

Parser: like chainl1?, but will return v if no p can be parsed

CHAINR* (P OP V)

Non-backtracking parser: like chainr1*, but will return v if no p can be parsed

CHAINR1* (P OP)

Non-backtracking parser: accept as many as possible, but at least one of p, reduced by result of op with right associativity

CHAINR1? (P OP)

Parser: accept one or more p reduced by result of op with right associativity

CHAINR? (P OP V)

Parser: like chainr1?, but will return v if no p can be parsed

CHAR? (CHARACTER)

Parser: accept token eql to argument

CHOICE (PARSER1 PARSER2)

Combinator: all alternatives from two parsers

CHOICE1 (PARSER1 PARSER2)

Combinator: one alternative from two parsers

CHOICES (&REST PARSER-LIST)

Combinator: all alternatives from multiple parsers

CHOICES1 (&REST PARSER-LIST)

Combinator: one alternative from multiple parsers

CHOOK? (RESULT P)

Parser: return result if p matches

CONTEXT?

Parser: return current context without consuming any input

CUT-TAG? (PARSER FORMAT-CONTROL &REST FORMAT-ARGUMENTS)

Parser modifier: add formatted string to tag stack for given parser, suppressing all lower level parsers.

DIGIT?

Parser: accept digit character

END?

Parser: matches end of input, returns t

EXCEPT? (P Q)

Parser: match p unless q matches.

EXPRESSION* (TERM OPERATORS &OPTIONAL (BRACKET-LEFT NIL) (BRACKET-RIGHT NIL))

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.

EXPRESSION? (TERM OPERATORS &OPTIONAL (BRACKET-LEFT NIL) (BRACKET-RIGHT NIL))

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.

FIND* (Q)

Non-backtracking parser: Find first q

FIND-AFTER* (P Q)

Non-backtracking parser: Find first q after some sequence of p.

FIND-AFTER-COLLECT* (P Q &OPTIONAL (RESULT-TYPE 'LIST))

Non-backtracking parser: Find first q after some sequence of p. Return cons of list of p-results and q

FIND-AFTER-COLLECT? (P Q &OPTIONAL (RESULT-TYPE 'LIST))

Parser: Find q after some sequence of p, earliest match first. Return cons of list of p-results and q

FIND-AFTER? (P Q)

Parser: Find q after some sequence of p, earliest matches first.

FIND-BEFORE* (P Q &OPTIONAL (RESULT-TYPE 'LIST))

Non-backtracking parser: Find a sequence of p terminated by q, doesn't consume q.

FIND-BEFORE-TOKEN* (P TOKEN &KEY (RESULT-TYPE 'LIST) (TEST #'EQL))

Non-backtracking parser: Find a sequence of p terminated by single token q, which is not consumed.

FIND-BEFORE? (P Q &OPTIONAL (RESULT-TYPE 'LIST))

Parser: Find a sequence of p terminated by q, doesn't consume q.

FIND? (Q)

Parser: Find q, earliest match first.

FORCE? (PARSER)

Parser modifier: fully realize result from parser

GATHER-BEFORE-TOKEN* (TOKEN &KEY (RESULT-TYPE 'LIST) (TEST #'EQL) (ACCEPT-END NIL) (ACCEPT-EMPTY NIL))

Non-backtracking parser: Find a sequence of tokens terminated by single token, which is not consumed.

GATHER-IF-NOT* (PREDICATE &KEY (RESULT-TYPE 'LIST) (ACCEPT-END NIL) (ACCEPT-EMPTY NIL))

Non-backtracking parser: Find a sequence of tokens terminated by one for which predicate returns true, which is not consumed.

HOOK? (FUNCTION P)

Parser: apply function to result of p

INT* (&OPTIONAL (RADIX 10))

Non-backtracking parser: accept integer, consuming as many digits as possible

INT? (&OPTIONAL (RADIX 10))

Parser: accept an integer, return as integer.

ITEM

Primitive parser: consume item from input and return it.

LETTER?

Parser: accept alphabetic character

LOWER?

Parser: accept lowercase character

MANY* (PARSER)

Non-backtracking parser: collect as many of first result of parser as possible

MANY1* (PARSER)

Non-backtracking parser: accept as many as possible, and at least one, of parser

MANY1? (PARSER)

Parser: accept one or more of expression accepted by parser

MANY? (PARSER)

Parser: accept zero or more repetitions of expression accepted by parser

MEMOIZE? (PARSER &OPTIONAL (LABEL (GENSYM)))

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.

NAT* (&OPTIONAL (RADIX 10))

Non-backtracking parser: accept natural number, consuming as many digits as possible

NAT? (&OPTIONAL (RADIX 10))

Parser: accept natural numbers

NESTED? (P &KEY (MIN NIL) (MAX NIL) (RESULT-TYPE 'LIST) (BRACKET-LEFT () (BRACKET-RIGHT )))

Parser: parse a sequence of p, like between?, but with p possibly nested in brackets.

OPT* (P)

Non-backtracking parser: result of p or nil

OPT? (P)

Parser: result of p or nil

PARSE-SEQUENCE (PARSER SEQUENCE)

Parse a sequence (where a sequence is any object which implementes CONTEXT interface), return a PARSE-RESULT object. All returned values may share structure.

PARSE-SEQUENCE* (PARSER SEQUENCE &KEY (COMPLETE NIL))

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, and the context front. The context front is an object containg 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. 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.

PARSE-STRING (PARSER STRING)

Synonym for parse-sequence. Parse a string, return a PARSE-RESULT object. All returned values may share structure.

PARSE-STRING* (PARSER STRING &KEY (COMPLETE NIL))

Synonym for parse-sequence*. Parse a string and return as multiple values the first result, whether the parse was incomplete, whether it was successful, and the context front. The context front is an object containg 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. 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.

PURE-WORD*

Parser: accept a string of alphabetic characters

PURE-WORD?

Parser: accept a string of alphabetic characters

QUOTED? (&KEY (QUOTE-CHAR ") (LEFT-QUOTE-CHAR NIL) (RIGHT-QUOTE-CHAR NIL) (ESCAPE-CHAR \) (INCLUDE-QUOTES T))

Parser: accept a string delimited with quote-char, possibly escaped by escape-char, possibly including quotation chars.

RESULT (V)

Primitive parser: return v, leaves input unmodified.

SAT (PREDICATE)

Parser: return a token satisfying a predicate.

SEPBY* (PARSER-ITEM PARSER-SEPARATOR)

Non-backtracking parser: accept as many as possible of parser-item separated by parser-separator.

SEPBY1* (PARSER-ITEM PARSER-SEPARATOR)

Non-backtracking parser: accept as many as possible of parser-item separated by parser-separator, but at least one.

SEPBY1-CONS? (P OP)

Parser: as sepby1, but returns a list of a result of p and pairs (op p). Mainly a component parser for chains

SEPBY1? (PARSER-ITEM PARSER-SEPARATOR)

Parser: accept at least one of parser-item separated by parser-separator

SEPBY? (PARSER-ITEM PARSER-SEPARATOR)

Parser: accept zero or more of parser-item separated by parser-separator

SEQ-LIST* (&REST PARSERS)

Non-backtracking parser: Return a list of result of PARSERS.

SEQ-LIST? (&REST PARSERS)

Parser: Return a list of results of PARSERS.

STRING? (SEQUENCE &KEY (TEST #'EQL) (RESULT-TYPE 'STRING))

Non-backtracking parser: accept a sequence of elements with equality tested by TEST.

TAG? (PARSER FORMAT-CONTROL &REST FORMAT-ARGUMENTS)

Parser modifier: add formatted string to tag stack for given parser.

TIMES? (PARSER COUNT)

Parser: accept exactly count expressions accepted by parser

UPPER?

Parser: accept uppercase character

VALIDATE? (P VALIDATION-FUNCTION &OPTIONAL (PRE-HOOK #'IDENTITY))

Parser: call validation-function on result of (funcall pre-hook p), fail if it returns nil, otherwhise return it as a result

WHITESPACE* (&KEY (RESULT-TYPE NIL) (ACCEPT-EMPTY NIL))

Non-backtracking parser: accept a sequence of whitespace characters.

WHITESPACE? (&KEY (RESULT-TYPE NIL) (ACCEPT-EMPTY NIL))

Parser: accept a sequence of whitespace characters.

WORD*

Parser: accept a string of alphanumeric characters

WORD?

Parser: accept a string of alphanumeric characters

ZERO

Primitive parser: parsing failure

Undocumented

CURRENT-RESULT (PARSE-RESULT)

DROP-PARSER-CACHE

GATHER-RESULTS (PARSE-RESULT)

MAKE-PARSE-RESULT (CONTINUATION)

NEXT-RESULT (PARSE-RESULT)

Private

CHAR-EQUAL? (CHARACTER)

Parser: accept token char-equal to argument

CUT? (PARSER)

Parser modifier: discard all results but the first

GATHER-IF* (PREDICATE &KEY (RESULT-TYPE 'LIST) (ACCEPT-END T) (ACCEPT-EMPTY NIL))

Non-backtracking parser: Find a sequence of tokens for which predicate returns true.

TIMES* (PARSER COUNT)

Non-backtracking parser: accept exactly count expressions accepted by parser, without backtracking.

Undocumented

BIND (PARSER PARSER-GENERATOR)

COPY-PARSE-RESULT (PARSE-RESULT)

DO-NOTATION (MONAD-SEQUENCE BIND IGNORE-GENSYM)

ENSURE-PARSER (PARSER)

EXECUTE-BIND (INP PARSER PARSER-GENERATOR)

EXECUTE-CHOICE (INP PARSER1 PARSER2)

FORCE (PROMISE)

GATHER-NODES (NODE)

MAKE-CACHE (CACHE-TYPE LENGTH)

MAKE-QUEUE (&OPTIONAL INITIAL-CONTENTS)

QUEUE-TO-LIST (QUEUE)

MACRO

Public

CACHED-ARGUMENTS? (PARSER LABEL &REST ARGUMENTS)

Parser modifier macro: cache parser as label with argument list equal under equal in global cache.

CACHED? (PARSER LABEL)

Parser modifier macro: cache parser as label in global cache.

CURTAIL? (NAME &BODY BODY)

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?`.

DEF-CACHED-ARG-PARSER (NAME ARGUMENTS &BODY BODY)

Define cached parser with arguments.

DEF-CACHED-PARSER (NAME &BODY BODY)

Define cached parser of no arguments.

DELAYED? (PARSER)

Parser modifier macro: parser will be built when called. This is necessary for left-recursive parsers.

MDO (&BODY SPEC)

Combinator: use do-like notation to sequentially link parsers. (<- name parser) allows capturing of return values.

NAMED-SEQ* (&REST PARSER-DESCRIPTIONS)

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.

NAMED-SEQ? (&REST PARSER-DESCRIPTIONS)

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.

NAMED? (NAME &BODY BODY)

Parser macro: give BODY a NAME, so it can refer to itself without causing generator recursion.

Undocumented

COPY-CONTEXT (CONTEXT CLASS &REST ADDITIONAL-ARGUMENTS)

DEFINE-ONESHOT-RESULT (INP IS-UNREAD &BODY BODY)

Private

Undocumented

%NAMED-SEQ? (SEQUENCE-PARSER &REST PARSER-DESCRIPTIONS)

DELAY (&BODY BODY)

WITH-PARSERS ((&REST PARSERS) &BODY BODY)

GENERIC-FUNCTION

Public

GATHER-IF-NOT*-USING-CONTEXT (INPUT PREDICATE ACCEPT-END ACCEPT-EMPTY)

Parser gather-if-not* specialized on context type

STRING?-USING-CONTEXT (INPUT VECTOR TEST)

Implementation of string? specialized on context type. Returns as multiple values result and new context or nil on failure.

Undocumented

CONTEXT-EQUAL (CONTEXT1 CONTEXT2)

CONTEXT-INTERVAL (CONTEXT1 CONTEXT2 &OPTIONAL RESULT-TYPE)

END-CONTEXT-P (CONTEXT)

MAKE-CONTEXT (SEQUENCE &OPTIONAL CACHE-TYPE)

MAKE-CONTEXT-AT-POSITION (BASE-CONTEXT POSITION)

Private

EMPTY-P (COLLECTION)

True if collection is empty

PEEK (COLLECTION)

Return top element without removing it

PEEK-BACK (COLLECTION)

Return value from the back without removing it

POP-FRONT (COLLECTION)

Remove and return value from the front

PUSH-BACK (COLLECTION VALUE)

Push value to the back

PUSH-FRONT (COLLECTION VALUE)

Push value to the front

Undocumented

CONTEXT-GREATER (CONTEXT1 CONTEXT2)

CONTEXT-NEXT (CONTEXT)

CONTEXT-PEEK (CONTEXT)

NTH-RESULT (N PARSE-RESULT-STORE)

UPDATE-FRONT-CONTEXT (CONTEXT)

SLOT-ACCESSOR

Public

Undocumented

COMMON-OF (OBJECT)

SETFCOMMON-OF (NEW-VALUE OBJECT)

CONTEXT-OF (OBJECT)

SETFCONTEXT-OF (NEW-VALUE OBJECT)

POSITION-OF (OBJECT)

SETFPOSITION-OF (NEW-VALUE OBJECT)

STORAGE-OF (OBJECT)

SETFSTORAGE-OF (NEW-VALUE OBJECT)

SUFFIX-OF (OBJECT)

SETFSUFFIX-OF (NEW-VALUE OBJECT)

TAGS-OF (OBJECT)

SETFTAGS-OF (NEW-VALUE OBJECT)

TREE-OF (OBJECT)

SETFTREE-OF (NEW-VALUE OBJECT)

Private

Undocumented

CACHE-OF (OBJECT)

SETFCACHE-OF (NEW-VALUE OBJECT)

CONTINUATION-OF (OBJECT)

SETFCONTINUATION-OF (NEW-VALUE OBJECT)

COUNT-OF (OBJECT)

SETFCOUNT-OF (NEW-VALUE OBJECT)

COUNTER-OF (OBJECT)

SETFCOUNTER-OF (NEW-VALUE OBJECT)

CURRENT-OF (OBJECT)

SETFCURRENT-OF (NEW-VALUE OBJECT)

EMIT-OF (OBJECT)

SETFEMIT-OF (NEW-VALUE OBJECT)

FRONT-OF (OBJECT)

SETFFRONT-OF (NEW-VALUE OBJECT)

HEAD-OF (OBJECT)

SETFHEAD-OF (NEW-VALUE OBJECT)

LENGTH-OF (OBJECT)

SETFLENGTH-OF (NEW-VALUE OBJECT)

SIZE-OF (OBJECT)

SETFSIZE-OF (NEW-VALUE OBJECT)

STORE-OF (OBJECT)

SETFSTORE-OF (NEW-VALUE OBJECT)

SUFFIX-CONTINUATION-OF (OBJECT)

SETFSUFFIX-CONTINUATION-OF (NEW-VALUE OBJECT)

TAIL-OF (OBJECT)

SETFTAIL-OF (NEW-VALUE OBJECT)

THUNK-OF (OBJECT)

SETFTHUNK-OF (NEW-VALUE OBJECT)

UP-OF (OBJECT)

SETFUP-OF (NEW-VALUE OBJECT)

VALUE-OF (OBJECT)

SETFVALUE-OF (NEW-VALUE OBJECT)

VARIABLE

Public

Undocumented

*DEFAULT-CONTEXT-CACHE*

Private

Undocumented

*CURTAIL*

*CUT-TAG*

*MEMO-TABLE*

*PARSER-CACHE*

*TAG-STACK*

CLASS

Public

Undocumented

END-CONTEXT

PARSER-POSSIBILITY

VECTOR-CONTEXT

Private

Undocumented

CONTEXT

CONTEXT-COMMON

CONTEXT-FRONT

LIST-CONTEXT

PARSE-RESULT

PARSE-RESULT-STORE

PROMISE

QUEUE

RESULT-NODE

VECTOR-CONTEXT-COMMON