Follow the grammar: bf

Writing a grammar

Here’s a simple grammar that describes a five-digit zip code:

A grammar consists of a series of produc­tion rules, written one per line. On the left of each rule is the name of a struc­tural element of the language. The name is like a vari­able—it can be anything we want (though as usual, short & mean­ingful names are wise). A colon goes in the middle of the rule.  + This nota­tion style is known as Extended Backus–Naur form or EBNF, so this kind of grammar is also known as an EBNF grammar. Above, we have produc­tion rules for two elements: zip-code and digit.

On the right of each rule, we have a pattern for that element. This side of the rule is like a regular expres­sion: it can include literal strings (like "<" or "def"), classes of strings (like UPPERCASE), or names of other produc­tion rules (denoting an appear­ance of that element). If a pattern has multiple possi­bil­i­ties for a certain posi­tion, they’re sepa­rated by a vertical bar |.

The first rule in a grammar defines the top-level element—in this case, a zip-code. A zip code has five digits, described by the pattern digit digit digit digit digit. White­space in each produc­tion rule is ignored during the matching, so this rule denotes five adja­cent digits.

On the next line, we define a digit as any string from "0" to "9", using vertical bars to sepa­rate the choices. Again, because white­space within the pattern is ignored, we can break the rule onto two lines.

Applying a grammar

How does a grammar-based parser work? The parser takes a string of source code as input (or an input port pointing at the code). Starting with the first produc­tion rule in the grammar, the parser tries to match the source code to the pattern on the right. If that pattern contains names of other rules in the grammar, the parser recur­sively tries to match those rules, again using the patterns on the right.

This process continues until one of two things happen:

Suppose we tried to parse the string "123ABC" with the grammar above:

Or suppose we tried to parse "1234":

Now suppose we tried to parse "01234":

By the way, how does a parser avoid going down fruit­less paths? It doesn’t. On the contrary, a parser might explore many cul-de-sacs on its way to a finished parse tree (just as a regular expres­sion might end up trying lots of unsuc­cessful substring matches). It’s trial and error.

Alter­na­tive gram­mars

Gram­mars are not unique. We can always find another grammar to describe a language. For instance, our zip-code grammar could also be written like this:

It should be apparent that any string that matched (or did not match) the first zip-code grammar would also match (or not match) this one. For instance, our string 01234 would now be parsed like so:

It would be perverse to define a zip-code grammar this way. Never­the­less, we have lati­tude to do so. As usual, however, simpler tends to be better.

Ambiguous gram­mars

It’s also possible to write gram­mars that are ambiguous, in the sense that the rules are suffi­ciently lenient that a string can produce more than one valid parse tree.

For instance, in this zip-code grammar, the pattern for the zip-code rule has two equiv­a­lent options for getting to five digits:

With this grammar, our string 01234 could be parsed one of two ways:

A parser gener­ator is unlikely to complain about this grammar—as long as it can complete a parse tree, it’s happy. But ambi­gu­i­ties like these often indi­cate lurking illogic, and are best avoided.

Groups and multi­ples in patterns

The produc­tion rules in our zip-code grammar only relied on simple string matching, and a vertical bar | to denote alter­nate possi­bil­i­ties. Let’s look at some of the other special nota­tion we can use in our produc­tion-rule patterns.

Recall that stacker programs consisted of a list of instruc­tions sepa­rated by line breaks, where each instruc­tion was either an integer num or the func­tions + and *. A grammar for stacker might look like this:

Step­ping through each rule:

So if we start with our good old stacker test program:

Our parse tree will look like this:

We should note how the parse tree lines up with the grammar:

Recur­sive gram­mars

Of course, most program­ming languages are more struc­turally intri­cate than stacker or a zip code. Fortu­nately, because the rules in a grammar can refer to each other recur­sively, a lot of complexity can be expressed in a small set of rules.

For instance, let’s invent M-expres­sions, which we’ll define as the subset of S-expres­sions that only contain addi­tion and multi­pli­ca­tion of inte­gers. M-expres­sions can be nested to any depth. A short example:

The grammar for M-expres­sions might look like this:

As before, the top-level element of our parse tree, m-expr, is the name of the first produc­tion rule. We can recycle the integer, digit, and func rules from the stacker grammar above.

The new possi­bility is an m-list, which is a series of items between paren­theses, starting with a func, and followed by any number of m-exprs sepa­rated with word spaces. Notice that the pattern for an m-expr refers to an m-list, and vice versa. Mutu­ally recur­sive defi­n­i­tions like these are not only legit, they’re often neces­sary to express recur­sive features of a language.

The result is that these five rules suffice to match any M-expres­sion, no matter how deeply nested. The parse tree for our test expres­sion will look like this (adjusting the white space for clarity):

As before, we can see that all the char­ac­ters in our source string appear in a node of the parse tree, and these nodes corre­spond to the names and patterns of the produc­tion rules.