var grammars;

window.onload = function() {
  clear();

  // Create new grammars
  grammars = new Array();

  // Update checkbox text so user knows what happens when select demo
  updateCheckboxText();
}

// -------------------------------------------------------------------------------------------------------

function Grammar(variableName, internalStates, inputAlphabet, transitionFunctionsSymbol, startingState, finalStates) {
  this._variableName = variableName;
  this._internalStates = internalStates;
  this._inputAlphabet = inputAlphabet;
  this._transitionFunctionsSymbol = transitionFunctionsSymbol;
  this._transitionFunctions = new Array();
  this._startingState = startingState;
  this._finalStates = finalStates;
}

Grammar.prototype._variableName;
Grammar.prototype._internalStates;
Grammar.prototype._inputAlphabet;
Grammar.prototype._transitionFunctionsSymbol;
Grammar.prototype._transitionFunctions;
Grammar.prototype._startingState;
Grammar.prototype._finalStates;

Grammar.prototype.getVariableName = function() {
  return this._variableName;
}

Grammar.prototype.getInternalStates = function() {
  return this._internalStates;
}

Grammar.prototype.getInputAlphabet = function() {
  return this._inputAlphabet;
}

Grammar.prototype.getTransitionFunctionsSymbol = function() {
  return this._transitionFunctionsSymbol;
}

Grammar.prototype.getTransitionFunctions = function() {
  return this._transitionFunctions;
}

Grammar.prototype.addTransitionFunction = function(newTransitionFunction) {
  return this._transitionFunctions.push(newTransitionFunction);
}

Grammar.prototype.getStartingState = function() {
  return this._startingState;
}

Grammar.prototype.getFinalStates = function() {
  return this._finalStates;
}

Grammar.prototype.toString = function() {
  return this._variableName+" =  {"+arrayToSet(this._internalStates)+", "+arrayToSet(this._inputAlphabet)+", "+this._transitionFunctionsSymbol+", "+this._startingState+", "+arrayToSet(this._finalStates)+"}";
}

Grammar.prototype.isAcceptAnyCharacter = function() {
  return this._inputAlphabet.length == 1 && this._inputAlphabet[0] == 'characters';
}

Grammar.prototype.isAcceptAnyWord = function() {
  return this._inputAlphabet.length == 1 && this._inputAlphabet[0] == 'words';
}

// -------------------------------------------------------------------------------------------------------

function ProductionRule(sourceNode, transitionValue, destNode) {
  this._sourceNode = sourceNode;
  this._transitionValue = transitionValue;
  this._destNode = destNode;
}

ProductionRule.prototype._sourceNode;
ProductionRule.prototype._transitionValue;
ProductionRule.prototype._destNode;

ProductionRule.prototype.getSourceNode = function() {
  return this._sourceNode;
}

ProductionRule.prototype.getTransitionValue = function() {
  return this._transitionValue;
}

ProductionRule.prototype.getDestNode = function() {
  return this._destNode;
}

// -------------------------------------------------------------------------------------------------------
function ReturnValue(msg, isError) {
  this._msg = msg;
  this._isError = isError;
}

ReturnValue.prototype._msg;
ReturnValue.prototype._isError;

ReturnValue.prototype.getMsg = function() {
  return this._msg;
}

ReturnValue.prototype.isError = function() {
  return this._isError;
}

// -------------------------------------------------------------------------------------------------------

function updateCheckboxText() {
  var checkBox = document.getElementById('explain_demo');
  var checkBoxText = document.getElementById('explain_demo_text');

  if (checkBox.checked) {
    checkBoxText.innerHTML = 'Show popups during demo';
  } else {
    checkBoxText.innerHTML = 'Do not show popups during demo';
  }
}

