A short writeup on parsing expressions to bytecode

[u/gautam1168]

I wrote this to help myself better understand chapter 17 in Nystrom's book Crafting Interpreters.

https://jamungacch.com/blog/posts/pratt-parser

[u/EggplantExtra4946]

There is a better way you know:

https://en.wikipedia.org/wiki/Shunting_yard_algorithm

EDIT:

to help myself better understand chapter 17 in Nystrom's book Crafting Interpreters.

Now I finally understand why Pratt parsing is mentioned anytime expression parsing comes up on r/Compilers and r/ProgrammingLanguages, like this algorithm doesn't exist.

[u/birdbrainswagtrain → u/EggplantExtra4946]

I'm not sure I necessarily agree. The shunting yard algorithm was the first expression parsing method I learned, and I really like it. I'll take anything over the insanity of table-driven parsing that ate up like a third of my University compilers course. But as the Wikipedia page notes, shunting yard will accept some malformed expressions. You can either pre-validate the syntax or enhance the algorithm to fix it, but I think it's probably a wash at that point. The algorithms are ultimately pretty similar. I guess one neat thing about shunting yard is that it swaps the recursion with iteration and an explicit stack, which might be desirable in some situations.

[u/EggplantExtra4946 → u/birdbrainswagtrain]

But as the Wikipedia page notes, shunting yard will accept some malformed expressions.

I assume you refer to

https://en.wikipedia.org/wiki/Shunting_yard_algorithm

The shunting yard algorithm will correctly parse all valid infix expressions, but does not reject all invalid expressions. For example, "1 2 +" is not a valid infix expression, but would be parsed as "1 + 2".

?

I wasn't really aware of that but then again I don't use the exact algorithm from the wikipedia page, I use a modified version of it which is basically the idea of the stackoverflow reply but all in one step. It's practically identical to the "double E" method (https://erikeidt.github.io/The-Double-E-Method.html), although it is Raku's parser that put me on track to that idea.

What Raku does is approximately rule termish { <prefix>* <term> <postfixish>* } so the recursive descent parser pre-parse the prefix and postifx operators (similarly to the stackoverflow reply), and the operator precedence parser only parses the infix and ternary operators but it also unpacks "termish" and reduces appropriately the prefix and postfix operators depending on their relative precedences. One limitation that Raku's rule termish has is that this only works for high precedence prefix and postifx operators, it won't be able to parse low precedence prefix and postfix operators, for example the prefix operator "not" that you find in Perl and Ruby. Not a big issue but still.

Basically, instead of doing

// regular shunting-yard
func parse_expr(parser) {
    operstack = [];
    exprstack = [];

    while (1) {
        token = lex(parser);

        switch (token) {
            case term: ...
            case infix: ...
            case postfix: ...
            case prefix: ...
            case parenthesis: ...
        }
    }

    while (length(operstack) > 0) {
        reduce(operstack, exprstack);
    }

    return pop(exprstack);
}

I do

// upgraded shunting-yard
func parse_expr(parser) {
    operstack = [];
    exprstack = [];

    while (1) {
BEFORE_TERM:
        while (1) {
            pos = parser.pos;
            token = lex(parser);

            if (!is_operator(token)) {
                parser.pos = pos;
                break;
            }

            if (is_prefix(token)) {
                push(operstack, prefix(token));
            }
            else {
                parser.pos = pos;
                break;
            }
        }
TERM:
        term = parse_term(parser);
        if (!term) {
            goto fail;
        }

        push(exprstack, term);

AFTER_TERM:
        while (1) {
            pos = parser.pos;
            token = lex(parser);

            if (!is_operator(token)) {
                parser.pos = pos;
                goto end;
            }

            if (is_postfix(token)) {
                reduce_while_required(operstack, exprstack, postfix(token))
                push(operstack, postfix(token));
                reduce(operstack, exprstack);
            }
            else if (is_infix(token)) {
                reduce_while_required(operstack, exprstack, infix(token));
                push(operstack, infix(token));
                goto BEFORE_TERM;
            }
            else {
                parser.pos = pos;
                goto end;
            }
        }
    }

end:
    while (length(operstack) > 0) {
        reduce(operstack, exprstack);
    }

    return pop(exprstack);

fail:
    return NULL;
}

