Extend a data format: jsonic

The tokenizer

Recall that a token is the small­est mean­ing­ful chunk of a string of source code. Within the reader, a source string is con­verted to tokens with a helper func­tion called a tok­enizer.

We won’t be able to totally reuse the bf tokenizer. But the jsonic tokenizer will follow a similar pattern. Let’s create a new "tokenizer.rkt" module with a shell for the tokenize func­tion, and we’ll step through the indi­vidual tokenizing rules:

As before, make-tokenizer takes a port as input and returns a func­tion, next-token, that the parser will call to retrieve tokens.

Within next-token, we use a helper func­tion called a lexer to break down the source code into tokens. We first used a lexer in bf. But let’s review how it works:

We import brag/support, which provides tools we need for the lexer: the basic lexer func­tion; from/to, which is a matching helper; trim-ends, another helper func­tion to process match results; and token, a data struc­ture that will coop­erate with the parser we’ll make later, using #lang brag.

We’ll need three rules in jsonic-lexer. Taking each in turn:

The first rule handles our line comments. Recall that any time we find the // char­acter combi­na­tion in the source, we want to ignore the rest of the line. So this rule matches every­thing from // to the next newline. We use the lexer rule from/to to make this pattern. Once we’ve gotten our match, we ignore it by calling (next-token) again, which has the effect of skip­ping to the next avail­able token.

Next, we match the embedded Racket expres­sions that will appear between the @$ and $@ delim­iters. This is an instance where it’s helpful to make a “big” token—ulti­mately, these Racket expres­sions will just pass through to the expander intact, so we don’t need to tokenize any of them into smaller pieces.

Again, we use a from/to rule to match every­thing between the @$ and $@ delim­iters (including the delim­iters them­selves). Once we’ve matched the embedded expres­sion—a value that will be held in the special lexer vari­able lexeme—we use trim-ends to remove the delim­iters.

Finally, we package this trimmed lexeme into a token struc­ture with the name SEXP-TOK. Named tokens can make a grammar simpler, because we can then refer to tokens within the grammar by name rather than by specific values. By conven­tion, named tokens use CAPS names to distin­guish them from names of produc­tion rules in the grammar. One nota­tional wrinkle: though we write 'SEXP-TOK here (the ' prefix makes it a symbol rather than a vari­able), in the grammar we’ll write this token’s name simply as SEXP-TOK.

For the last rule, we use an any-char rule to match every­thing else. In a lexer, this works like an else branch, handling all char­ac­ters not processed by earlier rules. We create another named token, this time called CHAR-TOK, and include lexeme as the token value.

When port reaches the end of the file, it emits the spe­cial eof sig­nal. By default, the lexer will auto­mat­i­cally handle eof by emit­ting an eof token, which in turn will stop the parser. If we like, we can write our own rule that matches eof, that performs other actions before returning the eof token. Usually this isn’t neces­sary, and we can just rely on the default behavior.  + For an example of an explicit eof rule, see the syntax-coloring tuto­rial.

Testing the tokenizer

It’s not a substi­tute for rigorous unit tests—we’ll get to those later—but let’s quickly check that our tokenizer gives us the results we expect.

We can use the REPL for "tokenizer.rkt" to test our tokenizer on sample strings. First, click Run to refresh make-tokenizer. Then we can enter some test expres­sions on the REPL using the helper func­tion apply-tokenizer-maker.

If we pass a comment to our tokenizer, it should result in no tokens:

A Racket expres­sion between delim­iters should result in a corre­sponding SEXP-TOK token:

And any other string should become a list of named CHAR-TOK tokens:

The trailing #f values are place­holders in the token data struc­ture for source loca­tion fields that we’re not collecting now. But we’ll start using those fields in the next tuto­rial.

Now that we have our make-tokenizer func­tion, we can make our parser. As we’ll find, the parser will be very simple thanks to the extra work we did here.

More broadly, when imple­menting a language, we’ll often have a choice about where to handle certain tasks: in the tokenizer, or in the parser, or in the expander. It’s more art than science. Though working with tokenizer rules is some­times a chore, they can substan­tially simplify the rest of imple­men­ta­tion.