5 — The symbol table

Every compiler has to answer one question thousands of times: when the program says x, which x does it mean?

That question is called name resolution, and it has a reputation for being complicated. In PL/0 it is one array, one integer, and a loop that runs backwards. Once you see it in this form, every more elaborate symbol table you meet later is a variation you can recognize.

What a name can be

PL/0 has exactly three kinds of thing a name can stand for, and that is the whole of its type system:

typedef enum { kind_constant, kind_variable, kind_procedure } Kind;

An entry records the kind and whatever that kind needs:

typedef struct {
    char name[MAX_IDENTIFIER];
    Kind kind;
    int value;   /* a constant's value                                     */
    int level;   /* the block nesting depth the name was declared at       */
    int address; /* a variable's frame offset, or a procedure's handle     */
} Entry;

The fields a given kind uses are disjoint. A constant uses value; a variable and a procedure use level and address, and address means different things in each — for a variable it is the offset inside its activation record, for a procedure it is the back end’s handle for its code.

Wirth expressed that with a Pascal variant record. The honest C equivalent is one struct whose unused fields stay zero, and it is worth noticing that the “wasteful” version is also the one that never reads a field that was written as something else. A tagged union would be safer still; at three kinds and five fields, the struct wins on readability, which at this size is the property that matters.

The table

typedef struct {
    Entry entries[MAX_TABLE];
    int count;
} Table;

One flat array shared by every block, and a count. That is all.

There is no tree of scopes, no map per block, no linked list of parents. This surprises people, so it is worth being explicit: the nesting is represented by the order of entries in one array, not by a data structure that mirrors the program’s shape.

The scope rule is a loop direction

Here is name resolution, complete:

/* The entry a name resolves to, searching from the innermost declaration outwards, or a null pointer
 * when the name is unknown. This is PL/0's entire name resolution. */
const Entry* table_lookup(const Table* table, const char* name) {
    for (int index = table->count - 1; index >= 0; index--) {
        if (strcmp(table->entries[index].name, name) == 0) {
            return &table->entries[index];
        }
    }

    return NULL;
}

And in Mica, the same loop, answering an index rather than a pointer:

exp function Position(t : pointer SymbolTable, name : string) : int32;
var
    i : int32;
begin
    Position := -1;
    i := t.Count - 1;

    while i >= 0 do
    begin
        if t.Entries[i].Name = name then
        begin
            Position := i;
            leave;
        end;

        i := i - 1;
    end;
end;

Read the loop bound again: it starts at the end and walks backwards.

That direction is the scope rule. Entries are appended as declarations are met, so later entries are from more deeply nested blocks. Searching backwards finds the most recently declared match — which is the innermost one — first. Shadowing is not implemented anywhere; it is a consequence of the search direction.

This is the single most elegant thing in PL/0, and it is one line of loop control. When you next read about scope chains and environment frames, come back and notice that they are all doing this, with more machinery.

Leaving a block

If declarations are appended as blocks are entered, something must remove them when blocks end. That something is two functions:

int table_mark(const Table* table) {
    return table->count;
}

void table_release(Table* table, int mark) {
    table->count = mark;
}

A block records the count on the way in, and truncates back to it on the way out. Everything declared in between disappears.

Nothing is erased and nothing is freed — the count simply moves. It is the same trick as a stack allocator, and it works for the same reason: declarations have strictly nested lifetimes, so a stack discipline is exactly right.

Here is the parser using it, in the routine that parses one block:

int mark = table_mark(&parser->table);
...                                     /* declarations and nested procedures */
...                                     /* the block's statement */
table_release(&parser->table, mark);

Four lines around the entire body of a block. That is scope management, whole.

The one thing Wirth’s table could not do

There is one improvement over the original here, and the reason it was possible is worth more than the improvement:

/* Whether the name is already declared in the block that began at the given mark. A name may shadow an
 * outer one — that is what nesting is for — but declaring it twice in one block is a mistake the
 * original could not detect, because its table never forgot where a block began. */
bool table_declared_since(const Table* table, int mark, const char* name) {
    for (int index = mark; index < table->count; index++) {
        if (strcmp(table->entries[index].name, name) == 0) {
            return true;
        }
    }

    return false;
}

Wirth’s compiler could not report var x, x;. Not because he overlooked it — because his table moved an index and never remembered where the current block started, so “is this a duplicate in this block?” was a question his data structure could not answer.

The mark makes it answerable. Everything at or after the mark belongs to the block being declared right now; everything before it is an enclosing block, where the same spelling is legitimate shadowing.

Try it:

printf 'var x, x;\nbegin\n   x := 1\nend.\n' > /tmp/dup.pl0
../build/c/pl0 run /tmp/dup.pl0

1:8: error 31: 'x' is already declared in this block
1 error(s)

A diagnostic stops the program from running — but notice what it does not stop. The duplicate is reported and then entered into the table anyway, so the rest of the parse still knows the name x and can go on checking the statements that use it. Had the parser refused to enter it, every later use would have produced a second, useless diagnostic: ‘x’ is not declared, four more times.

That decision — report, then carry on in the most plausible way — is what separates a compiler that reports five real mistakes from one that reports fifty phantoms, and it is the whole subject of the next chapter.

Levels and addresses

Two fields have not been explained yet, and they are the two that make nesting work at run time.

level is the block nesting depth the name was declared at. The main program is level 0, a procedure declared in it is level 1, a procedure declared in that is level 2.

address is, for a variable, its offset inside its own activation record.

Neither is useful alone. What the back end is handed is the difference:

} else if (entry->kind == kind_variable) {
    parser->backend->load_variable(parser->backend, level - entry->level, entry->address);
}

level there is where the use is; entry->level is where the declaration is. Their difference is how many nesting levels out the variable lives — 0 for a local, 1 for the enclosing procedure’s variable, 2 for one two levels out.

That number is the whole interface between the front end and the back end on the subject of nesting. The front end computes it from the symbol table; the back end decides what to do about it, and the two back ends in this series do completely different things:

The front end does not know or care which. It just subtracts two integers.

Why declarations are entered as they are met

One last detail with a lesson in it. Look at where a variable’s address comes from:

static int parser_variable_declarations(Parser* parser, int level, int mark, int already_declared) {

The parser counts variables as it declares them, and each one’s address is its position in that count. The count is also what the block later tells the back end so it can size the activation record.

So the symbol table is not only answering “what does this name mean” — it is assigning storage as a side effect of parsing declarations. In a bigger compiler those are separate passes over a tree. Here they are the same walk, and seeing them fused makes it obvious what a later separation would be for: you split them when you need to know something about a declaration before you have read all of them.

PL/0 never does, so it never splits them.

Next: 6 — The parser, where the grammar becomes a program.