Follow the grammar: bf

Writing a grammar for BF

Back to the task at hand—writing a grammar for bf so we can parse source code like this:

It turns out, however, that bf has a grammar even simpler than our ficti­tious M-expres­sions.

Let’s recall how bf works:

Let’s build up our grammar line by line. The first produc­tion rule repre­sents the top element, which we’ll call bf-program.

What’s the pattern for a bf-program? We know that bf is just a list of oper­a­tions and loops. Let’s call them bf-op and bf-loop respec­tively. Thus our pattern for bf-program is a list of any number of bf-ops or bf-loops:

To recap, (bf-op | bf-loop) means “either a bf-op or a bf-loop” and * means “zero or more of the preceding item”.

If we stopped here, our grammar wouldn’t work, because we’ve referred to bf-op and bf-loop without defining them. We’ll do that next:

So what’s a bf-op? As we noted, it’s one of the char­ac­ters > < + - . ,, which we notate like so:

Finally, what’s a bf-loop? It’s a pair of square brackets with another list of bf-ops or bf-loops inside:

That’s it—we have a complete grammar for bf. Meaning, bf may be a crazy language, but no matter how big or complex a bf program someone handed us, we could parse it using just these three rules.

Is this the only valid grammar for bf? No. We could recur­sively reuse our bf-program element like so:

We could also create a sepa­rate element, call it bf-exprs, to repre­sent a list of bf-ops and bf-loops:

A case could be made for either of these alter­na­tives. The tiebreaker is conve­nience. For reasons that will become clear when we write our expander, the easiest grammar to work with will be the first one, because bf-program only appears once, and it other­wise uses the fewest possible rules.

Converting a grammar to a parser

Our small invest­ment in making a grammar will pay an imme­diate divi­dend. Because now that we’ve made our bf grammar:

We need to convert it to an actual bf parser. How?

Consis­tent with the idea of using a domain-specific language to solve special­ized prob­lems, we’ll use a parser-gener­ating language called brag that takes a list of produc­tion rules as its source code, and turns those rules into a working parser.

Here’s how we use it. We make a new file called "parser.rkt" like so:

All we’ve done is take our grammar and add a #lang brag line to the top. When we import this module into our bf reader, we’ll get a func­tion called parse that imple­ments this grammar, and another called parse-to-datum that will let us check the gener­ated parse tree.

Let’s do that now, by making another file in the same direc­tory, and pasting in the source code from our demo program as the input to parse-to-datum:

When we run "parser-tester.rkt", we’ll get this:

Once again, all the char­ac­ters in our source code appear in a node of the parse tree, and these nodes corre­spond to the names and patterns of the produc­tion rules. (The curious can change the source string in "parser-tester.rkt" and see how the parse tree changes, though take care not to use any char­ac­ters other than the eight handled by our grammar.)

Not bad—with four lines of code, the heavy lifting for the parser is now done. To finish our parser, we need to build one helper func­tion that will take care of white­space and other char­ac­ters.