#include <fstream>
#include <iostream>
#include <sstream>
#include <stdio.h>
#include <string>
#include "Parser.h"
#include "PKB.h"
#include "TNode.h"

using namespace std;

bool Parser::hasAddedFirstProcedure;
string Parser::currentProcedure;
vector<string> Parser::varTable;
vector<string> Parser::procTable;
vector<string> Parser::statementTable;
vector<string> Parser::statementType;
vector<int> Parser::parentStack;
vector<pair<string, string>> Parser::followTable;
vector<pair<string, string>> Parser::parentTable;
map<string, string> Parser::usesRelationshipMap;
map<string, string> Parser::modifiesRelationshipMap;
map<string, vector<string>> Parser::assignPatternMap;
map<string, vector<int>> Parser::procedureStatementsMap;
map<string, vector<string>> Parser::procedureSequenceMap;
map<Parser::Symbol, string> Parser::symbolToStringMap;

Parser::Parser() {
    hasAddedFirstProcedure = false;
    currentProcedure = "";
    symbolToStringMap[leftParenthesis] = "(";
    symbolToStringMap[rightParenthesis] = ")";
    symbolToStringMap[leftCurlyBracket] = "{";
    symbolToStringMap[rightCurlyBracket] = "}";
    symbolToStringMap[timesSymbol] = "*";
    symbolToStringMap[divideSymbol] = "/";
    symbolToStringMap[plusSymbol] = "+";
    symbolToStringMap[minusSymbol] = "-";
    symbolToStringMap[moduloSymbol] = "%";
    symbolToStringMap[equalToSymbol] = "==";
    symbolToStringMap[notEqualToSymbol] = "!=";
    symbolToStringMap[greaterThanSymbol] = ">";
    symbolToStringMap[greaterThanEqualToSymbol] = ">=";
    symbolToStringMap[lessThanSymbol] = "<";
    symbolToStringMap[lessThanEqualToSymbol] = "<=";
    symbolToStringMap[semiColon] = ";";
    symbolToStringMap[comma] = ",";
    symbolToStringMap[whileSymbol] = "while";
    symbolToStringMap[ifSymbol] = "if";
    symbolToStringMap[thenSymbol] = "then";
    symbolToStringMap[elseSymbol] = "else";
    symbolToStringMap[procedureSymbol] = "procedure";
    symbolToStringMap[callSymbol] = "call";
    symbolToStringMap[readSymbol] = "read";
    symbolToStringMap[printSymbol] = "print";
    symbolToStringMap[assignSymbol] = "=";
    symbolToStringMap[notConditionSymbol] = "!";
    symbolToStringMap[andConditionSymbol] = "&&";
    symbolToStringMap[orConditionSymbol] = "||";
}

// Description: Function opens a file named "filename" and process the information inside
// Parameters:
// - filename: a non-empty string containing the location of the file
// Return:
// - string with the contents of the file
string Parser::getInformationFromFile(string filename) {
    string contents;
    ifstream inFile(filename);

    if (inFile) {
        ostringstream ss;
        ss << inFile.rdbuf();
        contents = ss.str();
        inFile.close();
    }
    return contents;
}

// Description: Function takes in a string, and remove any leading whitespace, tab, and newline
// Parameters:
// - inputString: a non-empty string
// Return:
// - string with no leading spaces (whitespace, tab, newline)
string Parser::removeLeadingSpacesFromString(string inputString) {
    string resultString = inputString;
    string spaceDelimiter = " ";
    string tabDelimiter = "\t";
    string newLineDelimiter = "\n";
    size_t position;

    do {
        position = resultString.find(spaceDelimiter);
        if (position != 0) {
            position = resultString.find(tabDelimiter);
            if (position != 0) {
                position = resultString.find(newLineDelimiter);
                if (position != 0) {
                    return resultString;
                }
                else {
                    resultString.erase(0, newLineDelimiter.length());
                }
            }
            else {
                resultString.erase(0, tabDelimiter.length());
            }
        }
        else {
            resultString.erase(0, spaceDelimiter.length());
        }
    } while (position == 0);
}

// Description: Function takes in a string, and remove any trailing whitespace, tab, and newline
// Parameters:
// - inputString: a non-empty string
// Return:
// - string with no trailing spaces (whitespace, tab)
string Parser::removeTrailingSpacesFromString(string inputString) {
    string lastCharacterString;
    string spaceDelimiter = " ";
    string tabDelimiter = "\t";
    size_t spacePosition;
    size_t tabPosition;

    lastCharacterString = inputString[inputString.length() - 1];

    while (lastCharacterString == spaceDelimiter || lastCharacterString == tabDelimiter) {
        lastCharacterString = inputString[inputString.length() - 1];
        if (lastCharacterString == spaceDelimiter) {
            inputString = inputString.substr(0, inputString.length() - 1);
        }
        else if (lastCharacterString == tabDelimiter) {
            inputString = inputString.substr(0, inputString.length() - 1);
        }
    }
    return inputString;
}

// Description: Function checks if an input string of file contents is a valid SIMPLE program
// Concrete Syntax Grammar Rule:
// program: procedure+
// Parameters:
// - contents: a non-empty string containing the file contents
// Return:
// - true if the file contents is a valid SIMPLE program
// - false if the file contents is an invalid SIMPLE program
bool Parser::program(string contents) {
    while (contents != "INVALID" && expect(procedureSymbol, contents)) {
        contents = procedure(contents);
    }

    if (contents == "INVALID") {
        return false;
    }

    // Check for non-existing procedure calls
    for (map<string, vector<string>>::iterator it = procedureSequenceMap.begin(); it != procedureSequenceMap.end(); it++) {
        for (int i = 0; i < it->second.size(); i++) {
            if (find(procTable.begin(), procTable.end(), it->second[i]) == procTable.end()) {
                return false;
            }
        }
    }

    // Check for recursive or cyclic procedure calls
    for (map<string, vector<string>>::iterator it = procedureSequenceMap.begin(); it != procedureSequenceMap.end(); it++) {
        for (int i = 0; i < it->second.size(); i++) {
            if (it->first == it->second[i]) {
                return false;
            }
            map<string, vector<string>>::iterator checkIterator = it;
            checkIterator++;
            for (checkIterator; checkIterator != procedureSequenceMap.end(); checkIterator++) {
                if (checkIterator->first == it->second[i]) {
                    for (int j = 0; j < checkIterator->second.size(); j++) {
                        if (checkIterator->second[j] == it->first) {
                            return false;
                        }
                    }
                }
            }
        }
    }

    processAssignStatementPatterns();
    processModifiesRelationships();
    processUsesRelationships();
    return true;
}

