4 — The scanner | Mica Development UG

The scanner — Wirth called it getsym, everyone else calls it a lexer or tokenizer — answers one question, over and over: what is the next word?

It is the only part of the compiler that ever looks at a character. Everything after it works in symbols, and that separation is the first and cheapest simplification a compiler makes. The parser never has to know that := is two characters or that comments exist.

The vocabulary

PL/0’s entire vocabulary is thirty-one symbols:

typedef enum {
    nul, ident, number, plus, minus, times, slash, oddsym, eql, neq, lss, leq, gtr, geq,
    lparen, rparen, comma, semicolon, period, becomes, beginsym, endsym, ifsym, thensym,
    whilesym, dosym, callsym, constsym, varsym, procsym, eofsym
} Symbol;

and in Mica, the same list as an enumeration:

exp Symbol = (SymNul, SymIdent, SymNumber, SymPlus, SymMinus, SymTimes, SymSlash,
              SymOdd, SymEql, SymNeq, SymLss, SymLeq, SymGtr, SymGeq, ...);

One detail in that list is load-bearing: nul is first, so it is the zero value. An uninitialized symbol, and a lookup that finds nothing, both read as “nothing here” rather than as some valid token. Ordering an enumeration so that its zero value means absent is a small habit that removes a whole class of bug, and it costs nothing.

What the scanner produces

The scanner does not return a token object. It deposits its answer into its own state and returns:

typedef struct {
    const char* source;
    int length;
    int offset;         /* the cursor: the index of the character to read next */
    int line;
    int column;

    /* what the last scan produced */
    Symbol symbol;                   /* the symbol just read                   */
    char identifier[MAX_IDENTIFIER]; /* its spelling, when it is an identifier */
    int number;                      /* its value, when it is a number         */
    int symbol_line;                 /* the line the symbol started on         */
    int symbol_column;               /* the column the symbol started on       */

    ErrorList* errors;
} Scanner;

This is Wirth’s shape, kept deliberately. He had sym, id and num as global variables; here they are fields of a struct that the parser owns. The change matters (two compilations can now run in one process) and the shape does not: one symbol is available at a time, and asking for the next one destroys the previous.

That is called a one-symbol lookahead, and it is exactly as much as recursive descent needs. If you have read about parsers that need more, this is the baseline they are more than.

Positions, from the first line

Look again at the last two fields. line and column are where the cursor is; symbol_line and symbol_column are where the current symbol started.

Two positions, not one, and the second is the one every diagnostic uses:

void scanner_next(Scanner* scanner) {
    scanner_skip_space_and_comments(scanner);

    scanner->symbol_line = scanner->line;
    scanner->symbol_column = scanner->column;
    ...

Wirth’s original could only print a caret under the current character of the current line, because that was the only position it had. The result is the experience everyone remembers from old compilers: the error is reported after the thing that caused it, sometimes lines after.

Recording where a symbol began, before consuming it, is what lets this compiler say:

3:11: error 11: 'x' is not declared

and point at the x rather than at whatever followed it. It costs two integers and one assignment per symbol. Do this in every scanner you ever write.

Reserved words

A word like begin and a word like arg are scanned identically — a run of letters and digits — and then distinguished by a lookup:

/* the binary search over the sorted reserved-word table — Wirth's own lookup device */
int low = 0;
int high = reserved_word_count - 1;

while (low <= high) {
    int middle = (low + high) / 2;
    int order = strcmp(scanner->identifier, reserved_words[middle].word);

    if (order == 0) {
        scanner->symbol = reserved_words[middle].symbol;
        return;
    }

    if (order < 0) {
        high = middle - 1;
    } else {
        low = middle + 1;
    }
}

scanner->symbol = ident;

Eleven reserved words, kept in alphabetical order:

static const struct {
    const char* word;
    Symbol symbol;
} reserved_words[] = {
    {"begin", beginsym}, {"call", callsym}, {"const", constsym}, {"do", dosym},
    {"end", endsym}, {"if", ifsym}, {"odd", oddsym}, {"procedure", procsym},
    {"then", thensym}, {"var", varsym}, {"while", whilesym},
};

Wirth used binary search because his target had neither a hash table nor a map. It is kept here for a better reason than nostalgia: it is the right choice at this size. Eleven entries is four comparisons worst case, with no hashing, no allocation, and no table to build at start-up. A hash map would be slower and larger.

The habit worth taking away is not “use binary search”. It is: know the size of your problem before you choose the data structure for it. Compilers are full of tables with a dozen entries and full of people who reached for a hash map.

The Mica twin makes the same decision and spells the table differently — as two routines rather than an array, for a reason worth stealing:

{ the eleven reserved words in alphabetical order, answered by index.

  The table is a routine rather than an array in the state record because it never changes - constant
  data that lives in mutable state is an invitation to mutate it. }
function ReservedWord(index : int32) : string;
begin
    case index of
        0: ReservedWord := "begin";
        1: ReservedWord := "call";
        2: ReservedWord := "const";
        ...
    else
        ReservedWord := "while"
    end;
end;

with a matching ReservedSymbol(index) answering the symbol each word stands for. Two routines, one table split in half — they must be edited together, which the comment says out loud. The binary search over them is the same search as in C.

Case, and one deliberate refusal

PL/0 is case-insensitive, so the spelling is folded as it is read:

scanner->identifier[length++] = (char)tolower((unsigned char)scanner_peek(scanner));

Fold on the way in, once, rather than comparing case-insensitively everywhere afterwards. Every later comparison — reserved words, the symbol table — is then an ordinary strcmp.

Now a place where this compiler deliberately does not do the convenient thing. Here is how it decides what whitespace is, in the Mica twin:

{ whether the character is ASCII whitespace, stated as the explicit six-character set. Naming all six
  rather than asking a library "is this space-like" is deliberate: an invisible byte silently skipped as
  whitespace is exactly the class of mistake this compiler family refuses to make anywhere. }
function IsSpace(c : unicode) : bool;
begin
    IsSpace := (c = ' ') or (c = Chr(9)) or (c = Chr(10)) or (c = Chr(11)) or (c = Chr(12)) or (c = Chr(13));
end;

The convenient version is one library call. The explicit version is one line longer and cannot be surprised by a locale, by a Unicode space, or by a non-breaking space pasted in from a web page — the one that produces a syntax error nobody can see.

Numbers, and a limit that is not arbitrary

if (value > MAX_NUMBER) { ... }

MAX_NUMBER is 2047. That looks like a strange choice until you know where it comes from: a constant is loaded by embedding it in the address field of a stack-machine instruction, and that field is eleven bits wide. The limit is not a policy — it is the target’s shape reaching back into the front end.

That happens in real compilers constantly, and it is worth noticing here where it is small enough to see whole. When you meet an odd limit in a language, looking for the machine underneath it is usually productive.

Comments, and what Wirth left out

PL/0 as published has no comment form at all. Both twins add one — { … }, Pascal’s — because a teaching program that cannot be annotated is a poor teaching program. It is skipped in the same loop as whitespace:

static void scanner_skip_space_and_comments(Scanner* scanner) {
    for (;;) {
        while (scanner->offset < scanner->length && isspace((unsigned char)scanner_peek(scanner))) {
            scanner_advance(scanner);
        }

        if (scanner_peek(scanner) != '{') {
            return;
        }
        ...

Note the structure: an outer for(;;) around both, because a comment may be followed by whitespace which may be followed by another comment. A single pass of “skip space, then skip a comment” would leave { a } { b } half-consumed. This is the kind of bug that survives a long time, because most test programs never have two comments in a row.

The cursor, and why `advance` is not `offset++`

static void scanner_advance(Scanner* scanner) {
    if (scanner->offset >= scanner->length) {
        return;
    }

    if (scanner->source[scanner->offset] == '\n') {
        scanner->line++;
        scanner->column = 1;
    } else {
        scanner->column++;
    }

    scanner->offset++;
}

Every character moves through exactly one place, and that place is the only place that knows what a newline means. Scatter offset++ through the scanner and the line counter drifts the first time you add a case that forgets it — and a drifted line counter produces diagnostics that point at the wrong line, which is worse than no diagnostic at all.

One cursor, one advance. It is a small rule with a large payoff.

Try it

The scanner is the easiest part to experiment with, because its output is visible in every diagnostic. Feed the compiler something wrong and watch the positions:

printf 'var a;\nbegin\n   a := 1 $ 2\nend.\n' > /tmp/bad.pl0
../build/c/pl0 run /tmp/bad.pl0

3:11: error 35: the character '$' has no meaning in PL/0
1 error(s)

Line 3, column 11 — the $ itself, not the end of the line and not the statement that contained it. That is symbol_line and symbol_column doing their job.

Next: 5 — The symbol table, where names acquire meanings.

The vocabulary#

What the scanner produces#

Positions, from the first line#

Reserved words#

Case, and one deliberate refusal#

Numbers, and a limit that is not arbitrary#

Comments, and what Wirth left out#

The cursor, and why advance is not offset++#

Try it#