Go with the flow: basic

Before we start writing the parser, let’s remind ourselves of the possible tokens we could get from the lexer via the tokenizer:

Using these tokens, and the ground rules laid out in spec­i­fi­ca­tion and setup, we can reason out a grammar for BASIC. Of course, we’ll be using #lang brag once again to generate a parser from that grammar.

Because many elements of BASIC have the same names as things in Racket, we’ll prefix our produc­tion rules with b- for clarity. This conven­tion isn’t required by #lang brag—it’ll just help keep things read­able, espe­cially once we get into the expander.

Program lines

Our first rule is b-program, which will become the root node of our parse tree. Every BASIC program is made of lines sepa­rated by NEWLINE tokens, which we could express like so:

The * quan­ti­fier means “zero or more repe­ti­tions” of the preceding group, in this case the paren­the­sized subpat­tern NEWLINE b-line.

This rule will work with our sample program:

But as language designers, we want to be alert to the possi­bility of other mischief, like a program with nothing in it:

Or a program with nothing but newlines:

Or a program with extra newlines scat­tered around:

There’s no reason these programs shouldn’t run—the obvious inter­pre­ta­tion is “ignore the newlines and continue as usual”. But if our parser rule for b-program isn’t suffi­ciently lenient, then these oddball programs will raise parsing errors.  + An appli­ca­tion of Postel’s Law.

So let’s revise the rule. We can make each b-line element optional by putting it in square brackets:

Reading the rule, we should be able to convince ourselves that it will handle a range of edge cases without violating the key require­ment, which is that multiple lines must be sepa­rated by at least one newline. (Of course, we could & should write unit tests to be sure.)

Moving on to the grammar for each indi­vidual line. A line has a line number, which is an integer, followed by zero state­ments, one state­ment, or multiple state­ments sepa­rated by :. If we also make sepa­rate rules for b-line-num and b-statement, we can write our b-line rule with three cases:

But we can also combine the three cases into one by using a * rather than a + quan­ti­fier on the colon-sepa­rated state­ments, and putting brackets around the state­ments, to repre­sent an optional match:

Not bad. And it would work with our sample program. But having just learned about the impor­tance of lenient rules, we should ask ourselves what should happen in edge cases like these:

There’s no reason these lines shouldn’t work. So let’s make our line grammar less finicky, and just skip over blank state­ment sepa­ra­tors. We can do this the same way we did in the b-program rule—by putting square brackets around each b-statement to make them optional:

That rule implies that the only thing that must be in a line is a line number.

Rem state­ments

A rem state­ment can form the tail of any line. We add a b-rem rule that only matches our special REM token. Then we make b-rem an optional match at the end of any b-line:

Other state­ments

We make three rules to cover each of our remaining state­ments: b-end, b-print, and b-goto. Then, the rule for b-statement simply chooses among these possi­bil­i­ties:

The b-end rule only matches a literal "end":

We remember from spec­i­fi­ca­tion and setup that the print state­ment is made of a literal print token, and then any number of string or numer­ical expres­sions as input, sepa­rated by ;. To express the possible input, we intro­duce a helper rule called b-printable that’s a choice between a STRING token and a new b-expr (which we’ll figure out momen­tarily). Then, in the b-print rule, we follow the approach we used in b-line, expressing b-print as an optional b-printable, followed by any number of optional b-printable argu­ments with ; sepa­ra­tors:

Finally, the b-goto consists of the literal "goto" token and a numer­ical expres­sion:

Expres­sions & values

All that’s left is to sort out numbers and numer­ical expres­sions. The only numbers we have are inte­gers and deci­mals—already repre­sented by the INTEGER and DECIMAL tokens—and the only numer­ical expres­sion we have to worry about is a sum:

Let’s do b-sum first. A sum is any series of numbers with + signs in between. Following the pattern we figured out for b-program and b-line, we can write the rule like so:

This time, however, we’re not going to be lenient about input, because an expres­sion like + + + or 4 + + 5 has no natural meaning as a sum. Instead, we leave it alone, so it will raise a parsing error.