// Description: Function checks for the grammar rule for procedure
// Concrete Syntax Grammar Rule:
// procedure: 'procedure' proc_name '{' stmtLst '}'
// Parameters:
// - contents: a non-empty string containing the file contents
// Return:
// - string containing remaining file contents if the grammar rule for procedure is valid
// - "INVALID" if the grammar rule for procedure is invalid
string Parser::procedure(string contents) {
    if (expect(procedureSymbol, contents)) {
        contents = accept(procedureSymbol, contents);
        string leftCurlyBracesTerminal = "{";
        size_t position = contents.find(leftCurlyBracesTerminal);
        if (position != string::npos) {
            string extractedProcedureName = contents.substr(0, position);
            extractedProcedureName = removeTrailingSpacesFromString(extractedProcedureName);
            if (isValidNameIdentifier(extractedProcedureName)) {
                if (find(procTable.begin(), procTable.end(), extractedProcedureName) == procTable.end()) {
                    procTable.push_back(extractedProcedureName);
                }
                else {
                    return "INVALID";
                }
                currentProcedure = extractedProcedureName;
                vector<int> emptyIntegerVector;
                vector<string> emptyStringVector;
                procedureSequenceMap[currentProcedure] = emptyStringVector;
                procedureStatementsMap[currentProcedure] = emptyIntegerVector;
                contents = eraseStringFromStartToPosition(contents, position);
                if (expect(leftCurlyBracket, contents)) {
                    contents = accept(leftCurlyBracket, contents);
                }
                contents = statementList(contents);
                if (contents != "INVALID") {
                    if (expect(rightCurlyBracket, contents)) {
                        contents = accept(rightCurlyBracket, contents);
                        return contents;
                    }
                }
            }
        }
    }
    return "INVALID";
}

// Description: Function checks for the grammar rule for statement list
// Concrete Syntax Grammar Rule:
// stmtLst: stmt+
// Parameters:
// - contents: a non-empty string representing the remaining file contents
// Returns:
// - string of remaining file contents if the grammar rule for statement list is valid
// - "INVALID" if the grammar rule for statement list is invalid
string Parser::statementList(string contents) {
    // This is to check for at least one statement. If there isn't, the SIMPLE program is invalid.
    if (expect(rightCurlyBracket, contents)) {
        return "INVALID";
    }
    size_t i = statementTable.size() + 1;
    //followTable.push_back(make_pair(to_string(statementTable.size() - 1), to_string(statementTable.size())));
    string contentStatus = statement(contents);
    while (contentStatus != "INVALID" && !expect(rightCurlyBracket, contentStatus)) {
        followTable.push_back(make_pair(to_string(i), to_string(statementTable.size() + 1)));
        i = statementTable.size() + 1;
        contentStatus = statement(contentStatus);
    }
    return contentStatus;
}

