writing about pratt parsing so I remember it

shunting yard

the shunting yard algorithm is, comparatively, much simpler than pratt. you have an output stream and an operator stack. operators are defined with their binding powers, where higher binding power means it binds tighter to its arguments (e.g. * has higher binding power in arithmetic than +). in the simplest description of shunting yard, for every token in the input stream:

• if it’s a “standalone” token (i.e. identifier/number), just push it to the output
• if it’s an operator token:
  • if it’s of higher binding power than the top of the operator stack, push it to the stack
  • if it’s of equal of lower binding power than the top of the operator stack, then pop all operator tokens of higher or equal binding power to the output stream before pushing the operator token to the operator stack
    • popping all “higher or equal binding power” operators assumes that all operators are left-associative
• at the end of the token stream, pop all remaining operators to the output.

a very primitive shunting yard in C, where expressions are converted to postfix notation, could be:

#include <stdio.h>
#include <ctype.h>

typedef struct {
    char ops[32]; // limit of 32 operators
    int idx; // index of last operator
} Stk;

void push(Stk *s, char op) {
    s->idx += 1;
    s->ops[s->idx] = op;
}
void pop(Stk *s)   { s->idx -= 1; }
char peek(Stk *s)  { return s->ops[s->idx]; }
char empty(Stk *s) { return s->idx == -1; }

int get_bindpower(char op) {
    static const int bps[] = { ['+'] = 1, ['-'] = 1, ['*'] = 2, ['/'] = 2 };
    return bps[op];
}

int main(int argc, char **argv) {
    char *str = argv[1];
    Stk _opstk = (Stk){ .idx = -1 };
    Stk *opstk = &_opstk;

    while (*str != '\0') {
        if (isdigit(*str)) {
            // number
            printf("EMIT '%c'\n", *str);
        } else {
            // operator (assumed valid)
            // get_bindpower(peek(opstk)) is the left binding power
            // get_bindpower(*str) is the right binding power
            while (!empty(opstk) && get_bindpower(peek(opstk)) >= get_bindpower(*str)) {
                printf("EMIT '%c'\n", peek(opstk));
                pop(opstk);
            }
            push(opstk, *str);
        }
        str += 1;
    }

    while (!empty(opstk)) {
        printf("EMIT '%c'\n", peek(opstk));
        pop(opstk);
    }

    return 0;
}

$ ./a.out '1+5*2+6'
EMIT '1'
EMIT '5'
EMIT '2'
EMIT '*'
EMIT '+'
EMIT '6'
EMIT '+'

the problem with shunting yard is that it’s not very extensible to new behavior. for example, the algorithm has no concept of “subexpressions” in the recursive sense; adding parentheses means attaching special functionality to the ) token for popping off the stack until reaching the matching (. that’s not hard in its own right, but more complex behavior like unary operators, right-associative expressions, functions with variable arguments, etc. will get messy. this is where the transformation to pratt parsing comes in.

from shunting to pratt

the core realization to turn shunting yard into pratt is, instead of using an explicit stack for operator precedence, using the call stack to implicitly be inside of subexpressions as we need them. unlike recursive descent, you don’t nest calls through every level of precedence for every expression, but rather only nest and return when entering subexpressions.

unfortunately, there’s no clean “intermediate” step for this. you kind of just have to thrust it all through the wringer and look at the output. here’s the simplest pratt-style parser I can show in c, equivalent to the shunting yard parser before:

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

int get_bindpower(char op) {
    // the end token ('\0') is now defined in the bind power array
    static const int bps[] = {
        ['\0'] = 0,
        ['+'] = 1, ['-'] = 1, ['*'] = 2, ['/'] = 2
    };
    return bps[op];
}

typedef struct {
    char *str;
} Parser;

char cur(Parser *p) { return *p->str; }
void bump(Parser *p) { p->str += 1; }

void
expr(Parser *parser, int left_bindpower) {
    // all expressions *must* start with a number (or "prefix" token)
    if (isdigit(cur(parser))) {
        printf("EMIT '%c'\n", cur(parser));
    } else {
        puts("expression doesn't start with a number");
        abort();
    }
    bump(parser);

    // at this point, we're at an infix (or postfix) operator.
    // when this check is false, it's equivalent to "unwinding" the stack in shunting yard.
    while (left_bindpower < get_bindpower(cur(parser))) {
        // assumed to be valid operator (like the shunting yard code)

        // there's an expression on the right side of binary operators. parse it first.
        // this is the equivalent of pushing to the operator stack in shunting yard.
        int new_left_bindpower = get_bindpower(cur(parser));
        char op = cur(parser);
        bump(parser);
        expr(parser, new_left_bindpower);

        printf("EMIT '%c'\n", op);
    }
}

int main(int argc, char **argv) {
    Parser parser = (Parser){ .str = argv[1] };

    expr(&parser, 0);

    return 0;
}

$ ./a.out '1+5*2+6'
EMIT '1'
EMIT '5'
EMIT '2'
EMIT '*'
EMIT '+'
EMIT '6'
EMIT '+'

on its own, this doesn’t look too exciting. I made the stack implicit. big whuff. but! there are two neat things here:

• “prefix” operators have first-class handling now
• we have the power to assign arbitrary code to any individual operator as soon as the operator is seen, just like recursive descent.

these combined allow for simple & straightforward extensibility. here’s all it takes to add parentheses into the mix:

int get_bindpower(char op) {
    // add '(' to bps
    static const int bps[] = {
        ['\0'] = 0,
        ['('] = 0,
        ['+'] = 1, ['-'] = 1, ['*'] = 2, ['/'] = 2
    };
    return bps[op];
}

// ...

// forward-declare expr() and add paren() subroutine.
// this doesn't even need to be a subroutine; you can inline this in the expr() func.
// but this is cleaner :)
void expr(Parser *parser, int left_bindpower);

void paren(Parser *parser) {
    expr(parser, get_bindpower('('));
    if (cur(parser) != ')') {
        puts("no matching ')'");
        abort();
    }
}

// ...

// add the if '(' conditional here; rest is same
void
expr(Parser *parser, int left_bindpower) {
    if (cur(parser) == '(') {
        bump(parser);
        paren(parser);
    } else if (isdigit(cur(parser))) {
        printf("EMIT '%c'\n", cur(parser));
    } else {
        puts("expression doesn't start with a valid prefix token");
        abort();
    }
    // ...
}

$ ./a.out '1+5*(2+6)'
EMIT '1'
EMIT '5'
EMIT '2'
EMIT '6'
EMIT '+'
EMIT '*'
EMIT '+'

want to add even more operators? coalesce the get_bindpower() function with choosing the subroutine to run, storing “rules” as a struct of the binding power, prefix subroutine, and postfix subroutine. the core stays simple while all the operators run in their own little functions! I’m not going to paste another blob of code here, but that setup is described in the crafting interpreters chapter. it’s so elegant!

hope this helps anyone else. happy parsing :)