//
// Example of recursive-descent parsing, version 2
//
// In this second version, we blend evaluation with recognition.
//
// The language of expressions is described by the following CFG:
//
// E -> E + T | E - T | T
// T -> T * F | T / F | F
// F -> D | ( E )
// D -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
//
// In the above rules, E is the start symbol.  Think of E as "expression",
// T as "term", F as "factor" and D as "digit."
//

#include <iostream>
#include <cctype>
#include <string>

using namespace std;

// prototypes for parsing routines

void E(int & result);
void T(int & result);
void F(int & result);
void D(int & result);
void Error();
void Match(char ch);
void Parse(int & result);

// global objects used by the parsing routines

const char EndOfString = '~';
string s;
int LookAheadIndex;
char LookAhead;
bool ErrorDetected;
int ErrorIndex;
int ExpressionValue;


int main() {
  cout << "Arithmetic expression parser" << endl;
  cout << "----------------------------" << endl << endl;

  string Prompt = "> ";
  cout << Prompt;
  while (getline(cin, s, '\n')) {
    // Echo the string
    cout << s << endl;

    // Append the end-of-string marker to the string
    s += EndOfString;

    Parse(ExpressionValue);
    if (!ErrorDetected)
      cout << "OK, value is: " << ExpressionValue << endl;
    else {
      // Indicate syntax error by placing caret at problem area
      for (int i = 0; i < ErrorIndex - 1; i++)
	cout << " ";
      cout << "^ Syntax error." << endl;
    }

    // Prompt for the next expression
    cout << Prompt;
  } 
}


void E(int & result) {

  int temp;   // used to save the value of a subexpression

  T(result);
  while ((LookAhead == '+') || (LookAhead == '-'))
    if (LookAhead == '+') {
      Match('+');
      T(temp);
      if (!ErrorDetected)
	result += temp;
    }
    else if (LookAhead == '-') {
      Match('-');
      T(temp);
      if (!ErrorDetected)
	result -= temp;
    }
}


void T(int & result) {

  int temp;    // used to save the value of a subexpression

  F(result);  
  while ((LookAhead == '*') || (LookAhead == '/'))
    if (LookAhead == '*') {
      Match('*');
      F(temp);
      if (!ErrorDetected)
	result *= temp;
    }
    else if (LookAhead == '/') {
      Match('/');
      F(temp);
      if (!ErrorDetected)
	result /= temp;
    }
}


void F(int & result) {
  if (isdigit(LookAhead))
    D(result);
  else if (LookAhead == '(') {
    Match('(');
    E(result);
    Match(')');
  }
  else
    Error();
}


void D(int & result) {
  if (isdigit(LookAhead)) {
    result = LookAhead - '0';
    Match(LookAhead);
  }
  else
    Error();
}


void Error() {
  if (!ErrorDetected) {
    ErrorDetected = true;         // ignore future syntax errors
    ErrorIndex = LookAheadIndex;  // save error position
    LookAhead = EndOfString;      // used for synchronizing
  }
}


void Match(char ch) {
  if (LookAhead == ch) {
    // get the next token, skipping over "white space"
    do {
      LookAheadIndex++;
    } while (s[LookAheadIndex] == ' ');
    LookAhead = s[LookAheadIndex];
  }
  else
    Error();
}


void Parse(int & result) {
  // Initially, we know of no syntax errors
  ErrorDetected = false;

  // Get the first token, skipping over "white space"
  LookAheadIndex = 0;
  while (s[LookAheadIndex] == ' ')
    LookAheadIndex++;

  // Save the first token
  LookAhead = s[LookAheadIndex];

  // Now parse the string, trying to find an arithmetic expression
  E(result);
  
  // Was the entire string consumed?
  Match(EndOfString);
}

/*
Sample Output:

Arithmetic expression parser
----------------------------

> 2 + 3
2 + 3
OK, value is: 5
> 2 + 3 * 4
2 + 3 * 4
OK, value is: 14
> ((2 + 3) * 4 + 5 * 6) * 2
((2 + 3) * 4 + 5 * 6) * 2
OK, value is: 100
> 2 + 3 * 4 +
2 + 3 * 4 +
          ^ Syntax error.      
*/