Top Down Operator Precedence - Douglas Crockford's Javascript

recursive-descent.cc

#include <iostream>
#include <assert.h>

const char* code = "-1+2*3";
const char* token = nullptr;

void init() {
  token = code;
}

void advance() {
  assert(*token);
  token++;
}

enum Op {
  kOpInvalid,
  kOpAdd,
  kOpSub,
  kOpMul,
  kOpMinus,
};

Op get_unop(char t) {
  switch (t) {
    case '-': return kOpMinus;
    default: return kOpInvalid;
  }
}

Op get_binop(char t) {
  switch (t) {
    case '+': return kOpAdd;
    case '-': return kOpSub;
    case '*': return kOpMul;
    default: return kOpInvalid;
  }
}

struct Node {
};

struct Binary {
  char op;
  char left;
  char right;
};

struct Unary {
  char op;
  char right;
};

int get_lbp(char token) {
  if (token == '+' || token == '-') return 5;
  return 6;
}

int get_rbp(char token) {
  if (token == '+' || token == '-') return 5;
  return 6;
}

int expr(int rbp) {
  // std::cout << "enter expr " << rbp << std::endl;
  int left = 0, right = 0;
  Op op = get_unop(*token);
  if (op != kOpInvalid) {
    advance();
    left = expr(10);
    left = left * -1;
    std::cout << "NEG " << std::endl;
  } else {
    assert(*token);
    std::cout << "PUSH " << *token << std::endl;
    left = *token - '0';
    advance();
  }

  if (*token) {
    op = get_binop(*token);
    int lbp = get_lbp(*token);
    // std::cout << *token << "==" << lbp << std::endl;
    while (op != kOpInvalid && lbp > rbp) {
      int rbp2 = get_rbp(*token);
      assert(*token);
      advance();
      // std::cout << left << std::endl;
      right = expr(rbp2);
      switch (op) {
        case kOpAdd: std::cout << "ADD" << std::endl; left = left + right; break;
        case kOpSub: std::cout << "SUB" << std::endl; left = left - right; break;
        case kOpMul: std::cout << "MUL" << std::endl; left = left * right; break;
        default:
          assert(0&&"Error");
      }
      if (*token) {
        op = get_binop(*token);
        lbp = get_lbp(*token);
      } else {
        break;
      }
    }
  }
  return left;
}

int main(int argc, char** argv) {
  init();
  std::cout << expr(0);
  return 0;
}