function runUnitTest() {
  var confirmVal = confirm('Running tests could clobber any grammars you have already defined. Continue?');
  if (!confirmVal) {
    return;
  }

  var tests = new Array();
  tests.push('dump');
  tests.push('');
  tests.push(' ');
  tests.push('# Just a comment. Should ignore.');
  tests.push('m1 = {{q0, valid state1, q2}, {a,b}, trans1, q0, {q0}}        # Should pass');
  tests.push('m1 = {{q0, valid-state1, q2}, {a,b}, trans1, q0, {q0, valid-state1}}        # Should pass');
  tests.push('m1 = {{q0, valid_state1, q2}, {a,b}, trans1, q0, {q0}}        # Should pass');
  tests.push('m1 = {{q0, $invalid-state1, q2}, {a,b}, trans1, q0, {q4}}     # Should fail: State contains invalid characters');
  tests.push('m1 = {{q0, q1, q2}, {valid input,b}, trans1, q0, {q0}}        # Should pass');
  tests.push('m1 = {{q0, q1, q2}, {valid-input,b}, trans1, q0, {q0}}        # Should pass');
  tests.push('m1 = {{q0, q1, q2}, {valid_input,b}, trans1, q0, {q0}}        # Should pass');
  tests.push('m1 = {{q0, q1, q2}, {$invalid_input,b}, trans1, q0, {q4}}     # Should fail: Invalid alphabet');
  tests.push('m1 = {{q0, q1, q2}, {a,b}, trans1, q0, {q0, q4}}              # Should fail: Final state not a valid state');
  tests.push('m1 = {{q0, q1, q2}, {a,b}, trans1, r0, {q0, q2}}              # Should fail: Starting state not a valid state');
  tests.push('m1 = {{q0, q1, q2}, {a,b}, trans1, q0, {q0, q2}}              # Should pass');
  tests.push('m1 = {{q0, q1}, {0, 1}, trans1, q0, {q1}}                     # Should pass: Replace last grammar m1');
  tests.push('m2 = {{q0, q1, q2}, {a, b}, trans1, q0, {q2}}                 # Should fail: transition function trans1 in grammar m1');
  tests.push('m2 = {{q0, q1, q2}, {a, b}, trans2, q0, {q2}}                 # Should pass');
  tests.push('trans3(q0,a) -> q1                                            # Should fail: trans3 does not exist in a grammar');
  tests.push('trans2(q0,a -> q1                                             # Should fail: bad parentheses');
  tests.push('trans2 q0,a) -> q1                                            # Should fail: bad parentheses');
  tests.push('trans2)q0,a( -> q1                                            # Should fail: bad parentheses');
  tests.push('trans2(bad-state,a) -> q1                                     # Should fail: input state does not exist');
  tests.push('trans2(q0,i) -> q1                                            # Should fail: input character invalid');
  tests.push('trans2(q0,a) -> bad-state                                     # Should fail: output state does not exist');
  tests.push('trans2(q0,a) -> q1                                            # Should pass');
  tests.push('trans2(q1,b) -> q2                                            # Should pass');
  tests.push('trans2(q2,a) -> q1                                            # Should pass');
  tests.push('trans2(q0,lambda) -> q2                                       # Should pass');
  tests.push('L(m2) ?                                                       # true');
  tests.push('L(m2) ? ab                                                    # true');
  tests.push('L(m2) ? abab                                                  # true');
  tests.push('L(m2) ? ababab                                                # true');
  tests.push('L(m2) ? ba                                                    # false');
  tests.push('L(m2) ? aba                                                   # false');
  tests.push('L(m2) ? a                                                     # false');
  tests.push('dump');
  
  // Test words mode
  tests.push('# Testing words mode');
  tests.push('todo = {{noun, description, dayOfWeek, period, finish}, {words}, todoTrans, noun, {finish}} # okay');
  tests.push('todoTrans(noun, *) -> noun           # okay');
  tests.push('todoTrans(noun, must) -> description # okay');
  tests.push('todoTrans(description, *) -> description # okay');
  tests.push('todoTrans(description, on) -> dayOfWeek  # okay');
  tests.push('todoTrans(dayOfWeek, *) -> description   # okay');
  tests.push('todoTrans(dayOfWeek, Monday) -> period   # okay');
  tests.push('todoTrans(dayOfWeek, Tuesday) -> period  # okay');
  tests.push('todoTrans(dayOfWeek, Wednesday) -> period  # okay');
  tests.push('todoTrans(dayOfWeek, Thursday) -> period  # okay');
  tests.push('todoTrans(dayOfWeek, Friday) -> period  # okay');
  tests.push('todoTrans(dayOfWeek, Saturday) -> period  # okay');
  tests.push('todoTrans(dayOfWeek, Sunday) -> period  # okay');
  tests.push('todoTrans(period, *) -> description     # okay');
  tests.push('todoTrans(period, on) -> dayOfWeek      # okay');
  tests.push('todoTrans(period, .) -> finish          # okay');
  tests.push('L(todo) ? I must fix the car on Friday. # true');
  tests.push('L(todo) ? The artist formerly known as prince must feed the cat on Friday. # true');
  tests.push('L(todo) ? Dana must sleep on Tuesday. # true');
  tests.push('L(todo) ? Dana must sleep on Tuesday and wake up. # false');
  tests.push('L(todo) ? Dana must sleep on Tuesday and wake up on Wednesday. # true');
  tests.push('L(todo) ? I want to go shopping on Saturday. # false');
  tests.push('dump');

  for (var i=0; i<tests.length; i++) {
    parseInput(tests[i]);
  }
  alert('Ran total of '+tests.length+' tests.');
}

