Go with the flow: basic

In previous tokenizer modules—for instance, those for bf and jsonic—we made one func­tion, make-tokenizer. It returned a func­tion called next-token that succes­sively retrieved tokens from an input port using a char­acter-matching func­tion called a lexer.

Since then, we’ve learned that a lexer can also be useful for syntax coloring. So this time, we’ll sepa­rate our lexer from our tokenizer. That way, we can reuse it later for the syntax colorer.

Rather than start with "basic/tokenizer.rkt", we create a new "basic/lexer.rkt" module:

Previ­ously we used lexer to set up our matching rules. That worked fine, but when we wanted to add source loca­tions, we found ourselves doing a lot of house­keeping—we had to manu­ally fill in the source-loca­tion fields for the tokens gener­ated on the right-hand side.

This time, we switch to lexer-srcloc, a variant of lexer that auto­mat­i­cally gathers source-loca­tion infor­ma­tion and attaches it to our tokens. We get the same source loca­tions as before, but with zero manual labor.

To make this happen, lexer-srcloc returns instances of a struc­ture called a srcloc-token. This struc­ture holds two values: a token (that is, what­ever we put on the right-hand side of the rule, which will usually be a string or an instance of the token struc­ture) and a source loca­tion (which is itself an instance of the srcloc struc­ture).

But we don’t need to get bogged down in the details. lexer-srcloc will auto­mat­i­cally create the correct srcloc and srcloc-token struc­tures. In turn, any parser made with #lang brag can take these srcloc-token struc­tures as input. So the output from lexer-srcloc can be passed to our parser without any extra house­keeping.

By the way, since a lexer takes an input port as an argu­ment, why aren’t we declaring this func­tion as (basic-lexer port)? If we look at our previous exam­ples, for instance the jsonic tokenizer, we also didn’t declare the lexer with an argu­ment. The reason is that both lexer and lexer-srcloc return a lambda that takes one argu­ment, so we omit the argu­ment from the left-hand side of the decla­ra­tion.

For the same reason, these two decla­ra­tions are the same:

In the second case, because the right-hand side is a lambda expres­sion, we don’t declare the x argu­ment on the left. In fact, the lambda nota­tion on the bottom is the “real” way func­tions are handled in Racket—the top nota­tion is a conve­nience that’s trans­formed into the bottom nota­tion. (For more about lambda nota­tion, see func­tions.)

If we wanted, we could declare basic-lexer like so:

But that’s just a wordier way of saying the same thing.

Lexer rules

First, we handle white­space. Most white­space in BASIC is ignored. But newlines have special status, because each line of the program has to be on a sepa­rate line of the file. This program is valid:

But this version, with the newline removed, is not:

When we write the parser, we’ll need to keep these two cases sepa­rate. We can only do that if we preserve the newline as a token. So our first white­space-lexing rule will match the "\n" char­acter, and put it inside a token struc­ture named NEWLINE:

But all the other white­space, we can ignore. In previous lexers, we ignored white­space or comments by recur­sively calling the lexer to fetch the next token. This shortcut doesn’t work with lexer-srcloc, because each recur­sive call also recur­sively wraps more layers of source-loca­tion infor­ma­tion. That’s not what we want.

Let’s learn an alter­nate tech­nique:

Rather than ignoring certain source char­ac­ters within the lexer, we can mark the tokens as “skip­pable” so that the parser ignores them. We do this by wrap­ping them in a token struc­ture as usual, but we make the token skip­pable by passing the #:skip? keyword argu­ment with a #t value. The parser will ignore this token, as if it had never been there in the first place. Problem solved.

A rem at the begin­ning of a line marks a line comment:

Recall from spec­i­fi­ca­tion and setup that a rem doesn’t remove the line entirely from the program—it can still be the target of a goto state­ment. So we only want to soak up the char­ac­ters on the right side of the rem state­ment (not the line number).

Further­more, though the "\n" marks the end of the rem, we don’t want to absorb the "\n" itself (because of its semantic signif­i­cance in sepa­rating lines). So we use from/stop-before to capture these char­ac­ters and put them in a REM token. Unlike from/to, which captures the left and right boundary char­ac­ters, from/stop-before captures the left boundary char­acter but not the right (hence “stop before”).

Then we add our other supported state­ments—print, goto, end—our only supported numer­ical oper­a­tion +, and the sepa­ra­tors for multiple print argu­ments ; and multiple state­ments ::

:or is a lexer func­tion that matches one of a listed set of possi­bil­i­ties.

As the return value, we make a token struc­ture, passing lexeme in both the type and value fields. Strictly speaking, we don’t need to return a token struc­ture for this rule. We could return the raw lexeme value, because it’ll be matched liter­ally in the parser. But when we get to the syntax colorer, we’ll find it more conve­nient to have the lexer results consis­tently pack­aged into token struc­tures.

Finally we need to put in our data types: inte­gers, deci­mals, and strings.

Both inte­gers and deci­mals need to match a string of digits. To simplify our nota­tion, we use define-lex-abbrev to make a little named subpat­tern that we can use in other rules. Our abbre­vi­a­tion digits will match any sequence of digits (where char-set means “match any char­acter in this string” and :+ still means “one or more”):

Once we have digits, we can easily write rules to match inte­gers and deci­mals:

An integer is just digits. We label the token with the name 'INTEGER, and use string->number to pass through the numeric value rather than its string repre­sen­ta­tion.

The decimal rule is a little trickier, because we want to capture three valid possi­bil­i­ties:

We can use :seq, a lexer func­tion that lets us match a series of patterns in a row, to express these possi­bil­i­ties as patterns, and then use :or to choose among them:

But we can combine the first and second cases into a single pattern by using :? to make the first digits subpat­tern optional (again, just like ? in a regular expres­sion).

And that becomes the pattern for our rule. Though we shouldn’t get overzealous about stream­lining the pattern, because this is wrong:

This rule is too broad, because it would also match a naked decimal point. A decimal number always needs digits on one side or the other. So we need two pieces to our pattern.

To finish, we label the token with the name 'DECIMAL, and again use string->number to pass through its numeric value.

Last, we have strings:

For these, we can use from/to to match anything delim­ited by either single or double quotes. When we make the token, we don’t need the quote marks, so we use substring to drop the first and last char­ac­ters of the matched lexeme. Then we package this into a token called 'STRING.

And that’s our finished lexer.

Testing the lexer

Well, almost finished. No func­tion is really done until it’s thor­oughly tested. We could put tests inside "basic/lexer.rkt" module using a test submodule, as we’ve done before. But here’s how we could make a set of tests for the lexer in a sepa­rate file:

First, we define lex, which is a helper func­tion that will take a string and lex it into a list of tokens using basic-lexer and the helper func­tion apply-port-proc, which comes from brag/support. apply-port-proc applies a func­tion to an input port (or string) repeat­edly until it reaches the end, and then returns the results in a list.

Then we use testing func­tions from rackunit like check-equal? and check-exn to compare the results of lex with lists of srcloc-token struc­tures. Here are some simple sample tests that cover every lexing rule we wrote for basic-lexer (but feel free to add others):