Shunting Yard

/************
 * collapse *
 ************/

/* shunting yard helper */

int
collapse(struct vector *outq, struct vector *opq, struct exp **res)
{
    struct exp *left, *right;
    struct binop *infix;
    enum op_type op;

    op = (enum op_type)vec_pop(opq);
    left = (struct exp *)vec_pop(outq);
    right = (struct exp *)vec_pop(outq);
    infix = binop_alloc(op, left, right);
    *res = exp_alloc(E_BINOP, infix);
    return 0;
}

/*********
 * shunt *
 *********/

/* implementation of the shunting-yard infix parser algorithm */

int
shunt(struct lexer *lex, struct token *tok, struct exp **res)
{
    struct vector *outq, *opq;
    struct exp *acc;
    struct bind_power cur_bp, prev_bp;
    int status;

    outq = vec_alloc(2, (void (*)(void *))exp_free);
    opq = vec_alloc(2, 0);

    while (1) {

        scan(lex, tok);

        /* the token is delimiting the end of an expression */

        if (exp_follow(tok->type))
            break;

        /* the token is an operator */

        if (is_infix(tok->type)) {
            cur_bp = bind_table[tok->type];
            prev_bp = bind_table[vec_peek(opq)];

            while (!vec_empty(opq) && cur_bp.left <= prev_bp.left) {
                status = collapse(outq, opq, &acc);
                vec_push(outq, (uintptr_t)acc);
            }

            vec_push(opq, (enum op_type)tok->type);
            continue;
        }

        /* the token is delimiting the beginning of an atomic expression */

        status = expr_at(lex, tok, &acc);

        if (status < 0)
            goto shunt_cleanup;

        vec_push(outq, (uintptr_t)acc);

        // no other case
    }

    /* pick up rest of outq */

    while (!vec_empty(opq)) {
        status = collapse(outq, opq, &acc);
        vec_push(outq, (uintptr_t)acc);
    }

    /* ASSERT OUTQ HAS LEN 1 */

    acc = (struct exp *)vec_pop(outq);
    *res = acc;

shunt_cleanup:

    vec_free(outq);
    vec_free(opq);

    return 0;
}