Quick program to find out if a word can be created by a set of rules (originally to test if the context sensitive grammar to the language {a^n b^n c^n|n>0} is correct)

isWordInKontextsensitiveGrammar.js

/**
 * Extremely and not at all fast way to find if a given word can be created via a given set of rules
 *
 * Can be used to check if a word can be created with a formal grammar.
 * Replace rule set and input to find out.
 *
 *
 * This script does not check if you are using only specific variables/symbols.
 * It just checks if the word can be derived to the start symbol.
 *
 * Run it with node.js and at least 8GB of RAM :D (node nameOfThisFile.js)
 */

/*
 * Your input, change to your input, start symbol and rule set
 */

const input = 'aaaSBCBCBC' // abc, aabbcc
const startSymbol = 'S'
const rules = [
  'S->aBC|aSBC',
  'CB->HB',
  'HB->HC',
  'HC->BC',
  'aB->ab',
  'bB->bb',
  'bC->bc',
  'cC->cc'
]

/*
 * The code (do not change besides if you know what you are doing)
 */

const convertRules = (rules) => {
  let convertedRules = []
  for (let i = 0; i < rules.length; i++) {
    const leftRightSide = rules[i].split('->')
    const rightSide = leftRightSide[1].split('|')
    convertedRules.push([leftRightSide[0], rightSide])
  }
  return convertedRules
}

const getRulesThatCanBeApplied = (input, rules) => {
  let leftRules = []
  for (let j = 0; j < rules.length; j++) {
    for (let k = 0; k < rules[j][1].length; k++) {
      if (input.includes(rules[j][1][k])) {
        leftRules.push([rules[j][0], rules[j][1][k]])
      }
    }
  }
  return leftRules
}

const getSubtreePromises = (input, startSymbol, rules, history, leftRules) => {
  let promises = [leftRules.length]
  for (let i = 0; i < leftRules.length; i++) {
    let tempHistory = history.slice()
    const lastIndex = input.lastIndexOf(leftRules[i][1])
    const tempInput = input.substring(0, lastIndex) +
     input.substring(lastIndex).replace(leftRules[i][1], leftRules[i][0])
    tempHistory.push([tempInput, leftRules[i]])
    promises[i] = tryToDeriveInput(tempInput, startSymbol, rules, tempHistory)
  }
  return promises
}

const reflect = p => p.then(v => ({v, status: 'fulfilled' }), e => ({e, status: 'rejected' }))

const tryToDeriveInput = (input, startSymbol, rules, history = []) => {
  return new Promise((resolve, reject) => {
    // check if start symbol is reached
    if (input === startSymbol) {
      resolve(history)
    }
    // get rules that can currently be applied
    const leftRules = getRulesThatCanBeApplied(input, rules)
    // get all sub trees as a promise array
    const subPromises = getSubtreePromises(input, startSymbol, rules, history, leftRules)
    // check if any of the promises was not false
    Promise.all(subPromises.map(reflect)).then(results => {
      // filter results to only get the resolved entries
      const fulfilled = results.filter(x => x.status === 'fulfilled')
      if (fulfilled.length !== 0) {
        // if there are any return the first one
        resolve(fulfilled[0].v)
      } else {
        // if not reject
        reject(new Error('Subtree found no solution'))
      }
    })
  })
}

const solveInput = (input, startSymbol, rules) => {
  // debug by printing input
  console.log('Input:', input)
  console.log('Start symbol:', startSymbol)
  console.log('Rules:')
  for (let i = 0; i < rules.length; i++) {
    console.log('  -', rules[i][0], ' -> ', rules[i][1].join(' | '))
  }
  // search for solution
  tryToDeriveInput(input, startSymbol, rules)
    .then(solution => {
      console.log('-------------------------------------------------------------')
      console.log('Solution found, word can be built with grammar in', solution.length, 'steps')
      console.log('Input:\n\t=>', input)
      for (let i = solution.length - 1; i >= 0; i--) {
        console.log('Step #' + (solution.length - i) + ':', 'Replace:', solution[i][1][0],
          'with', solution[i][1][1] + '\n\t=>', solution[i][0])
      }
    })
    .catch(error => {
      console.log('-------------------------------------------------------------')
      console.error('Solution not found (' + error.message + ')')
    })
}

solveInput(input, startSymbol, convertRules(rules))