6 — The parser | Mica Development UG

The parser is the part of a compiler that people expect to be hard. It is the part where the theory gets deepest — LL, LR, LALR, parser generators, ambiguity, lookahead sets.

PL/0’s parser uses none of that, and it is not a simplification. Recursive descent is what most production compilers use, including GCC’s and Clang’s C++ front ends, for a reason that will be obvious by the end of this chapter: it is the only technique in which the parser reads like the grammar, and a compiler that reads like its grammar is a compiler you can fix.

The grammar is the program

Here is the rule for a term, from chapter 1:

term = factor { ( "*" | "/" ) factor } .

And here is the code:

/* A term is a sequence of factors joined by '*' and '/'. That this is a separate procedure from
 * 'expression' is the whole of PL/0's operator precedence. */
static void parser_term(Parser* parser, int level, SymbolSet follow) {
    SymbolSet multiplicative = BIT(times) | BIT(slash);
    parser_factor(parser, level, follow | multiplicative);

    while (set_has(multiplicative, parser->scanner.symbol)) {
        ArithmeticOperation operation = parser->scanner.symbol == slash ? op_divide : op_multiply;

        scanner_next(&parser->scanner);
        parser_factor(parser, level, follow | multiplicative);
        parser->backend->arithmetic(parser->backend, operation);
    }
}

Line for line:

Grammar	Code
`factor`	`parser_factor(...)`
`{ … }`	`while (...)`
`( "*" \| "/" )`	`set_has(multiplicative, symbol)`
`factor`	`parser_factor(...)` again

That is the entire method. One procedure per grammar rule; the rule’s body becomes the procedure’s body. A repetition becomes a loop, an alternative becomes a branch, and a reference to another rule becomes a call.

The same rule in Mica, which spells the set membership with in rather than a bit test:

{ a term is a sequence of factors joined by '*' and '/'. That this is a separate routine from
  'Expression' is the whole of PL/0's operator precedence - nothing else encodes it. }
procedure Term(termFollow : SymbolSet);
var
    multiplicative : SymbolSet;
    operation : int32;
begin
    multiplicative := [SymTimes, SymSlash];
    Factor(termFollow + multiplicative);
    ...

Where precedence lives

Now the thing everyone gets told and few people are shown. 2 + 3 * 4 is 14, not 20. Where is that decided?

Not in a table. Not in a precedence-climbing loop. It is decided by the fact that expression calls term and term calls factor, and by nothing else:

expression  →  term { (+|-) term }        ← the loosest binding, so the outermost
term        →  factor { (*|/) factor }    ← tighter, so nested inside
factor      →  ident | number | ( expression )

expression cannot see a * — by the time control returns to it, term has already consumed the whole multiplication and emitted it. The multiply happens inside one iteration of the addition loop, so it happens first.

Precedence is the nesting order of the procedures. Three levels of nesting give three levels of precedence. If you want another one — say ^ binding tighter than * — you add a fourth procedure between term and factor, and you change nothing else. That is exercise 3 in chapter 11.

The parentheses case closes the circle: factor can call expression again, so ( … ) re-enters at the loosest level. Three procedures and one back edge give you arbitrarily nested arithmetic.

Emitting as you go

Look again at the last line of the loop in parser_term:

scanner_next(&parser->scanner);
parser_factor(parser, level, follow | multiplicative);
parser->backend->arithmetic(parser->backend, operation);

Read the order: consume the operator, parse the right operand — then emit the operation.

That ordering is what turns infix source into postfix output. By the time arithmetic is called, the code to push both operands has already been emitted, because parsing an operand is emitting it. So 2 + 3 * 4 emits:

load_constant 2
load_constant 3
load_constant 4
arithmetic multiply
arithmetic add

which is 2 3 4 * + — reverse Polish, produced for free by the recursion order. No tree was built, and no traversal happened. This is the heart of syntax-directed translation, and it is four lines.

The state a parse carries

typedef struct {
    Scanner scanner;
    Table table;
    Backend* backend;
    ErrorList* errors;
    int depth; /* the current recursion depth, so a pathological program is refused */
} Parser;

Wirth kept all of this in globals. Making it a struct costs one parameter everywhere and buys something specific: the compiler can compile two programs in one process, which is what lets the twins run their own diagnostic table through their own parser twenty-five times in a single run.

The depth field is a guard, not a feature:

static void parser_descend(Parser* parser) {
    if (++parser->depth > MAX_PARSE_DEPTH) {
        refuse("the program nests deeper than this compiler follows");
    }
}

Recursive descent recurses on the input. A program with ten thousand nested parentheses will recurse ten thousand deep, and a C stack does not survive that — it dies with a segmentation fault, which is not a diagnostic. Two hundred is far past anything a real PL/0 program does, and hitting it produces a sentence.

Any recursive-descent parser exposed to input it did not write needs this counter. It is three lines and it converts a crash into a message.

Error recovery: the actual hard part

Parsing correct programs is easy. What separates a usable compiler from a frustrating one is what happens after the first mistake.

The naive answer — stop at the first error — is unhelpful, because you fix one thing, recompile, and find the next. The naive alternative — keep going and report everything — is worse: a parser that has lost its place reports dozens of phantom errors that vanish when you fix the first real one.

Wirth’s answer is one routine, and it is the technique most hand-written parsers still use:

static void parser_expect(Parser* parser, SymbolSet expected, SymbolSet recovery, int code, const char* message) {
    if (set_has(expected, parser->scanner.symbol)) {
        return;
    }

    parser_error(parser, code, "%s", message);

    SymbolSet stop = expected | recovery | BIT(eofsym);

    while (!set_has(stop, parser->scanner.symbol)) {
        scanner_next(&parser->scanner);
    }
}

Read what it does: if the current symbol is acceptable, return. Otherwise report once, then skip forward until reaching a symbol somebody can continue from.

The set it skips to is the union of what this step expected and what the caller passed down as its follow set — the symbols that can legally come after whatever the caller is parsing. eofsym is always in the set, so the loop always terminates.

This is why every parsing routine in the compiler takes a follow parameter, and why they keep adding to it as they descend:

parser_condition(parser, level, follow | BIT(dosym));

“Parse a condition; if it goes wrong, you may also stop at do, because that is what I am going to look for next.”

The follow set is the parser telling its callee where the ground is. Threading it through every level is the entire cost of the technique, and the benefit is this:

printf 'const a := 1;\nvar x, x;\nbegin\n    y := 3 +;\n    call x\nend.\n' > /tmp/rec.pl0
../build/c/pl0 run /tmp/rec.pl0

1:9: error 1: a constant is declared with '=', not ':='
2:8: error 31: 'x' is already declared in this block
4:5: error 11: 'y' is not declared
4:13: error 24: a name, a number, or '(' was expected
5:10: error 15: 'x' is a variable, and only a procedure can be called
5 error(s)

Five mistakes in a six-line program, and five diagnostics — one per mistake, each at its own position, in source order. No cascade. That output is a regression test in both twins: if a change ever makes it six, the change is wrong.

Diagnostics are a feature

The error numbers are Wirth’s own, so a reader can look them up in the book. But the sentences are not his, and the difference is deliberate:

error 1: a constant is declared with '=', not ':='

rather than

error 1

A diagnostic that needs a lookup table is a diagnostic that goes unread. The number survives because it is part of PL/0’s literature; it travels with a sentence because a compiler’s error messages are the part of it that users actually experience.

Both twins ship a self-check for exactly this, which you can run:

../build/c/pl0 diagnostics | tail -3

code 9 a program without its period: ok
recovery: 5 diagnostics
diagnostics: 25 of 25

Twenty-five error cases, each a tiny program that provokes exactly one diagnostic, checked against the number the compiler must report. A compiler’s error table deserves tests as much as its code generator does — arguably more, because a wrong error message costs a user more time than a missing optimization.

Statements, and the shape of the whole

static void parser_statement(Parser* parser, int level, SymbolSet follow) {
    parser_descend(parser);

    switch (parser->scanner.symbol) {
    case ident:      parser_assignment(parser, level, follow);  break;
    case callsym:    parser_call(parser, level);                break;
    case ifsym:      parser_conditional(parser, level, follow); break;
    case whilesym:   parser_loop(parser, level, follow);        break;
    case beginsym:   parser_sequence(parser, level, follow);    break;
    default:                                                    break;
    }

    parser_expect(parser, follow, 0, 19, "this is not where a statement ends");
    parser->depth--;
}

One symbol of lookahead decides everything. That is what makes PL/0’s grammar LL(1), and it is why recursive descent fits it so exactly: each alternative begins with a distinct symbol, so the parser never has to guess and backtrack.

Note the default: break; — an empty statement is legal PL/0 (begin end is a valid program), so a symbol that begins nothing is not an error here. The parser_expect that follows catches it, with the right message and the right recovery set.

A whole control structure, start to finish

static void parser_loop(Parser* parser, int level, SymbolSet follow) {
    Label top = parser->backend->new_label(parser->backend);
    Label after = parser->backend->new_label(parser->backend);

    parser->backend->place_label(parser->backend, top);
    scanner_next(&parser->scanner);
    parser_condition(parser, level, follow | BIT(dosym));
    parser->backend->jump_if_false(parser->backend, after);

    if (parser->scanner.symbol == dosym) {
        scanner_next(&parser->scanner);
    } else {
        parser_error(parser, 18, "'do' was expected");
    }

    parser_statement(parser, level, follow);
    parser->backend->jump(parser->backend, top);
    parser->backend->place_label(parser->backend, after);
}

That is while c do s, complete. Two labels are reserved before anything is emitted, and one of them — after — is jumped to long before its position is known.

This is the classic problem of code generation: you must emit a jump to a place you have not generated yet. Wirth solved it by patching the address field of the jump after the fact — the backpatch, written out by hand twice in his statement procedure.

The seam here solves it by naming the target instead. new_label hands out an identity; place_label says where it landed; the back end reconciles them however it likes. The p-code back end backpatches, exactly as Wirth did. The Spectra back end does not have to: its representation has labels natively.

Look at what that bought. The parser no longer knows that a jump has an address field. That is one small interface decision, and it is the difference between a parser that can drive one machine and a parser that can drive any of them.

Next: 7 — The seam, which is that interface, in full, in two languages.

The grammar is the program#

Where precedence lives#

Emitting as you go#

The state a parse carries#

Error recovery: the actual hard part#

Diagnostics are a feature#

Statements, and the shape of the whole#

A whole control structure, start to finish#