TinyExpressionParser.cpp

#include <assert.h>
#include <stdint.h>
#include <vector>
#include <setjmp.h>
#include <stdio.h>

typedef char token_e;

namespace {
// return the precedence of an operator
int op_prec(token_e o) {
    switch (o) {
    case ('&'): return  1;
    case ('+'):
    case ('-'): return  2;
    case ('*'):
    case ('/'): return  3;
    default:    return  0;
    }
}

// return true if token is an operator
bool is_op(token_e o) {
    return op_prec(o) != 0;
}

// return true if token is a variable identifier
bool is_var(token_e o) {
    return (o>='A' && o<='Z') || (o>='a' && o<='z');
}

// return true if token is a numeric literal
bool is_num(token_e o) {
    return (o>='0' && o<='9');
}
} // namespace {}

struct parser_t {

    std::vector<token_e> op_;
    const char * s_;
    jmp_buf error_buf;

    void error() {
        longjmp (error_buf, 1);
    }

    parser_t(const char * stream)
        : op_()
        , s_(stream)
    {}

    char found_op () { return (is_op  (*s_)) ? *(s_++) : 0; }
    char found_var() { return (is_var (*s_)) ? *(s_++) : 0; }
    char found_num() { return (is_num (*s_)) ? *(s_++) : 0; }

    // check for specific token in the token stream
    bool found(char ch) {
        if (*s_ == ch) {
            s_++;
            return true;
        }
        return false;
    }

    // unconditionally expect a token in the token stream
    void expect(char ch) {
        if (*(s_++) != ch) {
            printf ("\nexpected '%c'\n", ch);
            error ();
        }
    }

    // ---- ---- ---- ---- ---- ---- ---- ---- <expression parser>

    void pop_op() {
        assert(op_.size() > 0);
        token_e t = op_.back();
        putchar (t);
        op_.pop_back();
    }

    void push_op(uint32_t tide, token_e tok) {
        while (op_.size() > tide) {
            if (op_prec (op_.back ()) > op_prec (tok))
                pop_op ();
            else
                break;
        }
        op_.push_back(tok);
    }

    void pop_all_op(uint32_t tide) {
        while (op_.size() > tide)
            pop_op();
    }

    void parse_lhs(uint32_t tide) {
        // parenthesis
        if (found('(')) {
            parse_expr ();
            expect (')');
        }
        // identifier
        else if (char var = found_var()) {
            // identifier name
            putchar (var);
            // index an object
            while (found('.')) {
                if (char ix = found_var()) {
                    putchar (ix);
                    putchar ('@');
                }
                else {
                    printf ("\nexpecting identifier, got '%c'\n", *s_);
                    error ();
                }
            }
            // function call
            if (found('(')) {
                //
                uint32_t num_args = 0;
                // argument list
                if (!found(')')) {
                    do {
                        ++num_args;
                        parse_expr();
                    } while (found(','));
                    expect (')');
                }
                // call instruction
                printf("<%d>",-num_args);
            }
        }
        // numeric literal
        else if (char num = found_num()) {
            putchar (num);
        }
        // unexpected token
        else {
            printf ("\nunexpected token '%c'\n", *s_);
            error ();
        }
    }

    // parse an expression with extended control
    void parse_expr_ex(uint32_t tide) {
        bool unary_not = found ('!');
        parse_lhs(tide);
        if (unary_not) {
            // logical not instruction
            putchar('!');
        }
        if (char op = found_op()) {
            push_op (tide, op);
            parse_expr_ex(tide);
        }
    }

    // parse a full expression
    void parse_expr() {
        uint32_t tide = op_.size();
        parse_expr_ex(tide);
        pop_all_op(tide);
    }

    // ---- ---- ---- ---- ---- ---- ---- ---- </expression parser>

    // parse root
    void parse() {
        if (!setjmp(error_buf)) {
            parse_expr ();
        } else {
            printf ("unable to parse\n");
        }
    }
};

// supported operators:
//      &       and
//      + -     add sub
//      * /     mul div
//      !       unary not
// example input:
//      A+B*C*(0-3)
//      A&!B
//      2+A(B,C+1)
int main() {
    char buffer[1024];
    // little REPL loop
    for (;;) {
        printf ("expr: ");
        fgets(buffer, sizeof(buffer), stdin);
        if (buffer[0] == '\0')
            break;
        parser_t parser(buffer);
        printf ("post: ");
        parser.parse();
        printf ("\n\n");
    }
    return 0;
}