tur/parsec
typed parser combinators over a backtracking result list.
A (Parser A) reads text and produces an A. Build small parsers -- (pchar #\=), (satisfy digit?), (pstring "true") -- and combine them with do-m (sequencing), alt-or (choice), fmap (transforming a result), many / many1 / optional / sep-by (repetition), then run the result with parse-first, run-parser-full or run-parser. Every combinator is typed: characters are Char, repetition yields a (List A), an optional piece an (Option A), a literal a String.
Parsing is fully backtracking: alt-or keeps the successes of both branches and a runner picks the first that consumed all of the input. many, many1 and optional are greedy (one result each).
See docs/guides/parsec-tutorial.md and docs/guides/parsec-guide.md.
Since: Phase B1 (typed surface: parsec-guide-plan)
Parser
(defopaque Parser [A] :ptr<void>)
a kind-(* -> *) handle over a backtracking parser; carrier is the fat-closure pointer (Input -> list (Pair A Input)).
Since: stdlib-hkt-consolidation T2
mzero
(mzero :int)
return the empty backtracking result (failure).
0, the null pointer representing no results.
(mzero) ; => 0
mreturn
(mreturn [x] :int)
lift a single value into the backtracking monad.
| x | the int64_t value to wrap. |
A newly allocated Cell containing x with a null next pointer.
(mreturn 42) ; => Cell{value=42, next=NULL}
mplus
(mplus [xs ys] :int)
concatenate two backtracking result lists.
| xs | the first Cell list (copied into a fresh list). | |
| ys | the second Cell list (appended by pointer, not copied). |
A new Cell list containing all results from xs followed by ys.
(mplus (mreturn 1) (mreturn 2)) ; => Cell{1} -> Cell{2}
mbind
(mbind [ma :int ^borrow ^fat fn :(fn [int] int)] :int)
monadic bind for the backtracking monad.
| ma | a Cell list of values to thread through fn. | |
| fn | a fat closure (fn [int] int): a value to a Cell list. |
The concatenated results of applying fn to every value in ma, preserving original order.
(mbind (mreturn 1) (fn [x] (mreturn (* x 2)))) ; => Cell{2}
bt-nil
(bt-nil :int)
return the empty backtracking list.
0 (null pointer).
bt-cons
(bt-cons [v nxt] :int)
prepend a value onto a backtracking Cell list.
| v | the int64_t value to prepend. | |
| nxt | the existing Cell list to prepend onto. |
A new Cell with value v pointing to nxt.
(bt-cons 3 (bt-nil)) ; => Cell{3, NULL}
bt-length
(bt-length [xs] :int)
count elements in a backtracking Cell list.
| xs | the Cell list to measure. |
The number of cells in the list as an int64_t.
(bt-length (bt-cons 1 (bt-cons 2 (bt-nil)))) ; => 2
pair-new
(pair-new [a b] :int)
allocate a new Pair holding two int64_t values.
| a | the first field value. | |
| b | the second field value. |
Pointer (as int64_t) to a heap-allocated Pair{first=a, second=b}.
(pair-new 1 2) ; => Pair{first=1, second=2}
pair-first
(pair-first [p] :int)
extract the first field from a Pair.
| p | pointer (as int64_t) to a Pair. |
The int64_t value stored in the first field.
(pair-first (pair-new 7 8)) ; => 7
pair-second
(pair-second [p] :int)
extract the second field from a Pair.
| p | pointer (as int64_t) to a Pair. |
The int64_t value stored in the second field.
(pair-second (pair-new 7 8)) ; => 8
input-new
(input-new [s :cstr pos] :int)
create a new Input from a C string and a starting position.
| s | the source string (:cstr). | |
| pos | the initial character position (0-based). |
Pointer (as int64_t) to a heap-allocated Input{str, pos}.
(input-new "hello" 0) ; => Input at position 0
input-at-end
(input-at-end [inp] :bool)
test whether an Input is at the end of its string.
| inp | pointer (as int64_t) to an Input. |
true if the current character is '\0', false otherwise.
(input-at-end (input-new "" 0)) ; => true
input-current-char
(input-current-char [inp] :int)
return the character at the current position.
| inp | pointer (as int64_t) to an Input. |
The ASCII code of the current character as an int64_t (unsigned byte).
(input-current-char (input-new "abc" 0)) ; => 97 ; 'a'
input-advance
(input-advance [inp] :int)
return a new Input advanced by one character.
| inp | pointer (as int64_t) to the current Input. |
A new heap-allocated Input with pos incremented by 1.
(input-pos (input-advance (input-new "ab" 0))) ; => 1
input-pos
(input-pos [inp] :int)
return the current position index of an Input.
| inp | pointer (as int64_t) to an Input. |
The int64_t character offset into the source string.
(input-pos (input-new "abc" 2)) ; => 2
input-remaining
(input-remaining [inp] :int)
count bytes remaining in an Input.
| inp | pointer (as int64_t) to an Input. |
The number of bytes from the current position to the terminating '\0'.
(input-remaining (input-new "abc" 1)) ; => 2
input-rest
(input-rest [inp] :cstr)
the unread suffix of an Input, as a borrowed cstr.
| inp | pointer (as int64_t) to an Input. |
A pointer into the source string at the current position (not a copy).
(input-rest (input-new "abc" 1)) ; => "bc"
apply-fat
(apply-fat [f :int arg :int] :int)
invoke a fat closure with one argument.
| f | pointer (as int64_t) to a fat closure. | |
| arg | the single int64_t argument to pass. |
The int64_t return value of the closure.
(apply-fat my-fn 42) ; => result of calling my-fn with 42
apply-parser
(apply-parser [p :int inp :int] :int)
run a parser fat closure against an Input.
| p | pointer (as int64_t) to a parser fat closure. | |
| inp | pointer (as int64_t) to the Input to parse. |
A Cell list of Pair(value, remaining-Input) results.
(apply-parser (item-raw) (input-new "a" 0)) ; => Cell{Pair(97, Input@1)}
pfail-raw
(pfail-raw)
carrier worker behind pfail: a parser with no results.
pfail
(pfail [A])
a Parser that always fails, consuming no input.
A (Parser A) that yields no results for any input. This is the
Alternative/MonadPlus zero for parsers (see empty).
(run-parser-full (:: (pfail) (Parser Char)) "abc") ; => (none)
Since: stdlib-hkt-consolidation T2
pure-impl
(pure-impl [_v inp] :int)
internal implementation for pure.
| _v | the value to return. | |
| inp | the current Input (passed through unchanged). |
pure-parser
(pure-parser [v] :ptr<void>)
carrier worker behind Applicative [Parser]'s pure.
| v | the value to embed in the parse result. |
A parser that returns Pair(v, inp) without advancing the input.
(apply-parser (pure-parser 99) (input-new "" 0)) ; => Cell{Pair(99, Input@0)}
item-impl
(item-impl [inp] :int)
internal implementation for item.
| inp | the current Input. |
item-raw
(item-raw)
carrier worker behind item: yields the next byte's code.
item
(item :(Parser Char))
a Parser that consumes exactly one character.
A (Parser Char) yielding the next character, or failing at the end of the input.
(parse-first (item) "A") ; => #\A
Since: Phase B1 (Char: parsec-guide-plan P3)
satisfy-impl
(satisfy-impl [pred :(fn [Char] bool) inp] :int)
internal implementation for satisfy.
| pred | the character predicate. | |
| inp | the current Input. |
satisfy
(satisfy [pred :(fn [Char] bool)] :(Parser Char))
a Parser for one character that passes a predicate.
The general single-character parser: item, pchar and every character class are satisfy with a particular predicate. stdlib/char.tur's digit?, alpha?, alnum?, space?, upper?, lower? and punct? drop straight in.
| pred | (fn [Char] bool), true for the characters to accept |
A (Parser Char) that consumes the next character when (pred c) holds, and fails (consuming nothing) otherwise or at the end of the input.
(parse-first (satisfy digit?) "7") ; => #\7 (run-parser-full (satisfy digit?) "x") ; => (none)
Since: parsec-guide-plan P3
pchar-impl
(pchar-impl [_c inp] :int)
internal implementation for pchar.
| _c | the expected character code. | |
| inp | the current Input. |
pchar-raw
(pchar-raw [c :int] :ptr<void>)
carrier worker behind pchar / pchar-int: match one code.
pchar
(pchar [c :Char] :(Parser Char))
a Parser that matches one specific character.
| c | the character to match, e.g. #\A |
A (Parser Char) that succeeds with c when the next character is c, and fails otherwise.
(parse-first (pchar #\A) "A") ; => #\A
Since: Phase B1 (Char: parsec-guide-plan P3)
pchar-int
(pchar-int [c :int] :(Parser int))
DEPRECATED: the old integer-code form of pchar.
Kept for one release so code written against (pchar 65) keeps building; write (pchar #\A) instead. Its results are character codes, not Chars.
| c | the character code to match |
A (Parser int) yielding c when the next character has that code.
(parse-first (pchar-int 65) "A") ; => 65
Since: parsec-guide-plan P3 (deprecated on arrival)
pstring-c-impl
(pstring-c-impl [s_raw inp] :int)
internal C implementation for pstring.
| s_raw | the pattern string as a raw int64_t pointer. | |
| inp | the current Input. |
cstr->int
(cstr->int [s :cstr] :int)
reinterpret a :cstr pointer as an int64_t without copying.
| s | the C string to reinterpret. |
The raw pointer value of s as an int64_t.
pstring
(pstring [s :cstr] :(Parser String))
a Parser that matches a literal string.
| s | the text to match, e.g. "true" (borrowed; it must outlive the parser) |
A (Parser String) that consumes s when the input continues with it, producing a fresh owned String holding s; fails otherwise.
(string/to-cstr (parse-first (pstring "hi") "hi")) ; => "hi"
Since: Phase B1 (String: parsec-guide-plan P6)
or-parser-impl
(or-parser-impl [lp lq inp] :int)
internal implementation for or-parser.
| lp | the first parser (int64_t fat-closure pointer). | |
| lq | the second parser (int64_t fat-closure pointer). | |
| inp | the current Input. |
or-parser-raw
(or-parser-raw [p q] :ptr<void>)
int-carrier worker behind or-parser / Alternative alt-or.
or-parser
(or-parser [A])
try two parsers and return all successes from either.
This is the typed (Parser A) worker behind the Alternative [Parser] alt-or method; write alt-or.
| p | the first parser to try. | |
| q | the second parser to try. |
A parser that returns the concatenation of results from p and q applied to the same input (full backtracking).
(parse-first (or-parser (pchar #\A) (pchar #\B)) "B") ; => #\B
Since: Phase B1
or-else-raw
(or-else-raw [p q] :ptr<void>)
carrier worker: p's results, or q's when p has none.
The biased choice behind sep-by: q runs only if p fails outright.
bind-parser-inner
(bind-parser-inner [f :fn pair] :int)
apply continuation f to a single parse Pair.
| lf | the continuation fat closure (value -> Parser). | |
| pair | a Pair(value, remaining-Input) from the first parser. |
bind-parser-impl
(bind-parser-impl [lp f :fn inp] :int)
internal implementation for bind-parser.
| lp | the first parser. | |
| lf | the continuation fat closure. | |
| inp | the current Input. |
bind-parser
(bind-parser [p f :fn] :ptr<void>)
carrier worker behind Monad [Parser]'s bind / do-m.
| p | the first parser. | |
| f | a :fn continuation of type value -> Parser; receives the parsed | |
value and returns the next parser to run. A (fn ...) literal | ||
| coerces into this slot. |
A parser that runs p, then for each result calls (f value) and runs the resulting parser on the remaining input.
(bind-parser (item-raw) (fn [c] (pure-parser c))) ; identity parser
then-parser-impl
(then-parser-impl [lp lq inp] :int)
internal implementation for then-parser.
| lp | the first parser (result discarded). | |
| lq | the second parser (result kept). | |
| inp | the current Input. |
then-parser-raw
(then-parser-raw [p q] :ptr<void>)
int-carrier worker behind then-parser.
then-parser
(then-parser [A B])
sequence two parsers, keeping only the second's result.
Equivalent to (do-m _ p v q (pure v)).
| p | parser whose result is discarded. | |
| q | parser whose result is kept. |
A parser that runs p, then runs q on the remaining input, returning only q's results.
(parse-first (then-parser (pchar #\() (item)) "(x") ; => #\x
Since: Phase B1
then-left-impl
(then-left-impl [lp lq inp] :int)
internal implementation for then-left-raw.
then-left-raw
(then-left-raw [p q] :ptr<void>)
carrier worker: run p then q, keeping p's result.
many-c-impl
(many-c-impl [p_raw inp] :int)
internal C implementation of greedy zero-or-more repetition.
| p_raw | parser fat closure as int64_t. | |
| inp | the current Input. |
many-raw
(many-raw [_p] :ptr<void>)
carrier worker behind many.
many
(many [A])
greedily match a parser zero or more times.
| p | the parser to repeat. |
A (Parser (List A)) that always succeeds: the values of every match, in order, and the empty list when p does not match at all. Greedy -- it takes as many matches as it can and does not offer shorter ones.
(list-count (parse-first (many (satisfy digit?)) "123")) ; => 3 (list-empty? (parse-first (many (satisfy digit?)) "")) ; => true
Since: Phase B1 (List: parsec-guide-plan P5)
many1-impl
(many1-impl [_p inp] :int)
internal implementation for many1.
| _p | the parser to repeat. | |
| inp | the current Input. |
many1-raw
(many1-raw [_p] :ptr<void>)
carrier worker behind many1.
many1
(many1 [A])
greedily match a parser one or more times.
| p | the parser to repeat. |
A (Parser (List A)) like many, except that it fails unless p matches
at least once.
(list-count (parse-first (many1 (satisfy digit?)) "42")) ; => 2 (run-parser-full (many1 (satisfy digit?)) "") ; => (none)
Since: Phase B1 (List: parsec-guide-plan P5)
optional-c-impl
(optional-c-impl [p_raw inp] :int)
internal C implementation for optional.
| p_raw | parser fat closure as int64_t. | |
| inp | the current Input. |
optional-raw
(optional-raw [_p] :ptr<void>)
carrier worker behind optional.
optional
(optional [A])
match a parser zero or one times.
| p | the parser to attempt. |
A (Parser (Option A)) that always succeeds: (some v) when p matched
(consuming what p consumed), (none) when it did not (consuming
nothing). Test the result with some? / none?, read it with unwrap
or unwrap-or -- never compare it with 0.
(some? (parse-first (optional (pchar #\-)) "-")) ; => true (some? (parse-first (optional (pchar #\-)) "")) ; => false
Since: Phase B1 (Option: parsec-guide-plan P4)
spaces
(spaces :(Parser (List Char)))
skip zero or more whitespace characters.
A (Parser (List Char)) that always succeeds, consuming any run of
space, tab, newline or carriage return (see space?).
(list-count (parse-first (spaces) " \t")) ; => 3
Since: parsec-guide-plan
token
(token [A])
run p, then skip any whitespace after it.
Lexing with token keeps whitespace handling out of the grammar: each token eats the spaces that follow it.
| p | the parser for the token itself |
A (Parser A) producing p's value.
(parse-first (token (pchar #\x)) "x ") ; => #\x
Since: parsec-guide-plan
between
(between [A L R])
run left, p, right, keeping only p's value.
| left | the opening parser, e.g. (pchar #\() | |
| right | the closing parser, e.g. (pchar #\)) | |
| p | the parser for what sits between them |
A (Parser A) producing p's value.
(parse-first (between (pchar #\[) (pchar #\]) (item)) "[x]") ; => #\x
Since: parsec-guide-plan
sep-by1-impl
(sep-by1-impl [lp lsep inp] :int)
internal implementation for sep-by1.
| lp | the element parser. | |
| lsep | the separator parser. | |
| inp | the current Input. |
sep-by1-raw
(sep-by1-raw [lp lsep] :ptr<void>)
carrier worker behind sep-by1.
sep-by1
(sep-by1 [A S])
one or more p, separated by sep.
| p | the element parser | |
| sep | the separator parser (its values are discarded) |
A (Parser (List A)) of the elements, in order; fails unless at least one element matches.
(list-count (parse-first (sep-by1 (satisfy digit?) (pchar #\,)) "1,2,3")) ; => 3
Since: parsec-guide-plan
sep-by
(sep-by [A S])
zero or more p, separated by sep.
| p | the element parser | |
| sep | the separator parser (its values are discarded) |
A (Parser (List A)) of the elements, in order -- the empty list when not even one element matches.
(list-count (parse-first (sep-by (satisfy digit?) (pchar #\,)) "1,2")) ; => 2 (list-empty? (parse-first (sep-by (satisfy digit?) (pchar #\,)) "")) ; => true
Since: parsec-guide-plan
ParseResult
(defopaque ParseResult [A] :int)
one (possibly partial) parse: the value and where it stopped.
An element of what run-parser returns. Read it with parse-result-value and parse-result-rest.
Since: parsec-guide-plan P7
parse-result-value
(parse-result-value [A])
the value a parse produced.
| r | one element of a run-parser result |
The parsed value.
(parse-result-value (list-first (run-parser (item) "ab"))) ; => #\a
Since: parsec-guide-plan P7
parse-result-rest
(parse-result-rest [A])
the input a parse left unread.
| r | one element of a run-parser result |
A fresh owned String holding the unconsumed suffix ("" for a full parse).
(string/to-cstr (parse-result-rest (list-first (run-parser (item) "ab")))) ; => "b"
Since: parsec-guide-plan P7
run-parser-raw
(run-parser-raw [A])
carrier worker: the raw result Cell list for p on s.
run-parser
(run-parser [A])
every parse of s, complete or partial.
The debugging runner: it shows each way p can read a prefix of s, in the order the backtracking produced them.
| p | the parser to run | |
| s | the input text |
A (List (ParseResult A)) -- empty when p cannot read any prefix of s.
(list-count (run-parser (alt-or (pchar #\a) (item)) "ab")) ; => 2
Since: Phase B1 (typed: parsec-guide-plan P7)
run-parser-full-raw
(run-parser-full-raw [results] :int)
internal: the first result Cell that consumed all of its input, or 0.
run-parser-full
(run-parser-full [A])
the first parse that consumes all of s.
| p | the parser to run | |
| s | the input text |
(some v) for the first parse (in backtracking order) that read all of
s, (none) when every parse left input over or none succeeded.
(some? (run-parser-full (pchar #\A) "A")) ; => true (some? (run-parser-full (pchar #\A) "AB")) ; => false (leftover "B")
Since: Phase B1 (typed: parsec-guide-plan P7)
parse-failure-message
(parse-failure-message [results s :cstr] :cstr)
internal: "parse failed at: ..." for parse-first.
Names where the longest partial parse stopped (the whole input when nothing parsed), so a failing test says where to look.
parse-fail__
(parse-fail__ [results s :cstr] :int)
internal: panic with parse-failure-message.
parse-first
(parse-first [A])
the value of the first full parse, or a panic.
A convenience for main and tests, where input that does not parse is a programming error. Anywhere a bad input is expected, use run-parser-full and handle (none).
| p | the parser to run | |
| s | the input text |
The value run-parser-full would wrap in some. When there is none
it panics with parse failed at: "<unread input>".
(parse-first (pchar #\A) "A") ; => #\A (parse-first (pchar #\A) "B") ; panics: parse failed at: "B"
Since: parsec-guide-plan P7
fmap-parser-raw
(fmap-parser-raw [p f :fn] :ptr<void>)
worker: map a :fn callback over the value arm of a parser.
ap-parser-raw
(ap-parser-raw [pf pa] :ptr<void>)
int worker: sequential application of a parser of functions.
Functor[Parser]
(definstance Functor [Parser])
map a function over each parsed value.
(fmap (satisfy digit?) char->digit) ; a (Parser int): the digit's value
Since: stdlib-hkt-consolidation T2
Applicative[Parser]
(definstance Applicative [Parser])
pure injects a value without consuming input; ap runs a parser of functions then a parser of arguments, applying one to the other.
(:: (pure 42) (Parser int)) ; succeeds with 42, consumes nothing
Since: stdlib-hkt-consolidation T2
Monad[Parser]
(definstance Monad [Parser])
bind sequences parsers, threading each parsed value into the continuation. This is what do-m / for lower onto.
(do-m a (item) b (item) (pure (char=? a b))) ; two equal characters?
Since: stdlib-hkt-consolidation T2
Alternative[Parser]
(definstance Alternative [Parser])
empty is the always-failing parser; alt-or runs both parsers and unions their results (full backtracking choice).
(alt-or (pchar #\Y) (pchar #\N)) ; match 'Y' or 'N'
Since: stdlib-hkt-consolidation T2