Follow the grammar: bf

Intro­ducing the tokenizer

Though it’s essen­tially true that the parser takes a string of source code as input, we glossed over a detail. It’s more precise to say that the parser takes as input a sequence of tokens. A token is the smallest mean­ingful chunk of a string of source code. A source string is converted to tokens with a func­tion called a tokenizer that sits between the source string and the parser.

Strictly speaking, a tokenizer is optional. If we don’t use a tokenizer, then every char­acter that appears in our source code counts as a token, and thus also has to appear in our grammar.

For that reason, a tokenizer is often conve­nient, because it reduces the number of distinct tokens we have to handle in our grammar. Because of this, the tokenizer and parser aren’t fully inde­pen­dent. Rather, the tokenizer gives us options for allo­cating the labor.

For instance, some tasks are more easily handled with a tokenizer:

Recall our zip-code grammar:

The tokenizer gets a string as input (or a port pointing at a string), so any func­tion that we can use with a string can be used in the tokenizer. Here, we could use a regular expres­sion to match the strings "0" through "9" and convert each of these to the token type DIGIT-TOKEN. We could then rewrite our grammar like this:

The parse tree for a zip code like 01234 will look the same:

In that way, the tokenizer can hide details about the source string that the grammar doesn’t need to care about.

What’s the down­side of a tokenizer?

All that said, the divi­sion of labor between parser and tokenizer is more art than science. We can use the tokenizer in what­ever way makes the most sense for a given language.

Designing the BF tokenizer

Let’s recall our bf grammar:

This captures the struc­ture of any bf program. But it omits one detail about bf source files: any char­ac­ters aside from the eight used in the grammar, including white­space, should be ignored.

So our tokenizer for bf will be simple: we’ll pass through the eight mean­ingful char­ac­ters intact, and toss out every­thing else.

Writing a reader with a tokenizer

We can start assem­bling the reader for bf. Let’s create a file called "reader.rkt" in the same folder as the existing "parser.rkt". We need to require our "parser.rkt" module (to get access to parse) and add a read-syntax func­tion:

Here’s the plan:

In stacker, we put the reader and expander in the same source file. This time we’re putting our expander in its own file. Within our module datum, we desig­nate "expander.rkt" as the path to our expander (though we still need to create that file).

Next, we add our new make-tokenizer func­tion. We’re passing the input port—which points at the source string—to make-tokenizer. Rather than return one big pile of tokens, make-tokenizer creates & returns a func­tion called next-token that the parser will call repeat­edly to retrieve new tokens:  + This “incre­mental tokenizing” approach is consis­tent with the idea of using a port to read from a source file incre­men­tally.

Finally, the tokenizing rules. This isn’t the moment for us to go deep on tokenizer-rule nota­tion—we’ll save that for a later tuto­rial. In short, the tokenizer relies on a helper func­tion called a lexer. Each branch of the lexer repre­sents a rule. On the left side of the branch is a pattern that works like a regular expres­sion. On the right side is a token-creating expres­sion. Each time next-token is called, bf-lexer will read as many char­ac­ters from the port as it can while still matching a rule pattern (aka “greedy” matching). The right side of the rule will convert the matched char­ac­ters into a token, and this token will be returned as the result.

We require brag/support so we can get lexer, which manages the pattern matching.

The first rule uses the lexer helper char-set to match one of our eight special bf char­ac­ters ><-.,+[]. We pass these through directly with the special lexer vari­able lexeme (= need­lessly obscure word for “that thing we just matched”).

The other rule uses the lexer helper any-char, which matches any other char­acter—we can think of it like an else branch. In bf, these char­ac­ters should all be ignored. We can accom­plish this by calling (next-token) again, which has the effect of skip­ping to the next avail­able token.

When a port reaches the end of a file, it emits the special eof signal. Thus, a lexer always needs to handle eof. We could write an explicit rule. But we can also just rely on the lexer’s default eof behavior: the lexer will emit an eof token, which in turn will stop the parser. For bf, that suffices.

That’s it. Our tokenizer is done. There­fore, so is our reader. We’ll keep in mind that if we ever want to extend our bf inter­preter—for instance, to support new char­ac­ters with other mean­ings—we’ll first have to adjust our make-tokenizer func­tion to let them through, and then update our grammar to handle them.

Testing the reader

We already did a quick test of our parser to make sure a snippet of bf source code could be converted into a parse tree. Now that our reader is assem­bled, let’s make sure we get the same result from a full source file.

We’ll take the code for our demo program and make it into a source file that relies on our new bf reader. As before, we’ll use the #lang reader path boot­strap­ping command. Save this file in the same direc­tory as "reader.rkt":

When we run this file, we’ll get an error like this:

That’s a good sign. It means we’re success­fully invoking "reader.rkt", which in turn is looking for "expander.rkt", but can’t find it. Because we haven’t made it.

So let’s stub it out. As usual, our expander needs to start with a macro called #%module-begin. As we did in stacker, we’ll avoid a conflict with the #%module-begin already defined by br/quicklang by calling our new macro bf-module-begin, and then using rename-out to change the exported name.

Look care­fully—the only work that bf-module-begin is doing is adding a ' prefix to the PARSE-TREE that’s arriving from the reader as our input. We did this in stacker too—it’s a quick way to print and debug the result we’re getting from the reader.

Now when we run "atsign.rkt", we’ll reveal the parse tree:

What are we seeing here? Two things:

While we’re here, let’s see what happens when we run a poorly formed bf program. We know that brackets have to come in pairs. So let’s delib­er­ately add an unmatched left bracket to the end of the program:

This time, when we run the program, we won’t see a parse tree—instead we’ll get an error like this:

This is the right result. Our parser can’t find a way to match this defec­tive code string to its grammar. Thus, when it reaches the unmatched bracket—"["—it gives up and raises an error.

Before we continue, let’s remove the spurious left bracket from the end of "atsign.rkt", and also the ' prefix from PARSE-TREE, so our files look like this:

Now we can finish the expander.