Now to finish b-expr. It would be fine to make this rule a choice between a b-sum and a b-number. But a b-sum can itself be a single b-number. So it suffices to make b-expr a b-sum:

The inter­po­si­tion of b-expr may seem unnec­es­sary now. But in the expander, we’ll see why it’s useful—we can use it as a “gateway” through which all our numer­ical expres­sions have to pass (and smooth over the differ­ences between Racket math and BASIC math). It also means that other elements, like b-print, only need to work with b-expr, rather than having to sepa­rately deal with other elements like b-sum, b-number, etc.

In terms of imple­menting the rules in spec­i­fi­ca­tion and setup, our grammar is done. Our parser will be able to handle all valid programs, including some weird ones.

Checking our work

Let’s make sure our parser works as expected. First, let’s try this small program:

We can check the parse tree by setting up a little test file:

The result looks like this:

As usual, we see that the parse tree contains every token that the parser consumed. The first element of each paren­the­sized node is the name of the rule in the grammar that was used to create the node. The remaining elements are the tokens that were matched to the pattern on the right-hand side of that rule. Named tokens like STRING and INTEGER are repre­sented by their actual token values.

(Those inter­ested in making unit tests—this would be a great moment to start copying out these test expres­sions & their results, to be combined into tests using check-equal?.)

Let’s also make sure our parser works on our orig­inal sample program:

We can move the source code into our testing file:

This time, the result looks like this:

This is correct. Admit­tedly, it’s hard to know this for sure unless we were to manu­ally pencil out the parse, which for a larger program is a drag. For unit tests, it’s simpler to use one- or two-line sample programs, where it’s easy to see how the source will be converted into a parse tree. But this proves, at least, that our sample program doesn’t trigger any errors from the tokenizer or the parser.

Dialects for debug­ging

“Why are we copying source code into another file? Why not just make a dialect called basic/parse-only that reads the source & returns the parse tree?”

Ah, what a wonderful idea. And we now have the skills to do it.

Let’s confirm the mission objec­tives. We want to be able to invoke this new basic/parse-only dialect like so:

And get its parse tree as the result:

This should be easy now. To make #lang basic/parse-only, we create a "parse-only.rkt" module and fit it with a simple reader and expander:

Here, our read-syntax func­tion takes a path and port and converts it into a module expres­sion. (Recall that our improved make-tokenizer func­tion takes both the port and path as input, so it can calcu­late source loca­tions correctly.) The expander we use in the module expres­sion is the same file, basic/parse-only. We then provide our read-syntax from a reader submodule.

The expander is like­wise simple: just a parse-only-mb that will be renamed on export as #%module-begin. All this macro does is put a quote prefix on our PARSE-TREE.

Now we can run our test program with our new inter­preter:

Sure enough, we get the parse tree:

What’s nice about using a dialect here is that it’s easy to switch back to running the file normally—we simply adjust the #lang line at the top (using basic-demo in this example since we haven’t made our own basic expander yet):  + What’s also inter­esting is the idea that a single source file can have different results depending on the inter­preter that runs it.

Like­wise, it’s easy to make a similar basic/tokenize-only dialect that reveals the output from the tokenizer:

And invoke it like so:

The point here is that once we know how to create languages quickly—at this point, we can make one with a few lines of code—they become a conve­nient tool even for small jobs.

Error high­lighting

Before we move on, let’s pause to enjoy the bene­fits of tracking source loca­tions using lexer-srcloc instead of lexer. Let’s return to our "test.rkt" file:

First, let’s induce a lexing error. A lexing error will occur if the lexer encoun­ters a char­acter that it can’t match with any of its lexing rules. We add a bogus line 25 xyzzy to our test program and run it again:

We get an error in the REPL from the lexer. But DrRacket will also high­light the first char­acter that failed to lex, and move the inser­tion point there:

The lexer only reports the x as an error—not the whole xyzzy—because it stops as soon as it can’t match any rule, and going further would be futile. We can induce a slightly different lexing error by changing line 25 to prinxyzzy:

This time, DrRacket high­lights prinx because the lexer got as far as matching prin—the first four char­ac­ters of the valid token print—before things went side­ways.

Let’s now induce a parsing error. To trigger a parsing error, our program needs to lex correctly (that is, it has to be made of valid elements) but some element has to be in a place that the parser grammar doesn’t expect to find it. For instance, let’s change line 25 to print goto:

This time, we get a parsing error, with the offending goto high­lighted:

By the way, if a program contains both a lexing error and a parsing error, the lexing error will be high­lighted first—regard­less of where in the program it occurs—because the lexer runs before the parser.

Feel free to noodle around with "test.rkt" and induce other errors. What we should notice is that we can start bene­fiting from DrRacket inte­gra­tion even before we’ve started the expander. More­over, all we had to do to get error high­lighting was use lexer-srcloc. Our lexer, tokenizer, and parser coop­er­ated with DrRacket to do the heavy lifting.

Cuts & splices

Though our parser works, we’d like to make our parse tree tidier.

By default, every matched token shows up in the parse tree, and then the whole parse tree is passed to the expander. The problem is that our parse tree will end up with a bunch of tokens that were only needed to complete the parsing. Once they’ve served their purpose, it would be nice to filter them out, so that our expander can deal with simpler, cleaner input.

For instance, let’s take a closer look at the parse tree for our shorter sample program (which we can generate with our new #lang basic/parse-only dialect):

We could work with this parse tree if we had to. But it contains a lot of super­fluous elements that don’t affect the meaning of the program:

If we omitted the unnec­es­sary elements, and spliced the elements from inside the b-line-num, b-statement, and b-number nodes, our parse tree would end up like this:

How can we get there? The brag language lets us add cuts and splices to our grammar to simplify the parse tree. Using cuts and splices, we can improve our grammar so that it auto­mat­i­cally produces this simpli­fied version of the parse tree. This, in turn, will simplify the work we do in the expander, because we don’t have to handle a bunch of extra­neous input.

A cut in a brag grammar will delete the item from the parse tree. A cut is notated by adding a slash / prefix to either the rule name (appearing on the left side of the rule) or a pattern element (appearing on the right). If the cut is applied to a rule name, the rule name disap­pears from the parse tree, but its node and its matched elements remain. If the cut is applied to a pattern element, that element disap­pears entirely from nodes matching that rule in the parse tree.

In this case, we only need to use cuts on the pattern elements. We want to get rid of the NEWLINE in the b-program rule, the ":" in the b-line rule, the ";" in the b-print rule, the "+" in the b-sum rule, and the state­ment names "end", "print", and "goto". We do this by prefixing each of these pattern elements with /:

Now, if we generate our sample parse tree again:

We can see that the cut elements are gone:

A splice in a brag grammar will merge the elements of a node into the surrounding node. A splice is notated by prefixing either the rule name or a pattern element with an at sign @. As with cuts, if the splice is applied to a pattern element, that element is spliced only within that rule. If the splice is applied to a rule name, then the splice is applied every time the rule appears in the grammar.

Here, we want to splice instances of b-line-num, b-statement, b-printable, and b-number. Since we want these splices to be global—that is, happen every time the rule appears—we apply the splices to the rule names by prefixing them with @:

This time, when we generate our sample parse tree:

We get the tidy parse tree we were orig­i­nally aiming for:

We can also try parsing our larger sample program:

With similar results (notice in partic­ular how close we’re already getting to the pseudocode for our imple­men­ta­tion):

Cuts and splices are strictly a conve­nience. We’re not required to use them. And they’re not the only way of pruning a parse tree. We could do the same work in the expander, sorting through the raw parse tree when it arrives and tossing out what we don’t need.

But often, that amounts to writing a func­tion that re-parses the parse tree. Given that we’re already making a parser, it makes sense to consol­i­date the house­keeping here. As we’ve seen, we can easily stream­line the parse tree by adding a few / and @ marks.

Finished parser

We are now really, truly done with our parser, and can move on to finishing the reader and then tack­ling the the expander. The extra effort we invested in the parser will pay divi­dends then.