/**
 *
 */
function runDemo() {

  var isExplain = document.getElementById('explain_demo').checked;
  
  if (isExplain) {
    var confirmVal = confirm('I\'m about to walk you through with some examples.\n\nI\'ll add them to the console and explain what I am doing.\n\nThis will take a minute. Continue?\n\n');
    if (!confirmVal) {
      return;
    }
  }
  
  parseInput('Grammar1 = {{P1,P2,P3},{a,b},trans1,P1,{P3}}');

  if (isExplain) {
    confirmVal = confirm('I just defined a grammar with four states and two letters in alphabet.\n\nContinue?');
    if (!confirmVal) {
      return;
    }
    alert('With this grammar, I can query for any string made up of zero or more characters in {a,b}.\n\nE.g., \'\', \'a\', \'b\', \'ab\', \'aaaabbababa\', etc.');
    alert('Right now, this grammar (and its associated language) does nothing. We need to define the transition function.\n\nI\'m going to add the statements to do this now.');
  }

  parseInput('trans1(P3,a) -> P2');
  parseInput('trans1(P2,b) -> P3');
  parseInput('trans1(P1,a) -> P2');
  
  if (isExplain) {
    confirmVal = confirm('I just defined the transition function for three inputs at particular states.\n\nContinue?');
    if (!confirmVal) {
      return;
    }
    alert('What we want is any string made up of the substring \'ab\' any number of times.\n\nE.g., \'ab\', \'abab\', \'ababab\', etc.');
    alert('Time to run some queries.');
  }

  parseInput('L(Grammar1) ? ba');
  parseInput('L(Grammar1) ? ababab');
  parseInput('L(Grammar1) ? abab');
  parseInput('L(Grammar1) ? ab');
  parseInput('L(Grammar1) ? ');

  if (isExplain) {
    confirmVal = confirm('Let me explain this really quickly.\n\nContinue?');
    if (!confirmVal) {
      return;
    }
    alert("The first example checks whether the empty string is included. It isn\'t, so it is rejected.");
    alert('The next three examples check correct strings, which should have been accepted.');
    alert('The last example is out of order, and was rejected.');

    alert('This demo is over. We only defined one grammar, which will remain in memory for you.\n\nYou can define additional grammars and use them concurrently. For more information, click on \'help\'.');
  }
}

var lineNumber = 1;
var isShowLineNumbers = false;

/**
 *
 */
function clear() {
  lineNumber = 1;
  var console = document.getElementById('console');
  console.innerHTML = '';
  printWelcome();
}

function printWelcome() {
  printHelp();
  println('Welcome to <span style="color: #edef4e;">language shell</span>. You can enter grammers and query their associated language for inclusion of strings.');
}

function printHelp() {
  println('Click on <span style="color: #4148dc;">help</span> link above for more information. Type below and click <span style="color: #4148dc;">submit</span> to enter commands.');
}

/**
 *
 */
function println(msg) {
  var console = document.getElementById('console');
  var existingText = console.innerHTML;
  if (existingText.length > 0) {
    if (isShowLineNumbers) {
      console.innerHTML = "<span style=\"color: #777;\">"+lineNumber +":</span> "+msg+'<br />'+existingText;
    } else {
      console.innerHTML = msg+'<br />'+existingText;
    }
  } else {
    
    if (isShowLineNumbers) {
      console.innerHTML = "<span style=\"color: #777;\">"+lineNumber +":</span> "+msg;
    } else {
      console.innerHTML = msg;
    }
  }
  lineNumber++;
}

/**
 *
 */
function getInput() {
  var inputField = document.getElementById('console-input');

  var inputValue = trim(inputField.value);
  parseInput(inputValue);
}

function parseInput(inputValue) {

  println('');

  var trimmedValue = trim(removeComments(inputValue));

  if (trimmedValue == '') {
    println('<span class="success">whatever</span>');
  } else if (trimmedValue == 'clear') {
    clear();
  } else if (trimmedValue == 'dump') {
    dumpGrammars();
    println('');
  } else if (trimmedValue == 'help') {
    printHelp();
  } else {
    var returnValue = false;

    // Parse and print response from parser
    if (isSetGrammar(trimmedValue)) {
      returnValue = parseGrammar(trimmedValue);
    } else if (isSetProductionRule(trimmedValue)) {
      returnValue = parseProductionRule(trimmedValue);
    } else if (isQuery(trimmedValue)) {
      returnValue = parseQuery(trimmedValue);
    } else {
      println('<span class="error">Unrecognized input: '+trimmedValue+'</span>');
    }

    // Check to see whether there is a return value
    if (returnValue) {
      if (!returnValue.isError()) {
        println('<span class="success">'+returnValue.getMsg()+'</span>');
      } else {
        println('<span class="error">'+returnValue.getMsg()+'</span>');
      }
    }
  }
  // Print what user typed
  if (trimmedValue != 'clear') {
    println('<span style="color: #999;">You entered&gt;</span> '+trimmedValue+' <span style="color: #edef4e;">'+getComment(inputValue)+'</span>');
  }
}

function removeComments(val) {
  var commentIndex = val.indexOf('#');
  if (commentIndex != -1){
    return val.substring(0,commentIndex);
  }
  return val;
}

function getComment(val) {
  var commentIndex = val.indexOf('#');
  if (commentIndex != -1){
    return val.substring(commentIndex,val.length);
  }
  return '';
}

function dumpGrammars() {
  for (var i=0; i<grammars.length; i++) {
    var g = grammars[i];

    // Print out production rules/transition function
    for (var j=g.getTransitionFunctions().length-1; j>=0; j--) {
      var t = g.getTransitionFunctions()[j];
      println('<span style="color: #4148dc;">&nbsp;&nbsp;&nbsp;&nbsp;'+g.getTransitionFunctionsSymbol()+"("+t.getSourceNode()+","+t.getTransitionValue()+") -> "+t.getDestNode()+"</span>");
    }

    // 
    println('<span style="color: #4148dc;">&nbsp;&nbsp;'+g.toString()+"</span>");
  }
  println("<span style=\"color: #4148dc;\">Total of "+grammars.length+" grammar"+((grammars.length == 1)?"":"s")+".</span>");
}

/**
 * M = ({states}, {alphabet}, productionRule, starting state, {final states})
 */
function parseGrammar(val) {
  
  // Split the right-hand variable from left-hand expression
  var splitVal = val.split('=');
  if (splitVal.length != 2) {
    return new ReturnValue("Must be one equal sign to set a grammar", true);
  }

  var variableName = trim(splitVal[0]);
  if (variableName.length < 1) {
    return new ReturnValue("Must offer a variable name to set a grammar", true);
  }

  var expression = trim(splitVal[1]);
  if (expression.length < 1) {
    return new ReturnValue("Must offer an expression ({...}) to set a grammar", true);
  }

  if (!isSet(expression)) {
    return new ReturnValue("Expression for defining grammar not a valid set: "+expression, true);
  }

  var members = setToArray(expression);
  
  if (members.length != 5) {
    return new ReturnValue("Expression for grammar ({...}) should have 5 members, found "+members.length, true);
  }
 
  // Parse out state(s)
  if (!isSet(members[0])) {
    return new ReturnValue("Expression for defining internal states not a valid set: "+members[0], true);
  }
  var states = setToArray(members[0]); 

  for (var i=0; i<states.length; i++) {
    var state = states[i];
    if (!isValidState(state)) {
      return new ReturnValue("Invalid state, can only contain alphanumeric, whitespace and .,;:()-_ for: "+state, true);
    }
  }

  // Parse out alphabet
  if (!isSet(members[1])) {
    return new ReturnValue("Expression for defining alphabet of input values not a valid set: "+members[0], true);
  }
  var alphabet = setToArray(members[1]);
  
  for (var i=0; i<alphabet.length; i++) {
    var alph = alphabet[i];
    if (!isValidInput(alph)) {
      return new ReturnValue("Invalid alphabet entry, can only contain alphanumeric, whitespace and .,;:()-_ for: "+alph, true);
    }
  }

  // Parse out productionRule
  var productionRule = members[2];

  // See whether production rule exists in another grammar
  for (var i=0; i<grammars.length; i++) {
    var nextGrammar = grammars[i];

    // If has same transition function label but will not be replaced by this transition function, error
    if (nextGrammar.getTransitionFunctionsSymbol() == productionRule && nextGrammar.getVariableName() != variableName) {
      return new ReturnValue("Ambiguous error: Grammar "+nextGrammar.getVariableName()+" already exists with transition function label "+productionRule+".", true);
    }
  }

  // Parse out starting state
  var startingState = members[3];
  var isContain = false;
  for (var i=0; i<states.length; i++) {
    if (states[i] == startingState) {
      isContain = true;
      break;
    }
  }
  if (!isContain) {
    return new ReturnValue("Starting state "+startingState+" not included in set of states", true);
  }
  
  // Parse out final state(s)
  if (!isSet(members[4])) {
    return new ReturnValue("Expression for defining final states not a valid set: "+members[4], true);
  }
  var finalStates = setToArray(members[4]);

  for (var j=0; j<finalStates.length; j++) {
    isContain = false;
    for (var i=0; i<states.length; i++) {
      if (states[i] == finalStates[j]) {
        isContain = true;
        break;
      }
    }
    if (!isContain) {
      return new ReturnValue("Final state "+finalStates[j]+" not included in set of states", true);
    }
  }

  var grammar = new Grammar(variableName, states, alphabet, productionRule, startingState, finalStates);

  // See whether should replace
  for (var i=0; i<grammars.length; i++) {
    var nextGrammar = grammars[i];
    if (nextGrammar.getVariableName() == variableName) {
      // Replace old grammar with same name
      grammars[i] = grammar;
      return new ReturnValue("okay, replaced existing grammar", false);
    }
  }

  // Not found, new grammar variable set
  grammars.push(grammar);

  // Everything is good
  return new ReturnValue("okay", false);
}

/**
 * Checks that values contain legitimate characters.
 */
function isValidState(state) {
  return isValidValue(state);
}

/**
 * Checks that values contain legitimate characters.
 */
function isValidInput(input) {

  if (trim(input) == '*') {
    return true;
  }

  return isValidValue(input);
}

/**
 * Checks that values contain legitimate characters.
 */
function isValidValue(val) {
  var regex = /^[A-Z0-9\-_\.,;:\(\)\s]+$/i;
  return val.match(regex);
}

/**
 * transFunction(state, val) -> new_state
 */
function parseProductionRule(val) {

  var openParenIndex = val.indexOf('(');
  var closeParenIndex = val.indexOf(')');

  if (openParenIndex == -1 || closeParenIndex == -1 || (openParenIndex > closeParenIndex)) {
    return new ReturnValue("Transition function syntax error, parentheses missing or do not match.", true);
  }

  var transFunction = trim(val.substring(0, openParenIndex));
  
  // Make sure transition function exists
  var matchingGrammar = false;
  for (var i=0; i<grammars.length; i++) {
    var nextGrammar = grammars[i];
    if (nextGrammar.getTransitionFunctionsSymbol() == transFunction) {
      matchingGrammar = nextGrammar;
    }
  }
  if (!matchingGrammar) {
    return new ReturnValue("Transition function "+transFunction+" not found in existing grammar.", true);
  }
  
  var argumentsStr = trim(val.substring(openParenIndex+1, closeParenIndex));

  var arguments = argumentsStr.split(',');
  if (arguments.length != 2) {
    return new ReturnValue("Expecting two parameters to function, instead found "+arguments.length, true);
  }

  var inputState = trim(arguments[0]);
  var inputValue = trim(arguments[1]);
  
  // Make sure input state exists
  var isFound = false;
  var matchingInternalStates = matchingGrammar.getInternalStates();
  for (var i=0; i<matchingInternalStates.length; i++) {
    if (matchingInternalStates[i] == inputState) {
      isFound = true;
      break;
    } 
  }
  if (!isFound) {
    return new ReturnValue("Did not find input state "+inputState+" for matching grammar "+matchingGrammar.getVariableName(), true);
  }

  // Make sure input value is valid
  if (matchingGrammar.isAcceptAnyCharacter()) {
    if (inputValue.length != 1 && inputValue != 'sigma') {
      return new ReturnValue("Grammar "+matchingGrammar.getVariableName()+" only accepts characters, so "+inputValue+" not valid.", true);
    }
    if (!isValidInput(inputValue)) {
      return new ReturnValue("Invalid input, can only contain alphanumeric, whitespace and .,;:()-_ for: "+inputValue);
    }
  } else if (matchingGrammar.isAcceptAnyWord()) {
    if (!isValidInput(inputValue)) {
      return new ReturnValue("Invalid input, can only contain alphanumeric, whitespace and .,;:()-_ for: "+inputValue);
    }
  } else {
    isFound = false;
    if (inputValue == 'lambda' || inputValue == '*') {
      isFound = true;
    } else {
      for (var i=0; i<matchingGrammar.getInputAlphabet().length; i++) {
        if (matchingGrammar.getInputAlphabet()[i] == inputValue) {
          isFound = true;
          break;
        }
      }
    }
    if (!isFound) {
      return new ReturnValue("Matching grammar "+matchingGrammar.getVariableName()+" does not accept input "+inputValue, true);
    }
  }

  var expressionSides = val.split("->");

  if (expressionSides.length != 2) {
    return new ReturnValue("Transition function syntax error, expecting right hand side to be preceded by one ->", true);
  }

  var outputState = trim(expressionSides[1]);

  // Make sure output state exists
  isFound = false;
  for (var i=0; i<matchingInternalStates.length; i++) {
    if (matchingInternalStates[i] == outputState) {
      isFound = true;
      break;
    } 
  }
  if (!isFound) {
    return new ReturnValue("Did not find output state "+outputState+" for matching grammar "+matchingGrammar.getVariableName(), true);
  }

  var pr = new ProductionRule(inputState, inputValue, outputState);
  matchingGrammar.addTransitionFunction(pr);

  return new ReturnValue("okay", false);
}

/**
 * L(grammar) ? val
 */
function parseQuery(val) {
  var sides = val.split('?');
  if (sides.length != 2) {
    return new ReturnValue("Query syntax error: expected one question mark, instead found "+(sides.length-1));
  }

  var inputString = trim(sides[1]);

  var languageString = trim(sides[0]);

  // Very predictable: L(grammar)
  if (languageString.charAt(0) != 'L' || languageString.charAt(1) != '(' || languageString.charAt(languageString.length-1) != ')') {
    return new ReturnValue("Query syntax error: language "+languageString+" does not start with L( and end with ).");
  }

  // Extract the grammar from the language
  var grammar = trim(languageString.substring(2,languageString.length-1));

  // Find matching grammar or return error message
  var matchingGrammar = false;
  for (var i=0; i<grammars.length; i++) {
    if (grammars[i].getVariableName() == grammar) {
      matchingGrammar = grammars[i];
      break;
    }
  }
  if (!matchingGrammar) {
    return new ReturnValue("Grammar "+grammar+" not found. No language to query.");
  }

  // Grammar found. Time to do the magic. Current states includes only initial state.
  var states = new Array();
  states.push(matchingGrammar.getStartingState());

  // Quick reference to all transition functions/production rules for grammar
  var prs = matchingGrammar.getTransitionFunctions();

  // Tokenize the input by characters or words
  var inputTokens = new Array();
  if (matchingGrammar.isAcceptAnyWord()) {
    inputTokens = splitStringIntoWords(inputString);
  } else {
    for (var i=0; i<inputString.length; i++) {
      inputTokens.push(inputString.charAt(i));
    }
  }

  // >>>>> For each token in input stream <<<<<
  for (var i=0; i<inputTokens.length; i++) {

    var token = inputTokens[i];

    // Machine halts if no states
    if (states.length == 0) {
      break;
    }

    // First, check lambda functions. Where can we get to from where we are?

    states = checkLambdaTransitionsForNewStates(states, matchingGrammar);

    var nextStates = new Array();

    // Check every state to see if continues or halts on input token
    for (var stateIndex = 0; stateIndex < states.length; stateIndex++) {
      var state = states[stateIndex];
      
      // Check against all transition functions
      for (var pIndex = 0; pIndex<prs.length; pIndex++) {
        var pr = prs[pIndex];
        
        // Did we find a transition function?
        if (pr.getSourceNode() == state && (pr.getTransitionValue() == token || pr.getTransitionValue() == '*')) {
          var dest = pr.getDestNode();

          // We need to determine if dest is already in list of next states
          var nextContains = false;
          for (var nextIndex=0; nextIndex<nextStates.length; nextIndex++) {
            if (nextStates[nextIndex] == dest) {
              nextContains = true;
              break;
            }
          }
          if (!nextContains) {
            nextStates.push(dest);
          }
        } // Find a matching transition function?
      } // Checking next transition function
    } // Checking every state with current token

    // Swap arrays so have current states
    states = nextStates;
  } // Checking each token

  // Check one last time for lamda functions
  states = checkLambdaTransitionsForNewStates(states, matchingGrammar);

  // Is there a final state?
  var finalStates = matchingGrammar.getFinalStates();
  for (var i=0; i<states.length; i++) {
    for (var j=0; j<finalStates.length; j++) {
      if (finalStates[j] == states[i]) {
        return new ReturnValue("true", false);
      }
    }
  }
  return new ReturnValue("false", false);
}

/**
 *
 */
function splitStringIntoWords(languageString) {
   // Collapse white space...
   languageString = trim(languageString.replace(/\s+/g, ' '));

   var words = languageString.split(" ");
   var tokens = new Array();

   // For each candidate work
   for (var i=0; i<words.length; i++) {
    
     var wasSplit = false;
     var word = words[i];

     // Go through each character to see whether need to split based on punctuation
     var startIndex = 0;
     var c = 0;
     for (c=0; c<word.length; c++) {
       var char = word.charAt(c);
       if (isPunctuation(char)) {
         if (startIndex == c) {
           tokens.push(char);
         } else {
           tokens.push(word.substring(startIndex,c));
           tokens.push(char);
         }

         // Set start to remaining string so not re-adding tokens
         startIndex = c+1;
         wasSplit = true;
       }
     }

     if (!wasSplit) {
       tokens.push(word);
     } else {
       // Put the last token from split string if not all whitespace
       var lastToken = trim(word.substring(startIndex,c));
       if (lastToken != '') {
         tokens.push(lastToken);
       }
     }
   } // For each word

   return tokens;
}

/**
 *
 */
function isPunctuation(char) {
  if (char.length != 1) {
    alertBug('isPunctuation('+char+') : input should be single character.');
  }

  var regex = /[.,;:\(\)\s]/i;
  return char.match(regex);
}

/**
 *
 */
function checkLambdaTransitionsForNewStates(states, grammar) {
  var prs = grammar.getTransitionFunctions();

  // At the end, need to determine whether a new state was found. If it
  // was, we need to start over so can keep following lambda functions
  var wasNewStateFound = false;

  // Using every state our machine is currently in...
  for (var stateIndex=0; stateIndex<states.length; stateIndex++) {

    // Speed up: if all states in collection, break. Nothing to do.
    if (states.length == grammar.getInternalStates().length) {
      break;
    }

    var state = states[stateIndex];

    // ... check against every production rule/transition function that is a lambda function
    for (var prIndex = 0; prIndex<prs.length; prIndex++) {
      var pr = prs[prIndex];

      // Is this a lambda function for this state?
      if (pr.getSourceNode() == state && pr.getTransitionValue() == 'lambda') {

        // Do not add same node twice. If already in collection, skip
        var contains = false;
        for (var c=0; c<states.length; c++) {
          if (states[c] == pr.getDestNode()) {
            contains = true;
            break;
          }
        }
          
        // We found a new state using lambda transition
        if (!contains) {
          states.push(pr.getDestNode());
          wasNewStateFound = true;
        }
      }
    }
  }

  if (wasNewStateFound) {
    return checkLambdaTransitionsForNewStates(states, grammar);
  }

  return states;
} // checkLambdaTransitionsForNewStates

/**
 *
 */
function isSetGrammar(inputValue) {
  return inputValue.match("=");
}

/**
 *
 */
function isSetProductionRule(inputValue) {
  return inputValue.match("->");
}

/**
 *
 */
function isQuery(inputValue) {
  return inputValue.match("\\?");
}

/**
 * Parses out members of a set from a set and returns as an array. For example:
 * {1, 2, {3, 4}} 
 * will return array:
 * [1, 2, {3, 4}]
 */
function setToArray(val) {
  // Value keeps track of inner sets
  var innerBracketCount = 0;

  // Assert that starts with { and ends with }
  if (!isSet(val)) {
    alertBug("Expression must start with a { and end with a } to set a grammar, for set in setToArray("+val+")", true);
  }

  var startPos = 1;
  var tokens = new Array();
  for (var i=1; i<val.length; i++) {

    var getToken = false;

    // End of item!
    if (val.charAt(i) == ',' && innerBracketCount == 0) {
      getToken = true;
    } 

    // Start inner set
    else if (val.charAt(i) == '{') {
      innerBracketCount++;
    }

    // End inner set
    else if (val.charAt(i) == '}') {

      // End of set!
      if (innerBracketCount == 0) {
        getToken = true;
      } 
      // End of inner set
      else {
        innerBracketCount--;
      }
    }

    if (getToken) {
      // Special case: if zero size, empty string
      if (startPos == i) {
        tokens.push('');
      } else {
        var token = trim(val.substring(startPos, i));
        tokens.push(token);
      }

      // Next token starts after comma
      startPos = i+1;
    }
  }

  return tokens;
}

/**
 *
 */
function arrayToSet(array) {
  var str = '';
  for (var i=0; i<array.length; i++) {
    str += array[i];
    if (i < array.length-1) {
      str += ', ';
    }
  }
  return "{"+str+"}";
}

/**
 *
 */
function isSet(str) {
  var val = trim(str);

  // Trimmed value must start and end with curly brackets
  if (val.charAt(0) != '{' || val.charAt(val.length-1) != '}') {
    return false;
  }
  // Must have matching count of curly brackets, and left brackets must always be greater than right
  var leftCount = 0;
  var rightCount = 0;

  // Don't check last value: we already know it is a }
  for (var i=0; i<val.length - 1; i++) {
    if (val.charAt(i) == '{') {
      leftCount++;
    } else if (val.charAt(i) == '}') {
      rightCount++;
    }
    if (leftCount <= rightCount) {
      return false;
    }
  }

  // Increment right curly bracket count for final }
  rightCount++;

  if (leftCount != rightCount) {
    return false;
  }

  return true;
}

function alertArray(message, array) {
  message+="' array: ";
  for (var i=0; i<array.length; i++) {
    message = message + array[i]+' ';
  }
  alert(message);
}

function alertBug(message) {
  alert("An error has happened, which is almost certainly my (the developer's) fault:\n\n"+message+"\n\nIf you are willing, please notify me at bryanesmith@gmail.com with this information to fix. Thank you!");

  alert('Script killed due to error. You can refresh the page to try again.\n\nIf you are willing, please submit the follow to bryanesmith@gmail.com:\n\n'+message);

  // Throw the error
  throw message;
}

/**
 *
 */
function trim(str) {
  return str.replace(/^\s+|\s+$/g, '');
}