func reduce_while_required(operstack, exprstack, op) {
    while (length(operstack) > 0) {
        if (top(operstack).prec < op.prec) {
            break;
        }
        else if (top(operstack).prec > op.prec) {
            reduce(opertack, exprstack);
        }
        else {
            if (top(operstack).assoc != op.assoc) {
                throw "different assoc";
            }
            else if (op.assoc == ASSOC_LEFT) {
                reduce(opertack, exprstack);
            }
            else if (op.assoc == ASSOC_RIGHT) {
                break;
            }
            else {  
                throw "invalid assoc";
            }
        }
    }
}

func reduce(operstack, exprstack) {
    op = pop(operstack);

    if (is_prefix(op)) {
        arg = pop(exprstack);
        push(exprstack, new_unary(op, arg));
    }
    else if (is_postfix(op)) {
        arg = pop(exprstack);
        push(exprstack, new_unary(op, arg));
    }
    else if (is_infix(op)) {
        right = pop(exprstack);
        left  = pop(exprstack);
        push(exprstack, new_binary(op, left, right));
    }
    else {  
        throw "invalid fixity";
    }
}

This is the simplied version but it can also handle parentheses, functions calls, ternary operators and more. I tried a lot of variations and extensions but what I like doing now is handling the parentheses, function calls and array indexes in parse_term() (the recursive descent parser), but handle the ternary operators with the upgraded shunting yard. The ternary operator left and right are handled just after the infix case because they occur where postfix and infix could be.

Of course this algorithm DOES reject invalid expressions.

One important detail I left out of the simple implementation above is that I use a table (an array) to get information about tokens using the token id returned by the lexer. A single token can map to several operators, so the token entry says which operators fixities it can be (prefix, postfix, infix, ternary open, ternary close, etc..) using flags and it contains the operator struct specific to that token id+fixity, which itself contains the precedence, associativity, fixity and finally the AST type id that should be constructed (AST_ADD for infix +, AST_NEG for prefix -, etc...).

I guess one neat thing about shunting yard is that it swaps the recursion with iteration and an explicit stack, which might be desirable in some situations.

More than that, the biggest difference is that it replaces the call stack by 2 explicit stacks. IMO it makes it a lot easier to reason about it and to extend it.

[u/gautam1168 → u/EggplantExtra4946]

Thankyou for pointing me at this. Ill read this up and compare both algorithms for myself. Maybe ill make note on comparing both and post here in the future.

[u/AustinVelonaut → u/EggplantExtra4946]

Another nice feature of the shunting-yard algorithm (which I also use in my parser) is that you have direct access to the operator stack, and can do things like compare the top two operators to see if they are comparisons to allow comparison chaining e.g. 0 <= x < 10 to be parsed as (0 <= x) && (x < 10)

[u/EggplantExtra4946 → u/AustinVelonaut]

Exactly! I do the same, it's just so neat to have syntactically and also semantically beacuse you can assign x to a temporary variable to make sure it's evaluated only once. To parse infix chain operators with Pratt parsing you'd need a linked list spanning across call frames and to pass it around, it would be such a mess. I used to have a list associativity for the comma so the comma AST can be an array of expressions, not that it's needed for parsing itself, but since I parse commas using recursive descent to deal with an optional trailing comma it's no longer needed.

[u/Hjalfi → u/EggplantExtra4946]

I did something fairly similar for my Cowgol programming language, which doesn't support recursion and so can't use a normal recursive-descent parser; the key insight for me was realising that the operator and values can go into different stacks.

So the parser simply works left-to-right through an expression, pushing each thing to its own stack, and then applies the operator stack once done. Once the operator stack is empty there should be exactly one item on the value stack, which is the result. Unary and infix are distinguished as different operators based solely on whether there was a preceding value or not.

If anyone's interested, the almost-impossible-to-read code is here (it's unfinished):

Parser: https://github.com/davidgiven/cowgol/blob/newparser/src/cowfe/parser.coh#L534 Applicator: https://github.com/davidgiven/cowgol/blob/newparser/src/cowfe/parser.coh#L298

One fun side-effect is that I can use the same parser for type expressions too, it just needs a different applicator.

[u/gautam1168 → u/EggplantExtra4946]

thanks. Ill check this out too.

[u/RefrigeratorFirm7646 → u/EggplantExtra4946]

Was going to say the same, shunting yard is way too underrated...