Extend a data format: jsonic

The parser

As we did in bf, we’ll use #lang brag to generate a parser for jsonic based on a grammar that describes the struc­ture of jsonic programs. The parser will take the tokens gener­ated by the tokenizer and orga­nize them into a parse tree. (Later, this parse tree will be passed to the expander for further processing.)

Let’s start a new file called "parser.rkt". From there, we’ll build the grammar piece by piece:

The first line repre­sents the starting produc­tion rule, which will become the top node of the parse tree. We name this rule jsonic-program:

What’s in a jsonic-program? Let’s be careful: though our source code combines syntax from JSON and S-expres­sions, our grammar doesn’t have to actu­ally handle the details of parsing JSON and S-expres­sions. It just needs to be able to distin­guish one from the other. After that, the S-expres­sions can be eval­u­ated as usual; every­thing else is JSON, and can be passed through as is.

So we describe a jsonic-program as a sequence of two possible elements: a jsonic-char or a jsonic-sexp. We use | in the grammar to indi­cate a choice between elements, and * to indi­cate zero or more occur­rences of the element:

Now we need to add produc­tion rules for our two new elements, jsonic-char and jsonic-sexp:

A jsonic-sexp is any sequence of char­ac­ters between our open and closing delim­iters. But in our tokenizer, we pack­aged our S-expres­sions into a named token called SEXP-TOK, and other char­ac­ters into a named token called CHAR-TOK. Now, we use these named tokens directly in our grammar:

By the way, when the parser matches a named token, it pulls the matched string out of the token and puts it in the parse tree. Thus, the finished parse tree will contain no refer­ences to SEXP-TOK or CHAR-TOK. It will contain the strings that were inside those tokens.

And that’s all we need.

Testing the parser

As we did with the tokenizer, let’s do some quick tests to make sure our grammar gener­ates sensible parse trees. Again, this isn’t a substi­tute for thor­ough unit tests. But it provides a basic sanity check before we move on. Also, as we’re building a DSL, it’s good to know how we can watch the pieces work together provi­sion­ally before we get all the way to testing source files.

Let’s start a new source file in DrRacket. We’ll require our new tokenizer and parser from jsonic/tokenizer and jsonic/parser, respec­tively. We’ll also require brag/support so we can use apply-tokenizer-maker again.

We can now tokenize & parse toy programs, either within the defi­n­i­tions window, or at the REPL prompt. For instance, a jsonic program consisting only of a comment should be parsed into a tree with a top jsonic-program node, and nothing else:

A program with a single S-expres­sion between delim­iters:

A program without nested delim­iters:

A three-line program that contains all three items:

Exactly right.

Here strings

This is an apt moment to learn an easier way to write multi­line input for any Racket func­tion: a here string. A here string is intro­duced with #<<LABEL, where LABEL is an arbi­trary name that will termi­nate the here string. The here string starts on the next line, and ends when LABEL appears on a line of its own. Below, we’ll use DEREK as a termi­nator, and include unescaped quotes around hi:

This time, the quotes around "hi" are treated as part of the source string, and thus appear in the parse tree.

As we look over these results, we should recall that in every parse tree, all the char­ac­ters in our source code will appear in a node of the parse tree (except those that are delib­er­ately removed, like comments). Further­more, the nodes of the parse tree cor­re­spond to the names and pat­terns of the pro­duc­tion rules in the grammar. This struc­ture, in turn, will guide the struc­ture of our expander. We’ll add that next.

Reader recap

Before we move on, let’s make sure our reader source files are correct: