//
// Example of recursive-descent parsing, version 1
//
// In this first version, we focus on the recognition of an expression.
//
// 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();
void T();
void F();
void D();
void Error();
void Match(char ch);
void Parse();

// global objects used by the parsing routines

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


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();
    if (!ErrorDetected)
      cout << "OK." << 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() {
  T();
  while ((LookAhead == '+') || (LookAhead == '-'))
    if (LookAhead == '+') {
      Match('+');
      T();
    }
    else if (LookAhead == '-') {
      Match('-');
      T();
    }
}


void T() {
  F();  
  while ((LookAhead == '*') || (LookAhead == '/'))
    if (LookAhead == '*') {
      Match('*');
      F();
    }
    else if (LookAhead == '/') {
      Match('/');
      F();
    }
}


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


void D() {
  if (isdigit(LookAhead))
    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() {
  // 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();
  
  // Was the entire string consumed?
  Match(EndOfString);
}

/*
Sample Output:

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

> 2 + 3
2 + 3
OK.
> 2 + 3 * 4
2 + 3 * 4
OK.
> ((2 + 3) * 4 + 5 * 6) * 2
((2 + 3) * 4 + 5 * 6) * 2
OK.
> 2 + 3 * 4 +
2 + 3 * 4 +
          ^ Syntax error.
> ((2 + 3 * 4)
((2 + 3 * 4)
           ^ Syntax error.        
*/