// Description: Function checks for the grammar rule for statement
// Concrete Syntax Grammar Rule:
// read: 'read' var_name ';'
// print: 'print' var_name ';'
// call: 'call' proc_name ';'
// while: 'while' '(' cond_expr ')' '{' stmtLst '}'
// if: 'if' '(' cond_expr ')' 'then' '{' stmtLst '}' else '{' stmtLst '}'
// assign: var_name '=' expr ';'
// Parameters:
// - contents: a non-empty string representing the remaining file contents
// Returns:
// - string of remaining file contents if the grammar rule for statement is valid
// - "INVALID" if the grammar rule for statement is invalid
string Parser::statement(string contents) {
    size_t rightCurlyBracketPosition = contents.find(symbolToStringMap[rightCurlyBracket]);
    if (rightCurlyBracketPosition == 0) {
        return contents;
    }

    size_t semiColonPosition = contents.find(symbolToStringMap[semiColon]);
    size_t assignPosition = contents.find(symbolToStringMap[assignSymbol]);

    if (expect(readSymbol, contents)) {
        contents = accept(readSymbol, contents);
        string readStatement = symbolToStringMap[readSymbol] + " ";
        size_t semiColonPosition = contents.find(symbolToStringMap[semiColon]);
        string varName = contents.substr(0, semiColonPosition);
        varName = removeTrailingSpacesFromString(varName);
        if (isValidNameIdentifier(varName)) {
            readStatement = readStatement + varName;
            if (find(varTable.begin(), varTable.end(), varName) == varTable.end()) {
                varTable.push_back(varName);
            }
            contents.erase(0, semiColonPosition);
            contents = removeLeadingSpacesFromString(contents);
            if (expect(semiColon, contents)) {
                contents = accept(semiColon, contents);
                readStatement = readStatement + symbolToStringMap[semiColon];
                statementTable.push_back(readStatement);
                addParent();
                statementType.push_back(symbolToStringMap[readSymbol]);
                procedureStatementsMap[currentProcedure].push_back(statementTable.size());
                return contents;
            }
        }
    }
    else if (expect(printSymbol, contents)) {
        contents = accept(printSymbol, contents);
        string printStatement = symbolToStringMap[printSymbol] + " ";
        size_t semiColonPosition = contents.find(symbolToStringMap[semiColon]);
        string varName = contents.substr(0, semiColonPosition);
        varName = removeTrailingSpacesFromString(varName);
        if (isValidNameIdentifier(varName)) {
            printStatement = printStatement + varName;
            if (find(varTable.begin(), varTable.end(), varName) == varTable.end()) {
                varTable.push_back(varName);
            }
            contents.erase(0, semiColonPosition);
            contents = removeLeadingSpacesFromString(contents);
            if (expect(semiColon, contents)) {
                contents = accept(semiColon, contents);
                printStatement = printStatement + symbolToStringMap[semiColon];
                statementTable.push_back(printStatement);
                addParent();
                statementType.push_back(symbolToStringMap[printSymbol]);
                procedureStatementsMap[currentProcedure].push_back(statementTable.size());
                return contents;
            }
        }
    }
    else if (expect(callSymbol, contents)) {
        contents = accept(callSymbol, contents);
        string callStatement = symbolToStringMap[callSymbol] + " ";
        size_t semiColonPosition = contents.find(symbolToStringMap[semiColon]);
        string procName = contents.substr(0, semiColonPosition);
        procName = removeTrailingSpacesFromString(procName);
        if (isValidNameIdentifier(procName)) {
            callStatement = callStatement + procName;
            procedureSequenceMap[currentProcedure].push_back(procName);
            contents.erase(0, semiColonPosition);
            contents = removeLeadingSpacesFromString(contents);
            if (expect(semiColon, contents)) {
                contents = accept(semiColon, contents);
                callStatement = callStatement + symbolToStringMap[semiColon];
                statementTable.push_back(callStatement);
                addParent();
                statementType.push_back(symbolToStringMap[callSymbol]);
                procedureStatementsMap[currentProcedure].push_back(statementTable.size());
                return contents;
            }
        }
    }
    else if (expect(whileSymbol, contents)) {
        contents = accept(whileSymbol, contents);
        string whileStatement = symbolToStringMap[whileSymbol] + " ";
        if (expect(leftParenthesis, contents)) {
            contents = accept(leftParenthesis, contents);
            whileStatement = whileStatement + symbolToStringMap[leftParenthesis];
            contents = conditionExpression(contents, &whileStatement);
            if (contents != "INVALID") {
                if (expect(rightParenthesis, contents)) {
                    contents = accept(rightParenthesis, contents);
                    whileStatement = whileStatement + symbolToStringMap[rightParenthesis] + " ";
                    if (expect(leftCurlyBracket, contents)) {
                        contents = accept(leftCurlyBracket, contents);
                        whileStatement = whileStatement + symbolToStringMap[leftCurlyBracket];
                        statementTable.push_back(whileStatement);
                        addParent();
                        parentStack.push_back(statementTable.size());
                        statementType.push_back(symbolToStringMap[whileSymbol]);
                        procedureStatementsMap[currentProcedure].push_back(statementTable.size());
                        whileStatement.clear();
                        contents = statementList(contents);
                        if (contents != "INVALID") {
                            if (expect(rightCurlyBracket, contents)) {
                                contents = accept(rightCurlyBracket, contents);
                                parentStack.pop_back();
                                return contents;
                            }
                        }
                    }
                }
            }
        }
    }
    else if (expect(ifSymbol, contents)) {
        contents = accept(ifSymbol, contents);
        string ifStatement = symbolToStringMap[ifSymbol] + " ";
        if (expect(leftParenthesis, contents)) {
            contents = accept(leftParenthesis, contents);
            ifStatement = ifStatement + symbolToStringMap[leftParenthesis];
            contents = conditionExpression(contents, &ifStatement);
            if (contents != "INVALID") {
                if (expect(rightParenthesis, contents)) {
                    contents = accept(rightParenthesis, contents);
                    ifStatement = ifStatement + symbolToStringMap[rightParenthesis] + " ";
                    if (expect(thenSymbol, contents)) {
                        contents = accept(thenSymbol, contents);
                        ifStatement = ifStatement + symbolToStringMap[thenSymbol] + " ";
                        if (expect(leftCurlyBracket, contents)) {
                            contents = accept(leftCurlyBracket, contents);
                            ifStatement = ifStatement + symbolToStringMap[leftCurlyBracket];
                            statementTable.push_back(ifStatement);
                            addParent();
                            parentStack.push_back(statementTable.size());
                            statementType.push_back(symbolToStringMap[ifSymbol]);
                            procedureStatementsMap[currentProcedure].push_back(statementTable.size());
                            contents = statementList(contents);
                            if (contents != "INVALID") {
                                if (expect(rightCurlyBracket, contents)) {
                                    contents = accept(rightCurlyBracket, contents);
                                    if (expect(elseSymbol, contents)) {
                                        contents = accept(elseSymbol, contents);
                                        if (expect(leftCurlyBracket, contents)) {
                                            contents = accept(leftCurlyBracket, contents);
                                            contents = statementList(contents);
                                            if (contents != "INVALID") {
                                                if (expect(rightCurlyBracket, contents)) {
                                                    contents = accept(rightCurlyBracket, contents);
                                                    parentStack.pop_back();
                                                    return contents;
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    else if (assignPosition != string::npos && semiColonPosition > assignPosition) {
        string varName = contents.substr(0, assignPosition);
        varName = removeTrailingSpacesFromString(varName);
        if (isValidNameIdentifier(varName)) {
            string assignStatement = varName + " ";
            if (find(varTable.begin(), varTable.end(), varName) == varTable.end()) {
                varTable.push_back(varName);
            }
            contents = eraseStringFromStartToPosition(contents, assignPosition);
            if (expect(assignSymbol, contents)) {
                contents = accept(assignSymbol, contents);
                assignStatement = assignStatement + symbolToStringMap[assignSymbol] + " ";
                semiColonPosition = contents.find(symbolToStringMap[semiColon]);
                string expr = contents.substr(0, semiColonPosition);
                expr = removeTrailingSpacesFromString(expr);
                if (expression(expr)) {
                    assignStatement = assignStatement + expr;
                    contents = eraseStringFromStartToPosition(contents, semiColonPosition);
                    if (expect(semiColon, contents)) {
                        contents = accept(semiColon, contents);
                        assignStatement = assignStatement + symbolToStringMap[semiColon];
                        statementTable.push_back(assignStatement);
                        addParent();
                        statementType.push_back("assign");
                        procedureStatementsMap[currentProcedure].push_back(statementTable.size());
                        return contents;
                    }
                }
            }
        }
    }

    return "INVALID";
}

void Parser::addParent() {
    if (parentStack.size() > 0) {
        size_t par = parentStack.back();
        parentTable.push_back(make_pair(to_string(par), to_string(statementTable.size())));
    }
}

// Description: Function checks for the grammar rule for condition expression
// Concrete Syntax Grammar Rule:
// cond_expr: rel_expr | '!' '(' cond_expr ')' | '(' cond_expr ')' '&&' '(' cond_expr ')' | '(' cond_expr ')' '||' '(' cond_expr ')'
// Parameters:
// - contents: a non-empty string representing the remaining file contents
// - *statementString: a string pointer to a statement string that will be stored in the statement table
// Returns:
// - string of remaining file contents if the grammar rule for condition expression if valid
// - "INVALID" if the grammar rule for condition expression is invalid
string Parser::conditionExpression(string contents, string *statementString) {
    if (expect(notConditionSymbol, contents)) {
        contents = accept(notConditionSymbol, contents);
        *statementString = *statementString + symbolToStringMap[notConditionSymbol];
        if (expect(leftParenthesis, contents)) {
            contents = accept(leftParenthesis, contents);
            *statementString = *statementString + symbolToStringMap[leftParenthesis];
            size_t rightParenthesisPosition = contents.find(symbolToStringMap[rightParenthesis]);
            string anotherConditionExpression = contents.substr(0, rightParenthesisPosition);
            anotherConditionExpression = removeTrailingSpacesFromString(anotherConditionExpression);
            if (conditionExpression(anotherConditionExpression, statementString) != "INVALID") {
                contents = eraseStringFromStartToPosition(contents, rightParenthesisPosition);
                if (expect(rightParenthesis, contents)) {
                    contents = accept(rightParenthesis, contents);
                    *statementString = *statementString + symbolToStringMap[rightParenthesis];
                    return contents;
                }
            }
        }
    }
    else if (expect(leftParenthesis, contents)) {
        contents = accept(leftParenthesis, contents);
        *statementString = *statementString + symbolToStringMap[leftParenthesis];
        size_t rightParenthesisPosition = contents.find(symbolToStringMap[rightParenthesis]);
        string anotherConditionExpression = contents.substr(0, rightParenthesisPosition);
        anotherConditionExpression = removeTrailingSpacesFromString(anotherConditionExpression);
        if (conditionExpression(anotherConditionExpression, statementString) != "INVALID") {
            contents = eraseStringFromStartToPosition(contents, rightParenthesisPosition);
            if (expect(rightParenthesis, contents)) {
                contents = accept(rightParenthesis, contents);
                *statementString = *statementString + symbolToStringMap[rightParenthesis];
                if (expect(andConditionSymbol, contents) || expect(orConditionSymbol, contents)) {
                    if (expect(andConditionSymbol, contents)) {
                        contents = accept(andConditionSymbol, contents);
                        *statementString = *statementString + symbolToStringMap[andConditionSymbol];
                    }
                    else if (expect(orConditionSymbol, contents)) {
                        contents = accept(orConditionSymbol, contents);
                        *statementString = *statementString + symbolToStringMap[orConditionSymbol];
                    }
                    if (expect(leftParenthesis, contents)) {
                        contents = accept(leftParenthesis, contents);
                        *statementString = *statementString + symbolToStringMap[leftParenthesis];
                        rightParenthesisPosition = contents.find(symbolToStringMap[rightParenthesis]);
                        anotherConditionExpression = contents.substr(0, rightParenthesisPosition);
                        anotherConditionExpression = removeTrailingSpacesFromString(anotherConditionExpression);
                        contents = conditionExpression(contents, statementString);
                        if (contents != "INVALID") {
                            if (expect(rightParenthesis, contents)) {
                                contents = accept(rightParenthesis, contents);
                                *statementString = *statementString + symbolToStringMap[rightParenthesis];
                                return contents;
                            }
                        }
                    }
                }
            }
        }
    }

    size_t rightParenthesisPosition = contents.find(symbolToStringMap[rightParenthesis]);
    string relExpr = contents.substr(0, rightParenthesisPosition);
    relExpr = removeTrailingSpacesFromString(relExpr);
    if (relationshipExpression(relExpr)) {
        *statementString = *statementString + relExpr;
        contents.erase(0, rightParenthesisPosition);
        return contents;
    }
    return "INVALID";
}

// Description: Function checks if the string token (based on the symbol) occurs from string length 0 onwards (of contents) and erase it
// Parameters:
// - symbol: symbol representing the string token to select
// - contents: a non-empty string representing the remaining file contents
// Returns:
// - string of remaining file contents if the string token occurs from string length 0 of contents
// - "INVALID" if the string token does not occur from string length 0 of contents
string Parser::accept(Parser::Symbol symbol, string contents) {
    string stringToSearch = symbolToStringMap[symbol];
    size_t stringToSearchPosition = contents.find(stringToSearch);

    if (stringToSearchPosition == 0) {
        contents.erase(0, stringToSearch.length());
        contents = removeLeadingSpacesFromString(contents);
        return contents;
    }
    return "INVALID";
}

// Description: Function checks if the string token (based on the symbol) occurs from string length 0 onwards (of contents)
// Parameters:
// - symbol: symbol representing the string token to select
// - contents: a non-empty string representing the remaining file contents
// Returns:
// - true if the string token occurs from string length 0 of contents
// - false if the string token does not occur from string length 0 of contents
bool Parser::expect(Parser::Symbol symbol, string contents) {
    string stringToSearch = symbolToStringMap[symbol];
    size_t stringToSearchPosition = contents.find(stringToSearch);

    if (stringToSearchPosition == 0) {
        return true;
    }
    return false;
}

// Description: Function erases a string from string length 0 to specified position and returns it
// Parameters:
// - stringToErase: a non-empty string to have its contents erased
// - position: the string position to erase to
// Returns:
// - string of remaining contents if position is valid (less than length of string)
string Parser::eraseStringFromStartToPosition(string stringToErase, size_t position) {
    if (position < stringToErase.length()) {
        stringToErase.erase(0, position);
        stringToErase = removeLeadingSpacesFromString(stringToErase);
    }
    return stringToErase;
}

// Description: Function checks for the grammar rule for relationship expression
// Concrete Syntax Grammar Rule:
// rel_expr: rel_factor '>' rel_factor | rel_factor '>=' rel_factor | rel_expr: rel_factor '<' rel_factor | rel_factor '<=' rel_factor | rel_factor '!=' rel_factor | rel_factor '==' rel_factor
// Parameters:
// - relExpr: a non-empty string representing the relationship expression to check
// Returns:
// - true if the grammar rule for relationship expression is valid
// - false if the grammar rule for relationship expression is invalid
bool Parser::relationshipExpression(string relExpr) {
    size_t greaterThanPosition = relExpr.find(symbolToStringMap[greaterThanSymbol]);
    size_t greaterThanEqualToPosition = relExpr.find(symbolToStringMap[greaterThanEqualToSymbol]);
    size_t lessThanPosition = relExpr.find(symbolToStringMap[lessThanSymbol]);
    size_t lessThanEqualToPosition = relExpr.find(symbolToStringMap[lessThanEqualToSymbol]);
    size_t equalToPosition = relExpr.find(symbolToStringMap[equalToSymbol]);
    size_t notEqualToPosition = relExpr.find(symbolToStringMap[notEqualToSymbol]);

    if (greaterThanEqualToPosition != string::npos) {
        string relFactor = relExpr.substr(0, greaterThanEqualToPosition);
        relFactor = removeTrailingSpacesFromString(relFactor);
        if (relationshipFactor(relFactor)) {
            relExpr = eraseStringFromStartToPosition(relExpr, greaterThanEqualToPosition);
            if (expect(greaterThanEqualToSymbol, relExpr)) {
                relExpr = accept(greaterThanEqualToSymbol, relExpr);
                if (relationshipFactor(relExpr)) {
                    return true;
                }
            }
        }
    }
    else if (lessThanEqualToPosition != string::npos) {
        string relFactor = relExpr.substr(0, lessThanEqualToPosition);
        relFactor = removeTrailingSpacesFromString(relFactor);
        if (relationshipFactor(relFactor)) {
            relExpr = eraseStringFromStartToPosition(relExpr, lessThanEqualToPosition);
            if (expect(lessThanEqualToSymbol, relExpr)) {
                relExpr = accept(lessThanEqualToSymbol, relExpr);
                if (relationshipFactor(relExpr)) {
                    return true;
                }
            }
        }
    }
    else if (greaterThanPosition != string::npos) {
        string relFactor = relExpr.substr(0, greaterThanPosition);
        relFactor = removeTrailingSpacesFromString(relFactor);
        if (relationshipFactor(relFactor)) {
            relExpr = eraseStringFromStartToPosition(relExpr, greaterThanPosition);
            if (expect(greaterThanSymbol, relExpr)) {
                relExpr = accept(greaterThanSymbol, relExpr);
                if (relationshipFactor(relExpr)) {
                    return true;
                }
            }
        }
    }
    else if (lessThanPosition != string::npos) {
        string relFactor = relExpr.substr(0, lessThanPosition);
        relFactor = removeTrailingSpacesFromString(relFactor);
        if (relationshipFactor(relFactor)) {
            relExpr = eraseStringFromStartToPosition(relExpr, lessThanPosition);
            if (expect(lessThanSymbol, relExpr)) {
                relExpr = accept(lessThanSymbol, relExpr);
                if (relationshipFactor(relExpr)) {
                    return true;
                }
            }
        }
    }
    else if (equalToPosition != string::npos) {
        string relFactor = relExpr.substr(0, equalToPosition);
        relFactor = removeTrailingSpacesFromString(relFactor);
        if (relationshipFactor(relFactor)) {
            relExpr = eraseStringFromStartToPosition(relExpr, equalToPosition);
            if (expect(equalToSymbol, relExpr)) {
                relExpr = accept(equalToSymbol, relExpr);
                if (relationshipFactor(relExpr)) {
                    return true;
                }
            }
        }
    }
    else if (notEqualToPosition != string::npos) {
        string relFactor = relExpr.substr(0, notEqualToPosition);
        relFactor = removeTrailingSpacesFromString(relFactor);
        if (relationshipFactor(relFactor)) {
            relExpr = eraseStringFromStartToPosition(relExpr, notEqualToPosition);
            if (expect(notEqualToSymbol, relExpr)) {
                relExpr = accept(notEqualToSymbol, relExpr);
                if (relationshipFactor(relExpr)) {
                    return true;
                }
            }
        }
    }

    return false;
}

// Description: Function checks for the grammar rule for relationship factor
// Concrete Syntax Grammar Rule:
// rel_factor: var_name | const_value | expr
// Parameters:
// - relExpr: a non-empty string representing the relationship expression to check
// Returns:
// - true if the grammar rule for relationship factor is valid
// - false if the grammar rule for relationship factor is invalid
bool Parser::relationshipFactor(string relFactor) {
    if (isValidNameIdentifier(relFactor)) {
        if (find(varTable.begin(), varTable.end(), relFactor) == varTable.end()) {
            varTable.push_back(relFactor);
        }
        return true;
    }
    else if (constantValue(relFactor)) {
        return true;
    }
    return expression(relFactor);
}

// Description: Function checks for the grammar rule for expression
// Concrete Syntax Grammar Rule:
// expr: expr '+' term | expr '-' term | term
// Parameters:
// - expr: a non-empty string representing the expression to check
// Returns:
// - true if the grammar rule for expression is valid
// - false if the grammar rule for expression is invalid
bool Parser::expression(string expr) {
    if (expect(leftParenthesis, expr)) {
        return term(expr);
    }

    size_t position = expr.find(symbolToStringMap[plusSymbol]);
    string anotherExpression;
    if (position != string::npos) {
        size_t minusPosition = expr.find(symbolToStringMap[minusSymbol]);
        if (position > minusPosition && minusPosition != string::npos) {
            position = minusPosition;
        }
        anotherExpression = expr.substr(0, position);
        anotherExpression = removeTrailingSpacesFromString(anotherExpression);
        if (expression(anotherExpression)) {
            expr = eraseStringFromStartToPosition(expr, position);
            if (expect(plusSymbol, expr)) {
                expr = accept(plusSymbol, expr);
                return expression(expr);
            }
            else if (expect(minusSymbol, expr)) {
                expr = accept(minusSymbol, expr);
                return expression(expr);
            }
        }
    }
    else {
        position = expr.find(symbolToStringMap[minusSymbol]);
        if (position != string::npos) {
            anotherExpression = expr.substr(0, position);
            anotherExpression = removeTrailingSpacesFromString(anotherExpression);
            if (expression(anotherExpression)) {
                expr = eraseStringFromStartToPosition(expr, position);
                if (expect(minusSymbol, expr)) {
                    expr = accept(minusSymbol, expr);
                    return expression(expr);
                }
            }
        }
        return term(expr);
    }

    return false;
}

// Description: Function checks for the grammar rule for term
// Concrete Syntax Grammar Rule:
// term: term '*' factor | term '/' factor | term '%' factor | factor
// Parameters:
// - inputTerm: a non-empty string representing the term to check
// Returns:
// - true if the grammar rule for term is valid
// - false if the grammar rule for term is invalid
bool Parser::term(string inputTerm) {
    if (expect(leftParenthesis, inputTerm)) {
        return factor(inputTerm);
    }

    size_t position = inputTerm.find(symbolToStringMap[timesSymbol]);
    string anotherTerm;
    if (position != string::npos) {
        size_t anotherPosition = inputTerm.find(symbolToStringMap[divideSymbol]);
        size_t moduloPosition = inputTerm.find(symbolToStringMap[moduloSymbol]);
        if (anotherPosition > moduloPosition && moduloPosition != string::npos) {
            anotherPosition = moduloPosition;
        }
        if (position > anotherPosition && anotherPosition != string::npos) {
            position = anotherPosition;
            anotherTerm = inputTerm.substr(0, position);
            anotherTerm = removeTrailingSpacesFromString(anotherTerm);
            if (term(anotherTerm)) {
                inputTerm = eraseStringFromStartToPosition(inputTerm, position);
                if (expect(divideSymbol, inputTerm)) {
                    inputTerm = accept(divideSymbol, inputTerm);
                }
                else if (expect(moduloSymbol, inputTerm)) {
                    inputTerm = accept(moduloSymbol, inputTerm);
                }
                return term(inputTerm);
            }
        }
        else {
            anotherTerm = inputTerm.substr(0, position);
            anotherTerm = removeTrailingSpacesFromString(anotherTerm);
            if (term(anotherTerm)) {
                inputTerm = eraseStringFromStartToPosition(inputTerm, position);
                if (expect(timesSymbol, inputTerm)) {
                    inputTerm = accept(timesSymbol, inputTerm);
                    return term(inputTerm);
                }
            }
        }
    }
    else {
        position = inputTerm.find(symbolToStringMap[divideSymbol]);
        if (position != string::npos) {
            size_t moduloPosition = inputTerm.find(symbolToStringMap[moduloSymbol]);
            if (position > moduloPosition && moduloPosition != string::npos) {
                position = moduloPosition;
            }
            anotherTerm = inputTerm.substr(0, position);
            anotherTerm = removeTrailingSpacesFromString(anotherTerm);
            if (term(anotherTerm)) {
                inputTerm = eraseStringFromStartToPosition(inputTerm, position);
                if (expect(divideSymbol, inputTerm)) {
                    inputTerm = accept(divideSymbol, inputTerm);
                }
                else if (expect(moduloSymbol, inputTerm)) {
                    inputTerm = accept(moduloSymbol, inputTerm);
                }
                return term(inputTerm);
            }
        }
        else {
            position = inputTerm.find(symbolToStringMap[moduloSymbol]);
            if (position != string::npos) {
                anotherTerm = inputTerm.substr(0, position);
                anotherTerm = removeTrailingSpacesFromString(anotherTerm);
                if (term(anotherTerm)) {
                    inputTerm = eraseStringFromStartToPosition(inputTerm, position);
                    if (expect(moduloSymbol, inputTerm)) {
                        inputTerm = accept(moduloSymbol, inputTerm);
                    }
                    return term(inputTerm);
                }
            }
            return factor(inputTerm);
        }
    }
    return false;
}

// Description: Function checks for the grammar rule for factor
// Concrete Syntax Grammar Rule:
// factor: var_name | const_value | '(' expr ')'
// Parameters:
// - inputFactor: a non-empty string representing the factor to check
// Returns:
// - true if the grammar rule for factor is valid
// - false if the grammar rule for factor is invalid
bool Parser::factor(string inputFactor) {
    if (isValidNameIdentifier(inputFactor)) {
        if (find(varTable.begin(), varTable.end(), inputFactor) == varTable.end()) {
            varTable.push_back(inputFactor);
        }
        return true;
    }
    else if (constantValue(inputFactor)) {
        return true;
    }
    else {
        if (expect(leftParenthesis, inputFactor)) {
            inputFactor = accept(leftParenthesis, inputFactor);
            size_t position = inputFactor.find(symbolToStringMap[rightParenthesis]);
            string expr = inputFactor.substr(0, position);
            if (expression(expr)) {
                inputFactor = eraseStringFromStartToPosition(inputFactor, position);
                if (expect(rightParenthesis, inputFactor)) {
                    inputFactor = accept(rightParenthesis, inputFactor);
                    return true;
                }
            }
        }
    }
    return false;
}

// Description: Function checks for the grammar rule for constant value
// Concrete Syntax Grammar Rule:
// const_value: DIGIT+
// Parameters:
// - constValue: a non-empty string representing the constant value to check
// Returns:
// - true if the grammar rule for constant value is valid
// - false if the grammar rule for constant value is invalid
bool Parser::constantValue(string constValue) {
    return isValidIntegerToken(constValue);
}

// Description: Function checks if a given string is a valid (variable/procedure) name identifer
// Parameters:
// - name: a non-empty string representing the (variable/procedure) name to check
// Returns:
// - true if the (variable/procedure) name is valid
// - false if the (variable/procedure) name is invalid
bool Parser::isValidNameIdentifier(string name) {
    if (isNotStatementIdentifer(name)) {
        if (isValidNameToken(name)) {
            return true;
        }
    }
    return false;
}

// Description: Function checks if a given string is a valid (variable/procedure) name token
// Lexical tokens:
// NAME: LETTER (LETTER|DIGIT)* -- procedure names and variables are strings of letters, and digits, starting with a letter
// Parameters:
// - name: a non-empty string representing the (variable/procedure) name to check
// Returns:
// - true if the (variable/procedure) name is valid
// - false if the (variable/procedure) name is invalid
bool Parser::isValidNameToken(string name) {
    for (string::size_type i = 0; i < name.size(); ++i) {
        if (i == 0) {
            if (!(isValidLetter(name[i]))) {
                return false;
            }
        }
        else {
            if (!(isValidLetter(name[i]) || isValidDigit(name[i]))) {
                return false;
            }
        }
    }
    return true;
}

// Description: Function checks whether the input character is a valid letter
// Lexical tokens:
// LETTER: A-Z | a-z -- capital or small letter
// Parameters:
// - c: non-empty char
// Return:
// - true if letter is an alphabet
// - false if letter is not an alphabet
bool Parser::isValidLetter(char c) {
    return isalpha(c);
}

// Description: Function checks whether the input character is a valid digit
// Lexical tokens:
// DIGIT: 0-9
// Parameters:
// - c: non-empty char
// Return:
// - true if letter is a digit
// - false if letter is not a digit
bool Parser::isValidDigit(char c) {
    return isdigit(c);
}

// Description: Function checks whether the input string "constantValue" is a valid integer token
// Lexical tokens:
// INTEGER: DIGIT+ -- constants are sequences of digits
// Parameters:
// - constantValue: a non-empty string
// Return:
// - true if integer token format is valid
// - false if integer token format is not valid
bool Parser::isValidIntegerToken(string constantValue) {
    for (string::size_type i = 0; i < constantValue.size(); ++i) {
        if (!isValidDigit(constantValue[i])) {
            return false;
        }
    }
    return true;
}

// Description: Function checks if a given string is a valid (variable/procedure) name identifer
// Parameters:
// - name: a non-empty string representing the (variable/procedure) name to check
// Returns:
// - true if the (variable/procedure) name is valid
// - false if the (variable/procedure) name is one of the statement identifiers (e.g. if, while, etc.)
bool Parser::isNotStatementIdentifer(string name) {
    if (name != symbolToStringMap[readSymbol] &&
        name != symbolToStringMap[printSymbol] &&
        name != symbolToStringMap[callSymbol] &&
        name != symbolToStringMap[whileSymbol] &&
        name != symbolToStringMap[ifSymbol]) {
        return true;
    }
    return false;
}

void Parser::processAssignStatementPatterns() {
    assignPatternMap.clear();
    for (int i = 0; i < statementType.size(); i++) {
        if (statementType[i] == "assign") {
            string assignStatement = statementTable[i];
            size_t position = assignStatement.find(symbolToStringMap[assignSymbol]);
            string leftOfAssignStatement = assignStatement.substr(0, position);
            leftOfAssignStatement = removeTrailingSpacesFromString(leftOfAssignStatement);
            assignStatement = eraseStringFromStartToPosition(assignStatement, position + symbolToStringMap[assignSymbol].length());
            position = assignStatement.find(symbolToStringMap[semiColon]);
            string rightOfAssignStatement = assignStatement.substr(0, position);
            rightOfAssignStatement = removeTrailingSpacesFromString(rightOfAssignStatement);
            vector<string> assignPattern;
            assignPattern.push_back(leftOfAssignStatement);
            assignPattern.push_back(rightOfAssignStatement);
            assignPatternMap[to_string(i+1)] = assignPattern;
        }
    }
}

void Parser::processUsesRelationships() {
    for (int i = 0; i < statementType.size(); i++) {
        if (statementType[i] == "assign") {
            string assignStatement = statementTable[i];
            size_t position = assignStatement.find(symbolToStringMap[assignSymbol]);
            assignStatement = eraseStringFromStartToPosition(assignStatement, position + symbolToStringMap[assignSymbol].length());
            position = assignStatement.find(symbolToStringMap[semiColon]);
            string rightOfAssignStatement = assignStatement.substr(0, position);
            for (int j = 0; j < varTable.size(); j++) {
                position = rightOfAssignStatement.find(varTable[j]);
                if (position != string::npos) {
                    usesRelationshipMap[to_string(i + 1)] = varTable[j];
                }
            }
        }
        else if (statementType[i] == symbolToStringMap[printSymbol]) {
            for (int j = 0; j < varTable.size(); j++) {
                size_t position = statementTable[i].find(varTable[j]);
                if (position != string::npos) {
                    usesRelationshipMap[to_string(i + 1)] = varTable[j];
                }
            }
        }
        else if (statementType[i] == symbolToStringMap[ifSymbol] || statementType[i] == symbolToStringMap[whileSymbol]) {
            for (int j = 0; j < varTable.size(); j++) {
                size_t position = statementTable[i].find(varTable[j]);
                if (position != string::npos) {
                    usesRelationshipMap[to_string(i + 1)] = varTable[j];
                }
                // there is a statement s1 in container such that Uses(s1, v) [See above 2 uses cases]
                else {
                    // Use the Parent* relationship to determine if the next lines are in the container
                }
            }
        }
    }
    // Uses (Procedure p, Variable v) holds if there is a statement s in p or
    // in a procedure called (directly or indirectly) from p such that Uses (s, v) holds.
    for (int i = 0; i < procTable.size(); i++) {
        for (map<string, vector<int>>::iterator it = procedureStatementsMap.begin(); it != procedureStatementsMap.end(); it++) {
            for (int j = 0; j < it->second.size(); j++) {
                if (statementType[it->second[j]-1] != symbolToStringMap[callSymbol]) {
                    // Copy & Paste the Uses (s, v) into here
                }
                else {

                }
            }
        }
    }
}

void Parser::processModifiesRelationships() {
    for (int i = 0; i < statementType.size(); i++) {
        if (statementType[i] == "assign") {
            string assignStatement = statementTable[i];
            size_t position = assignStatement.find(symbolToStringMap[assignSymbol]);
            string leftOfAssignStatement = assignStatement.substr(0, position);
            leftOfAssignStatement = removeTrailingSpacesFromString(leftOfAssignStatement);
            for (int j = 0; j < varTable.size(); j++) {
                position = leftOfAssignStatement.find(varTable[j]);
                if (position != string::npos) {
                    modifiesRelationshipMap[to_string(i + 1)] = varTable[j];
                }
            }
        }
        else if (statementType[i] == symbolToStringMap[readSymbol]) {
            for (int j = 0; j < varTable.size(); j++) {
                size_t position = statementTable[i].find(varTable[j]);
                if (position != string::npos) {
                    modifiesRelationshipMap[to_string(i + 1)] = varTable[j];
                }
            }
        }
        else if (statementType[i] == symbolToStringMap[ifSymbol] || statementType[i] == symbolToStringMap[whileSymbol]) {
            for (int j = 0; j < varTable.size(); j++) {
                // there is a statement s1 in container such that Modifies(s1, v) [See above 2 uses cases]
            }
        }
        else if (statementType[i] == symbolToStringMap[callSymbol]) {
            // TODO...
        }
    }
    // Modifies (Procedure p, Variable v) holds if there is a statement s in p or
    // in a procedure called (directly or indirectly) from p such that Modifies (s, v) holds.
    for (int i = 0; i < procTable.size(); i++) {
        for (map<string, vector<int>>::iterator it = procedureStatementsMap.begin(); it != procedureStatementsMap.end(); it++) {
            for (int j = 0; j < it->second.size(); j++) {
                if (statementType[it->second[j]-1] != symbolToStringMap[callSymbol]) {
                    // Copy & Paste the Modifies (s, v) into here
                }
                else {

                }
            }
        }
    }
}

void Parser::printFollowTable() {
    for (auto& element : followTable) {
        cout << "Follows(" << element.first << "," << element.second << ")" << endl;
    }
}

void Parser::printParentTable() {
    for (auto& element : parentTable) {
        cout << "Parents(" << element.first << "," << element.second << ")" << endl;
    }
}

void Parser::printAllVariables() {
    cout << "Printing VarTable..." << endl;
    for (int i = 0; i < varTable.size(); i++) {
        cout << "index " << i << ": \"" << varTable[i] << "\"" << endl;
    }
}

void Parser::printAllProcedures() {
    cout << "Printing ProcTable..." << endl;
    for (int i = 0; i < procTable.size(); i++) {
        cout << "index " << i << ": \"" << procTable[i] << "\"" << endl;
    }
}

void Parser::printAllStatements() {
    cout << "Printing Statements..." << endl;
    for (int i = 0; i < statementTable.size(); i++) {
        cout << "stmt #" << i+1 << ": \"" << statementTable[i] << "\"" << endl;
    }
    cout << "Printing Statement Types..." << endl;
    for (int i = 0; i < statementType.size(); i++) {
        cout << "stmt #" << i + 1 << ": \"" << statementType[i] << "\"" << endl;
    }
}

void Parser::printAllAssignPatterns() {
    cout << "Printing Assign Patterns..." << endl;
    for (map<string, vector<string>>::iterator it = assignPatternMap.begin(); it != assignPatternMap.end(); it++) {
        cout << "stmtNum: \"" << it->first << "\", lhs: \"" << it->second[0] << "\", rhs: \"" << it->second[1] << "\"" << endl;
    }
}

void Parser::printAllUsesRelationships() {
    cout << "Printing Uses Relationships..." << endl;
    for (map<string, string>::iterator it = usesRelationshipMap.begin(); it != usesRelationshipMap.end(); it++) {
        cout << "Uses(\"" << it->first << "\", \"" << it->second << "\")" << endl;
    }
}

void Parser::printAllModifiesRelationships() {
    cout << "Printing Modifies Relationships..." << endl;
    for (map<string, string>::iterator it = modifiesRelationshipMap.begin(); it != modifiesRelationshipMap.end(); it++) {
        cout << "Modifies(\"" << it->first << "\", \"" << it->second << "\")" << endl;
    }
}