Chido Parse🔗ℹ

William Hatch <william@hatch.uno>

1 Guide🔗ℹ

NOTE - chido-parse is NOT YET STABLE, and APIs may change.

Chido Parse is an expressive, extensible, composable parsing system. It allows users to build and compose parsers using any mix of ad-hoc procedural parsing, parser combinators, and other parsing abstractions and interfaces, such as readtables and BNF. It allows ambiguous grammars, but provides tools to filter ambiguity, including declarative operator associativity and precidence rules in readtables and BNF rules. Chido Parse supports context-sensitive grammars, including data-dependent grammars, in addition to supporting the entire class of context-free grammars.

Chido Parse is also... slow. So until and unless it can be optimized about 1 order of magnitude faster, I don’t expect people to really use it except for quick prototyping. If it gets 1 order of magnitude faster it will still be slow, but probably faster than macro expansion (at least for s-expression based languages), which will make it viable for projects where extensible and composable concrete syntax extension is as important as macro-based extension. But if you want fast compilation... look elsewhere.

You can use Chido Parse by constructing parser objects and then using whole-parse to parse your input. The simplest kind of parser to use is a literal string, and you can easily use combinators like sequence.

(define abc-d (whole-parse "abc" (sequence "a" "b" "c")))

The above code will return a derivation object. We can get a semantic result out with parse-derivation-result:

(parse-derivation-result abc-d)

Which will return '("a" "b" "c").

One of the key features of Chido Parse is its support for procedural parsers. Parsing procedures take a port and return either a derivation or a parse failure. To use them as parsers, you need to wrap them with the proc-parser struct. We can easily re-use existing parsers this way.

(proc-parser (λ (port) (make-parse-derivation (read-syntax (object-name port) port))))

Actually, procedural parsers can return a stream tree of parse derivations and failures. This allows them to support ambiguous grammars. However, result streams for Chido Parse should be constructed with stream-cons or for/parse, unless you know what you’re doing.

Procedural parsers can recur back into the parsing system by using parse*. parse* is like whole-parse, except that it doesn’t have to consume the whole input and it returns a stream of derivations. Note that whole-parse actually returns a parse failure if there is more than one derivation. If you want multiple results from a top-level parse, you can use whole-parse*. While parsers can return a tree of streams, they are flattened and parse* and whole-parse* return a stream whose members are all parse-derivation? objects.

For example:

(define plus

(proc-parser

(λ (port)

(for/parse ([l (parse* port expression)])

(for/parse ([op (parse* port "+" #:start l)])

(for/parse ([r (parse* port expression #:start op)])

(make-parse-derivation

`(+ ,(parse-derivation-result l)

,(parse-derivation-result r))

#:derivations (list l op r))))))))

Note that parse* does not actually consume input from the port, so successive parses need the #:start keyword. But there’s an easier way. Instead of parse*, you can use parse*-direct, which uses delimited continuation magic to loop over a stream while looking like straight-line code:

(define plus

(proc-parser

(λ (port)

(define l (parse*-direct port expression))

(define op (parse*-direct port "+"))

(define r (parse*-direct port expression))

(make-parse-derivation

`(+ ,(parse-derivation-result l)

,(parse-derivation-result r))

#:derivations (list l op r)))))

Note that if we define the expression parser like so:

(define expression

(alt-parser plus number))

(define number

(kleene-plus (char-range-parser "09")

#:result/bare (λ (ds) (string->number (apply string ds)))))

It turns out that our procedural plus parser is left-recursive! Everybody knows that if you make a left-recursive procedural parser you get infinite recursion! But not in Chido Parse. Chido Parse dynamically detects left-recursive dependency cycles and resolves them by capturing and descheduling first-class delimited continuations. When a cycle occurs, Chido Parse saves the continuation, finds other work, and then applies the continuation to a result when one is available from a different alternate. If there is no alternate that can make progress, Chido Parse breaks the cycle by returning a failure result to the left-recursive parser. Failing cycles this way is mostly so the parser can compute a good failure message, but conceivably you could implement a biased alternate this way. However, at present Chido Parse doesn’t guarantee any order to cycle breaking, so don’t.

Chido Parse also has BNF forms, of course:

(define-bnf dumb-statement-parser

[statement ["pass"]

["for" id "in" expression "do" statement]

["{" [: #:repeat-min 0 #:splice 1 statement] "}" #:name "block"]

[expression]]

[expression [number-parser]

[id]

[expression "+" expression #:associativity 'left]

[expression "*" expression

#:associativity 'right

#:precedence-greater-than '("+")]]

; Obviously this is a bad identifier parser, but I'm making dumb examples in a hurry.

[id [[: #:repeat-min 1 (char-range "az")]]])

The define-bnf form has a bunch of optional arguments for specifying automatic layout insertion (IE allowing whitespace between things). Note that these things are all just parsers. You can use a procedural parser anywhere in your BNF definition, you can stick a BNF parser in a combinator, etc.

Of course, the real reason I started Chido Parse was because I wanted better readtables. So Chido Parse has a readtable-style abstraction for making and extending fancy s-expression parsers.

(define cool-s-exp

(chido-readtable-add-list-parser "$(" ")" basic-chido-readtable

#:wrap '#%dollar-paren))

Now cool-s-exp can parse

as '(foo bar (#%dollar-paren quux flub) zonkers)

Chido readtables support infix/prefix/postfix operators as well as the kinds of extensions that Racket’s normal readtables support. Chido readtables support arbitrary-length prefixes unlike Racket readtables with their single character prefix..

Chido readtables and BNF parsers can be extended, eg. with extend-chido-readtable and extend-bnf. BNF parsers are actually made out of readtables, and you can do extend-readtable-as-bnf.

Parsers can be extended, modified, or loaded dynamically. Eg. you can use extend-readtable during parsing, and you can create parsers like Racket’s built-in #reader form. All these fancy parsing abstractions are built out of procedural parsers. If there is another parsing abstraction you know of and like, you can build that abstraction too!

This is clearly a bad guide, but I wanted to write at least something real quick.

TODO - write a better guide.

2 Reference🔗ℹ

NOTE - chido-parse is NOT YET STABLE, and APIs may change.

2.1 Gotchas🔗ℹ

Don’t use parameter?s, use chido-parse-parameter?s. Don’t use stream-cons or other stream constructors, use parse-stream-cons and its derivatives provided by Chido Parse.

2.2 Core API🔗ℹ

2.2.1 Parsing Functions🔗ℹ

If this is the first call into the parsing system, the input port is actually replaced for inner parses with a wrapper that can be rewound for multiple ambiguous parses. In any event, parse* does NOT change the current position of the port. If you do a series of parses with parse*, you should pass the previous derivation as the start position to the next call of parse*. Realistically, within a parser parse* should only be used in tail position or in combination with for/parse. For a more convenient function for use within parsers, see parse*-direct.

This is technically the core parsing function, but you probably want to use whole-parse or whole-parse* for the initial parse, and parse*-direct inside parsers.

However, if you are doing some OTHER delimited continuation stuff or creating a stream of results using something other than parse-stream-cons (or for/parse), you may need to take care to use delimit-parse*-direct so the overall parse result is correct.

But really just don’t use something other than parse-stream-cons (and its derivatives) to construct result streams!

2.2.2 Parse Derivations🔗ℹ

Result can be anything, but if it is a procedure it is assumed to be a delayed result. The procedure should be of the form:

(λ (src line col pos span derivations) (datum->syntax #f 'my-result (list src line col pos span)))

2.2.3 Parse Failures🔗ℹ

Note that parse failures implement the gen:stream interface as empty streams.

2.2.4 Chido Parse Parameters🔗ℹ

Don’t use parameter?s inside parsing procedures. Use chido-parse-parameters instead.

They behave similarly, but chido-parse-parameters are a key to the parsing cache (so you don’t accidentally pull out a cached result that was constructed by referring to a different parameter value, such as a different value for current-chido-readtable) and are preserved by parse-stream-cons, whereas regular parameters are NOT preserved by stream-cons and friends.

2.2.5 Stream construction🔗ℹ

2.2.6 Parsers and core parser constructors🔗ℹ

BUT - here I’ll at least document what this is meant to check, and what you can expect from functions that return parser?s.

Parsers are either proc-parsers, alt-parsers, string?s, structs that implement prop:custom-parser, non-cached-parser-thunk, or a thunk that returns one of those.

Thunks are allowed because parsers often need to recursively refer to each other. If parsers are mutually recursive, you have an ordering issue where neither can be constructed without the other. To break the cycle, put one in a thunk! Thunks that contain parsers are only forced once and cached, so you can rely on the results of the thunk being eq? (eg.for filtering purposes). Because sometimes you really do want the thunk to be re-evaluated, thunks wrapped with the non-cached-parser-thunk struct are NOT cached. Additionally, chido-parse-parameter?s used as parser thunks are not cached, because their whole point is to be this dynamically extensible thing to allow you to implement parsers independently then have them dynamically reference the right parser when recurring.

If you use a procedure as a parser that is NOT a thunk that returns (perhaps eventually through multiple layers of thunks) a primitive parser, you will get an exception when the scheduler actually tries to force it and use it as a parser.

If prefix is given, it is a literal prefix to match before the procedure is called. Unless preserve-prefix? is true, the port is set to just after the prefix, so your parsing function can focus on the interesting part of the parse. preserve-prefix? is mostly there as a convenience for wrapping existing parsing procedures.

The prefix may be queried and used in a semantically meaningful way, as by chido-readtable?s.

TODO - I should document this. But really it should probably be gen:custom-parser and support multiple methods, eg. for name, prefix, etc.

IE this is not stable.

At any rate, while this is undocumented you can also just use a function that takes your struct and returns a parser, though that’s less satisfying.

Note that this has to force thunks.

Note that this has to force thunks.

2.3 Literal Parsers🔗ℹ

You can use string?s as literal parsers. You can always create proc-parsers that parse literals. The other literal parsers here are just proc-parsers that are convenient enough to be in the standard parser library.

2.4 Combinators🔗ℹ

The alternation combinator alt-parser is documented in another section.

The derive, result/bare, and result/stx arguments are for building the result derivation, and only one may be given (a non-#f value). They are all procedures that must accept one value for each of parser, but not the before, between, or after parsers.

derive should be a function that accepts one derivation for each parser, and should return a parse-derivation?.

result/bare should be a function that accepts the result values (IE using parse-derivation-result) from each parser and should return a value to be used as the result field of make-parse-derivation. You can also provide #t instead of a procedure to just get the results in a list.

result/stx is like result/bare, but it wraps the result you return as a syntax object with appropriate source location info. You can also provide #t instead of a procedure to just get the results in a syntax list.

If none of the result options are given, the default is as if result/stx is #t.

TODO - example usage.

The optional argument API is like sequence. between is used between iterations of parser, before and after are parsed before/after the first/last repetition of parser.

derive, result/bare, and result/stx act like sequence but should accept a single argument which will be a list of derivations returned by parser (in order). Again, result/bare and result/stx may be #t instead of a procedure, in which case the results will be put in a list or syntax list. If none of the options are non-false, result/stx is treated as #t.

You can specify the minimum and maximum number of acceptible repetitions with min and max. If greedy? is non-false, derivations will only be returned if they parsed the max number of repetitions or no more repetitions can be parsed after the last one. Note that the result may still be ambiguous depending on whether parser or before/between/after are ambiguous. If greedy? is false, all derivations with a number of repetitions between min and max, inclusive, are returned. Frankly, for any realistic use, you want greedy? to be true, because the extra ambiguity of non-greedy makes a lot of work for the system, even though most of it is immediately thrown away.

TODO - usage example.

UNSTABLE - I might change the default option for greedy?. On the one hand, false gives the more general parser and what most people would probably expect at first. But non-greedy repetition is just so much slower that any practical use really needs to reach for greedy.

UNSTABLE - I might change the default option for greedy?.

You can supply result as the result field for make-parse-derivation.

You could use this with eg. parse*-direct to peek ahead without actually effecting the input port.

To bind the derivation as a result, use the #:bind keyword to bind the derivation to name. Then just refer to name later!

Global options affect the entire sequence. between-parser is inserted between each element in the sequence. If between-parser is not specified but inherit-between is truthy, then the sequence inherits the between-parser from any binding-sequence that surrounds this one. If splice-global is a number greater than 0, the resulting list is spliced that many times (which is only useful if your sequence only has a single non-ignored element). The derive, result/bare, and result/stx arguments are similar to the similar arguments in sequence, though note that splices and ignores affect the list of arguments that will be passed to them. The default derivation result will be a syntax list of the results of the elements (taking into account splices and ignores).

Each element in the sequence may have extra options about binding, splicing, or repetition. The binding-name argument is bound to the derivation of that element for future elements in the sequence. The splice-number argument should be a positive integer, and the result list of that parser will be spliced that number of times into the outer result list. If the ignore argument is true, that element is not included in the result list. The repetition arguments act as in repetition, though the between-parser is inserted between repetitions.

2.4.1 Filters🔗ℹ

The filter-func receieves the input port at the position after the parser’s derivation, as well as the derivation itself. If the filter-func returns false, that derivation is removed from the result stream of the filtered parser. If replace-derivation? is true, the filter-func’s non-false results must be new parse derivations, which replace the original derivations in the parse stream. Otherwise the original parse derivations are used even if the truthy value returned by filter-func is itself a parse derivation.

If include-failures? is true, each filtered derivation will be replaced in the stream by a parse-failure? with a message about the filtered derivation. It’s really only useful if you want to track all failures with chido-parse-keep-multiple-failures?.

Eg. (must-follow-filter "abc" "d") parses the first three characters of the string "abcd", but does not parse the strings "abc" or "abce".

2.5 Chido-Readtable Parsers🔗ℹ

Chido-readtables have an interface similar to Rackets readtables (see Readtables in the Racket Guide)

Chido-readtables are a fancy kind of alternative parser. Among their alternatives, chido-readtables have a built-in symbol parser whose behavior is modified by the other parsers. Chido-readtables are extended with parsers and a symbol denoting an effect on the built-in symbol parser, such as 'terminating or 'nonterminating-layout.

When the built-in symbol parser is used by a chido-readtable, the symbol continues until reaching the prefix of a 'terminating or 'terminating-layout parser or a successful parse from a 'soft-terminating or 'soft-terminating-layout parser.

Layout parsers are whitespace or comment parsers that delimit symbols and are generally allowed between other parsers inside lists. Results from layout parsers are ignored when creating parse results from readtable parsers, only the fact that they succeed at parsing is relevant. They come in 'terminating-layout, 'soft-terminating-layout, and 'nonterminating-layout varieties, which match the symbol effects of 'terminating, 'soft-terminating, and 'nonterminating parsers, respectively.

Terminating parsers are parsing alternatives that also delimit symbols (IE they terminate the built-in symbol parsing). In other words no space is necessary between a symbol and a following terminating parser. 'soft-terminating parsers terminate a symbol only of they parse successfully. Hard terminating ('terminating) parsers terminate a symbol when their prefix matches, whether or not they parse successfully. Therefore the prefixes of hard terminating parsers are disallowed anywhere within symbols.

Nonterminating parsers are alternatives that do not delimit a symbol. Layout (whitespace) is required between a symbol and a following nonterminating parser.

Terminating and nonterminating parsers can follow each other with no layout in between, though layout is allowed between them, and usually good style to have.

Note that when using a chido-readtable as a parser directly, it parses only ONE form, equivalent to using chido-readtable->read1. When you want to parse a sequence using chido-readtables, instead of using a kleene star combinator, you should use chido-readtable->read*.

Ambiguous results are possible from parsing with a chido-readtable when terminating/nonterminating parsers themselves return ambiguous results or when multiple terminating/nonterminating parsers are successful at a given position. If another parser is successful, the symbol parser is not tried. The symbol parser never returns an ambiguous result.

One final parser flag is 'left-recursive-nonterminating. Parsers with the 'left-recursive-nonterminating flag are run after the symbol parser and do not effect symbol parsing. While chido-parse doesn’t normally need a flag to handle left-recursive parsers, because most readtable parsers are run before the symbol parser and used to effect the symbol parser, left-recursive parsers need a special flag in the readtable parser.

2.5.1 chido-readtable objects🔗ℹ

TODO - list the flags that the table starts with, eg. chido-readtable-symbol-support?.

2.5.2 Variations on chido-readtable parsers🔗ℹ

UNSTABLE - chido readtables don’t yet support symbols with escapes (IE with backslash) or as literals with pipes around them as Racket’s built-in readtable does. At some point there will be options to set on the readtable itself to toggle options about those.

2.5.3 Extending and modifying chido-readtables🔗ℹ

All readtable “modifiers” are functional. They do not actually mutate a readtable, they merely return a new modified readtable.