Recursive descent calculator example

gistfile1.txt

// Had to cut some stuff out that distracted from the main point, so maybe it doesn't compile, but...
struct calculator {
  bool Succes;
  const char* Start;
  const char* FailAt;
  const char* Error;
  const char* C;

  real Compute(const char* ExprStr) {
    Succes = true;
    Start = ExprStr;
    C = Start;
    FailAt = 0;
    Error = 0;

    real Result = Expr();

    EatWhitespace();
    if (*C != '\0')
      Fail("Syntax error");
    return Result;
  }

  bool IsDigit(char C) {
    return (C >= '0') && (C <= '9');
  }

  bool IsAlpha(char C) {
    return (C >= 'a') && (C <= 'z');
  }

  int ToDigit(char C) {
    return C-'0';
  }

  void EatWhitespace() {
    while (*C == ' ' || *C == ' \t')
      C++;
  }

  void Fail(const char* Error) {
    if (Succes == true) {
      Succes = false;
      FailAt = C;
      this->Error = Error;
    }
  }

  real LiteralReal() {
    u64 Acc = 0;
    u64 Divisor = 1;

    while (IsDigit(*C)) {
      Acc *= 10;
      Acc += ToDigit(*C);
      C++;
    }
    if (*C == '.') {
      C++;
      while (IsDigit(*C)) {
        Acc *= 10;
        Acc += ToDigit(*C);
        Divisor *= 10;
        C++;
      }		
    }

    return ((real)Acc) / ((real)Divisor);
  }

  void MatchBeginParens() {
    if (*C == '(')
      C++;
    else
      Fail("Expected '('");
  }

  void MatchEndParens() {
    if (*C == ')')
      C++;
    else
      Fail("Expected ')'");
  }

  void MatchComma() {
    if (*C == ',')
      C++;
    else
      Fail("Expected ','");
  }

  bool MatchIdentifier(const char* Identifier) {
    int i = 0;

    while (1) {
      if (Identifier[i] == '\0') {
        C += i;
        return true;
      }
      else if (C[i] == Identifier[i]) {
        i++;
      }
      else {
        return false;
      }
    }

  }

  real MatchSingleArgument() {
    MatchBeginParens();
    EatWhitespace();
    real Argument = Expr();
    EatWhitespace();
    MatchEndParens();
    return Argument;
  }

  real MatchFirstArgument() {
    MatchBeginParens();
    EatWhitespace();
    real Argument = Expr();
    EatWhitespace();
    return Argument;
  }

  real MatchLastArgument() {
    MatchComma();
    EatWhitespace();
    real Argument = Expr();
    EatWhitespace();
    MatchEndParens();
    return Argument;
  }


  real FunctionCallOrConstant() {
    if (MatchIdentifier("abs")) return zabs(MatchSingleArgument());
    if (MatchIdentifier("sin")) return zsind(MatchSingleArgument());
    if (MatchIdentifier("cos")) return zcosd(MatchSingleArgument());
    if (MatchIdentifier("exp")) return zexpd(MatchSingleArgument());
    if (MatchIdentifier("step")) return (MatchFirstArgument() > MatchLastArgument()) ? 0.0 : 1.0 ;

    Fail("Unknown identifier");

    return 0.0;
  }

  real Factor() {
    real Value;

    EatWhitespace();

    if (*C == '(') {
      C++;
      Value = Expr();
      EatWhitespace();
      if (*C == ')')
        C++;
      else
        Fail("Expected ')'");
    }
    else if (*C == '+') {
      C++;
      Value = Factor();
    }
    else if (*C == '-') {
      C++;
      Value = -Factor();
    }
    else if (IsAlpha(*C)) {
      Value = FunctionCallOrConstant();
    }
    else if (IsDigit(*C) || *C == '.') {
      Value = LiteralReal();
    }
    else if (*C == '\0'){
      Fail("Unexpected EOF");
    }
    else {
      Fail("Syntax error");
    }

    return Value;
  }

  real Term() {
    real Value = Factor();
    EatWhitespace();

    while (*C == '*' || *C == '/') {
      if (*C == '*') {
        C++;
        Value *= Factor();
        EatWhitespace();
      }
      else if (*C == '/') {
        C++;
        Value /= Factor();
        EatWhitespace();
      }
    }

    return Value;
  }

  real Expr() {
    real Value = Term();
    EatWhitespace();

    while (*C == '+' || *C == '-') {
      if (*C == '+') {
        C++;
        Value += Term();
        EatWhitespace();
      }
      else if (*C == '-') {
        C++;
        Value -= Term();
        EatWhitespace();
      }
    }

    return Value;
  }
};

void AssertResult(calculator& Calculator, const char* Str, real Expected) {
  real Actual = Calculator.Compute(Str, NULL, 0, 0);
  if (Calculator.Succes == false || Actual != Expected)
    DebugBreak;
}

void AssertFail(calculator& Calculator, const char* Str, const char* ExpectedError) {
  real Actual = Calculator.Compute(Str, NULL, 0, 0);
  if (Calculator.Succes == true || !StringEqual(ExpectedError, Calculator.Error))
    DebugBreak;
}

void RunTests() {
  calculator Calculator;
  AssertResult(Calculator, "1", 1.0);
  AssertResult(Calculator, "123", 123.0);
  AssertResult(Calculator, "   50  ", 50.0);
  AssertResult(Calculator, "1.5", 1.5);
  AssertResult(Calculator, ".25", 0.25);
  AssertResult(Calculator, "199.", 199.0);
  AssertResult(Calculator, "199.25", 199.25);
  AssertResult(Calculator, "  + + + 1", 1.0);
  AssertResult(Calculator, "  + - + 1", -1.0);
  AssertResult(Calculator, "  ---1", -1.0);
  AssertFail(Calculator, " ", "Unexpected EOF");
  AssertFail(Calculator, "1 q", "Syntax error");
  AssertResult(Calculator, " 2 * 3", 6.0);
  AssertResult(Calculator, " -2 * -3", 6.0);
  AssertResult(Calculator, " 2 * -3", -6.0);
  AssertResult(Calculator, " 2 * -3 * -4", 24.0);
  AssertResult(Calculator, " 1.5 * 1.5", 2.25);
  AssertResult(Calculator, " 24 / 4 / 3", 2.0);
  AssertResult(Calculator, " 24 / 4 * 3.5", 21.0);
  AssertResult(Calculator, "1+2", 3.0);
  AssertResult(Calculator, "6-3-2", 1.0);
  AssertResult(Calculator, "3*4+7", 19.0);
  AssertResult(Calculator, "3+4*7", 31.0);
  AssertResult(Calculator, "3*(4+7)", 33.0);
  AssertResult(Calculator, " ( 3 +  4 ) * 7 ", 49.0);
  AssertResult(Calculator, "(3+4)*7", 49.0);
  AssertResult(Calculator, "(1)", 1.0);
  AssertFail(Calculator, "(1", "Expected ')'");
  AssertFail(Calculator, "(1+2", "Expected ')'");
  AssertFail(Calculator, "(1+(3*4)", "Expected ')'");
  AssertFail(Calculator, "()", "Syntax error");
  AssertResult(Calculator, "abs(-1)", 1.0);
  AssertFail(Calculator, "abs -1", "Expected '('");
  AssertFail(Calculator, "abs(-1", "Expected ')'");
  AssertFail(Calculator, "", "Unexpected EOF");
  AssertFail(Calculator, "aslasla(1)", "Unknown identifier");
  AssertResult(Calculator, "step(-1, -2)", 0.0);
  AssertResult(Calculator, "step(-1, 0)", 1.0);
  AssertResult(Calculator, "step(-1, -1)", 1.0);
  AssertFail(Calculator, "step(1)", "Expected ','");
}