The parser.packrat
library provides an extensible framework for
efficient parsing and pattern matching on different kinds of inputs.
Aspects of this system are inspired by OMeta, optima, and esrap.
Modular/composable grammars
Support for the following kinds of inputs is built in:
- Sequences
- Lists
- Vectors
- of character (i.e. strings)
- of octets
- of bit
- Streams
- of octets
- of characters
- Objects and structures
- Trees
The fundamental concepts are
- expression
- such as src_lisp[:exports code]{(:seq (or #\a #\b) #\c)}
- rule
- Named expression, optionally accepting parameters and optionally transforming the parse result before returning it.
- grammar
- Named collections of rules tied to a particular kind of input. Grammars can use and extend other grammars and rules in one grammar can invoke rules in other grammars.
Defining a grammar
(parser.packrat:defgrammar :integers
(:class parser.packrat.grammar.string:simple-string-grammar))
(parser.packrat:in-grammar :integers)
#<SIMPLE-STRING-GRAMMAR INTEGERS 0 rules {10036A19A3}>
Defining rules
(parser.packrat:defrule digit (base)
(:<- char)
(or (digit-char-p char base) (:fail)))
(parser.packrat:defrule integer (base)
(* (:<<- digits (digit base)) 1)
(loop :for digit :in digits
:for weight = 1 :then (* base weight)
:sum (* weight digit)))
#<RULE INTEGER {205B9F0B}>
Applying rules to inputs
(list (list* #1="1234" #2=10 (multiple-value-list (parser.packrat:parse '((integer :integers) #2#) #1#)))
(list* #3="bee" #4=16 (multiple-value-list (parser.packrat:parse '((integer :integers) #4#) #3#)))
(list* #5="beef" #6=16 (multiple-value-list (parser.packrat:parse '((integer :integers) #6#) #5#))))
input | base | success? | consumed | value |
---|---|---|---|---|
1234 | 10 | T | 4 | 1234 |
bee | 16 | T | 3 | 3054 |
beef | 16 | T | 4 | 48879 |
src
- Source code
grammar
- Grammar protocols
base
- Base Grammar
sequence
- Sequence Grammar
sexp
- S-expression Grammar
test
- Unit tests
examples
- Examples
types and programming languages
- Solutions to some of the exercises of the book, obviously using a parsing- and pattern-matching-heavy style.
documentation
- Documentation
- <<grammar-base-grammar>>
base-grammar
Grammar Classnot documented
- <<rule-base-grammar:and-expression>>
AND-EXPRESSION ::= (AND «anything» (LIST 'AND (* (~[[rule-base-grammar:expression!][~expression!~]] ~ (VARIABLE-REFERENCE-EXPRESSION)))))
- <<rule-base-grammar:anything-expression>>
ANYTHING-EXPRESSION ::= (OR ANY 'ANY)
- <<rule-base-grammar:compose-expression>>
COMPOSE-EXPRESSION ::= (AND «anything» (LIST COMPOSE (* (~[[rule-base-grammar:expression!][~expression!~]] ~ (VARIABLE-REFERENCE-EXPRESSION)))))
- <<rule-base-grammar:constant-expression>>
CONSTANT-EXPRESSION ::= (AND «anything» (OR (LIST 'QUOTE «anything») (GUARD «anything» (TYPEP '(NOT (OR CONS (AND SYMBOL (NOT KEYWORD))))))))
- <<rule-base-grammar:expression>>
EXPRESSION ::= (OR (~[[rule-base-grammar:predicate-expression][~predicate-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-base-grammar:anything-expression][~anything-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-base-grammar:position-expression][~position-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-base-grammar:constant-expression][~constant-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-base-grammar:set-expression][~set-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-base-grammar:push-expression][~push-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-base-grammar:must-expression][~must-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-base-grammar:not-expression][~not-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-base-grammar:and-expression][~and-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-base-grammar:or-expression][~or-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-base-grammar:compose-expression][~compose-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-base-grammar:transform-expression][~transform-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-base-grammar:value-expression][~value-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-base-grammar:next-rule-invocation-expression][~next-rule-invocation-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-base-grammar:rule-invocation-expression][~rule-invocation-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)))
- <<rule-base-grammar:expression!>>
EXPRESSION! ::= (MUST-EXPRESSION (~[[rule-base-grammar:expression][~expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)))
- <<rule-base-grammar:function-name-or-partial-application>>
FUNCTION-NAME-OR-PARTIAL-APPLICATION ::= (OR (GUARD «anything» SYMBOLP) (LIST (GUARD «anything» SYMBOLP) (REST-EXPRESSION «anything»)))
- <<rule-base-grammar:function-name-or-partial-application!>>
FUNCTION-NAME-OR-PARTIAL-APPLICATION! ::= (MUST-EXPRESSION (~[[rule-base-grammar:function-name-or-partial-application][~function-name-or-partial-application~]] ~))
- <<rule-base-grammar:grammar-name>>
GRAMMAR-NAME ::= (GUARD «anything» SYMBOLP)
- <<rule-base-grammar:grammar-name!>>
GRAMMAR-NAME! ::= (MUST-EXPRESSION (~[[rule-base-grammar:grammar-name][~grammar-name~]] ~))
- <<rule-base-grammar:implicit-list>>
IMPLICIT-LIST ::= (AND «anything» (LIST (+ (~[[rule-base-grammar:variable-name!][~variable-name!~]] ~))))
- <<rule-base-grammar:must-expression>>
MUST-EXPRESSION ::= (AND «anything» (LIST (OR MUST 'MUST) (~[[rule-base-grammar:expression!][~expression!~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (? (GUARD «anything» STRINGP))))
- <<rule-base-grammar:next-rule-invocation-expression>>
NEXT-RULE-INVOCATION-EXPRESSION ::= (AND «anything» (LIST (OR NEXT-RULE 'NEXT-RULE) (* (~[[rule-base-grammar:expression!][~expression!~]] ~ VALUE))))
- <<rule-base-grammar:not-expression>>
NOT-EXPRESSION ::= (AND «anything» (LIST 'NOT (~[[rule-base-grammar:expression!][~expression!~]] ~ (VARIABLE-REFERENCE-EXPRESSION))))
- <<rule-base-grammar:or-expression>>
OR-EXPRESSION ::= (AND «anything» (LIST 'OR (* (~[[rule-base-grammar:expression!][~expression!~]] ~ (VARIABLE-REFERENCE-EXPRESSION)))))
- <<rule-base-grammar:position-expression>>
POSITION-EXPRESSION ::= 'POSITION
- <<rule-base-grammar:predicate-expression>>
PREDICATE-EXPRESSION ::= (AND «anything» (LIST (OR GUARD 'GUARD) (OR (SEQUENCE-EXPRESSION ((~[[rule-base-grammar:expression!][~expression!~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-base-grammar:function-name-or-partial-application!][~function-name-or-partial-application!~]] ~))) (~[[rule-base-grammar:function-name-or-partial-application!][~function-name-or-partial-application!~]] ~))))
- <<rule-base-grammar:push-expression>>
PUSH-EXPRESSION ::= (OR (~[[rule-base-grammar:push-expression/simple][~push-expression/simple~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-base-grammar:push-expression/compose][~push-expression/compose~]] ~ (VARIABLE-REFERENCE-EXPRESSION)))
- <<rule-base-grammar:push-expression/compose>>
PUSH-EXPRESSION/COMPOSE ::= (AND «anything» (LIST '<<- (OR (~[[rule-base-grammar:implicit-list][~implicit-list~]] ~ PUSH) (~[[rule-base-grammar:expression!][~expression!~]] ~ (VARIABLE-REFERENCE-EXPRESSION))) (* (~[[rule-base-grammar:expression!][~expression!~]] ~ (VARIABLE-REFERENCE-EXPRESSION)))))
- <<rule-base-grammar:push-expression/simple>>
PUSH-EXPRESSION/SIMPLE ::= (AND «anything» (LIST (OR <<- '<<-) (AND (NOT LIST (REST-EXPRESSION «anything»)) (~[[rule-base-grammar:variable-name!][~variable-name!~]] ~)) (? (~[[rule-base-grammar:expression!][~expression!~]] ~ (VARIABLE-REFERENCE-EXPRESSION)))))
- <<rule-base-grammar:rule-invocation-expression>>
RULE-INVOCATION-EXPRESSION ::= (AND «anything» (LIST (OR (LIST (~[[rule-base-grammar:rule-name!][~rule-name!~]] ~) (~[[rule-base-grammar:grammar-name!][~grammar-name!~]] ~)) (~[[rule-base-grammar:rule-name][~rule-name~]] ~)) (* (~[[rule-base-grammar:expression!][~expression!~]] ~ VALUE))))
- <<rule-base-grammar:rule-name>>
RULE-NAME ::= (GUARD «anything» SYMBOLP)
- <<rule-base-grammar:rule-name!>>
RULE-NAME! ::= (MUST-EXPRESSION (~[[rule-base-grammar:rule-name][~rule-name~]] ~))
- <<rule-base-grammar:set-expression>>
SET-EXPRESSION ::= (OR (~[[rule-base-grammar:set-expression/simple][~set-expression/simple~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-base-grammar:set-expression/compose][~set-expression/compose~]] ~ (VARIABLE-REFERENCE-EXPRESSION)))
- <<rule-base-grammar:set-expression/compose>>
SET-EXPRESSION/COMPOSE ::= (AND «anything» (LIST '<- (OR (~[[rule-base-grammar:implicit-list][~implicit-list~]] ~ SET) (~[[rule-base-grammar:expression!][~expression!~]] ~ (VARIABLE-REFERENCE-EXPRESSION))) (* (~[[rule-base-grammar:expression!][~expression!~]] ~ (VARIABLE-REFERENCE-EXPRESSION)))))
- <<rule-base-grammar:set-expression/simple>>
SET-EXPRESSION/SIMPLE ::= (AND «anything» (OR (~[[rule-base-grammar:variable-name][~variable-name~]] ~) (LIST (OR <- '<-) (AND (NOT LIST (REST-EXPRESSION «anything»)) (~[[rule-base-grammar:variable-name!][~variable-name!~]] ~)) (? (~[[rule-base-grammar:expression!][~expression!~]] ~ (VARIABLE-REFERENCE-EXPRESSION))))))
- <<rule-base-grammar:transform-expression>>
TRANSFORM-EXPRESSION ::= (AND «anything» (LIST (OR TRANSFORM 'TRANSFORM) (~[[rule-base-grammar:expression!][~expression!~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (REST-EXPRESSION «anything»)))
- <<rule-base-grammar:value-expression>>
VALUE-EXPRESSION ::= (LIST 'VALUE (LIST «anything») «anything»)
- <<rule-base-grammar:variable-name>>
VARIABLE-NAME ::= (GUARD «anything» (TYPEP '(AND SYMBOL (NOT (OR KEYWORD NULL)))))
- <<rule-base-grammar:variable-name!>>
VARIABLE-NAME! ::= (MUST-EXPRESSION (~[[rule-base-grammar:variable-name][~variable-name~]] ~))
- <<rule-base-grammar:and-expression>>
- <<grammar-sequence-grammar>>
sequence-grammar
Grammar Classnot documented
- <<rule-sequence-grammar:+-expression>>
+-EXPRESSION ::= (LIST '+ «anything»)
- <<rule-sequence-grammar:?-expression>>
?-EXPRESSION ::= (LIST '? «anything»)
- <<rule-sequence-grammar:bounds-expression>>
BOUNDS-EXPRESSION ::= (LIST 'BOUNDS (LIST (MUST-EXPRESSION (GUARD «anything» SYMBOLP)) (MUST-EXPRESSION (GUARD «anything» SYMBOLP))) (REST-EXPRESSION «anything»))
- <<rule-sequence-grammar:expression>>
EXPRESSION ::= (OR (~[[rule-sequence-grammar:repetition-expression][~repetition-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-sequence-grammar:sequence-expression][~sequence-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-sequence-grammar:?-expression][
?-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) ([[rule-sequence-grammar:+-expression][~+-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-sequence-grammar:bounds-expression][~bounds-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)))
- <<rule-sequence-grammar:repetition-expression>>
REPETITION-EXPRESSION ::= (LIST '* (~[[rule-sequence-grammar:expression][~expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (* (SEQUENCE-EXPRESSION ((~[[rule-sequence-grammar:expression][~expression~]] ~ VALUE) (* (~[[rule-sequence-grammar:expression][~expression~]] ~ VALUE))))))
- <<rule-sequence-grammar:sequence-expression>>
SEQUENCE-EXPRESSION ::= (AND «anything» (LIST (OR SEQ 'SEQ) (* (~[[rule-sequence-grammar:expression][~expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)))))
- <<rule-sequence-grammar:+-expression>>
- <<grammar-sexp-grammar>>
sexp-grammar
Grammar ClassA grammar class for matching Lisp objects.
In particular, this grammar class adds constructs for matching lists (`list’, `list*’, `rest’), vectors (`vector’, `vector*’) and structures including conses (`structure’, `cons’).
Rules defined in grammars of this class operate on objects but can switch to sequence-based processing using the `as-list’ and `as-vector’ constructs.
- <<rule-sexp-grammar:cons-expression>>
CONS-EXPRESSION ::= (LIST 'CONS «anything» «anything»)
- <<rule-sexp-grammar:expression>>
EXPRESSION ::= (OR (~[[rule-sexp-grammar:structure-expression][~structure-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-sexp-grammar:list-elements-expression][~list-elements-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-sexp-grammar:rest-expression][~rest-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-sexp-grammar:vector-elements-expression][~vector-elements-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-sexp-grammar:list-expression][~list-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-sexp-grammar:list*-expression][~list*-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-sexp-grammar:vector-expression][~vector-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-sexp-grammar:vector*-expression][~vector*-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-sexp-grammar:cons-expression][~cons-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-sexp-grammar:value-expression][~value-expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-meta-grammar:expression][~meta-grammar:expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-meta-grammar:expression][~meta-grammar:expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)))
- <<rule-sexp-grammar:list*-expression>>
LIST*-EXPRESSION ::= (LIST 'LIST* (* (AND (SEQUENCE-EXPRESSION («anything» «anything»)) «anything»)) «anything»)
- <<rule-sexp-grammar:list-elements-expression>>
LIST-ELEMENTS-EXPRESSION ::= (AND «anything» (LIST 'LIST-ELEMENTS (~[[rule-sexp-grammar:expression!][~expression!~]] ~ (VARIABLE-REFERENCE-EXPRESSION))))
- <<rule-sexp-grammar:list-expression>>
LIST-EXPRESSION ::= (LIST 'LIST (REST-EXPRESSION «anything»))
- <<rule-sexp-grammar:rest-expression>>
REST-EXPRESSION ::= (AND «anything» (LIST 'REST (~[[rule-sexp-grammar:expression!][~expression!~]] ~ (VARIABLE-REFERENCE-EXPRESSION))))
- <<rule-sexp-grammar:structure-expression>>
STRUCTURE-EXPRESSION ::= (AND «anything» (LIST 'STRUCTURE (~[[rule-sexp-grammar:expression!][~expression!~]] ~ VALUE) (* (AND (LIST (REST-EXPRESSION «anything»)) (MUST-EXPRESSION (LIST «anything» (~[[rule-sexp-grammar:expression!][~expression!~]] ~ (VARIABLE-REFERENCE-EXPRESSION))))))))
- <<rule-sexp-grammar:value-expression>>
VALUE-EXPRESSION ::= (LIST 'VALUE (LIST (~[[rule-sexp-grammar:variable-name!][~variable-name!~]] ~)) (~[[rule-sexp-grammar:expression!][~expression!~]] ~ (VARIABLE-REFERENCE-EXPRESSION)))
- <<rule-sexp-grammar:vector*-expression>>
VECTOR*-EXPRESSION ::= (LIST 'VECTOR* (REST-EXPRESSION «anything»))
- <<rule-sexp-grammar:vector-elements-expression>>
VECTOR-ELEMENTS-EXPRESSION ::= (AND «anything» (LIST 'VECTOR-ELEMENTS (~[[rule-sexp-grammar:expression!][~expression!~]] ~ (VARIABLE-REFERENCE-EXPRESSION))))
- <<rule-sexp-grammar:vector-expression>>
VECTOR-EXPRESSION ::= (LIST 'VECTOR (REST-EXPRESSION «anything»))
- <<rule-sexp-grammar:cons-expression>>
- <<grammar-simple-string-grammar>>
simple-string-grammar
Grammar Classnot documented
- <<rule-simple-string-grammar:expression>>
EXPRESSION ::= (OR (~[[rule-meta-grammar:expression][~meta-grammar:expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)) (~[[rule-meta-grammar:expression][~meta-grammar:expression~]] ~ (VARIABLE-REFERENCE-EXPRESSION)))
- <<rule-simple-string-grammar:expression>>
- <<grammar-stream-grammar>>
stream-grammar
Grammar Classnot documented