A little parser 1. parsing

little-parser-i.js

/* constants for types of expression */
const exps = {
  Plus: "Plus",
  Mult: "Mult",
  Power: "Power",
  NumOrGroup: "NumOrGroup",
  NumLiteral: "NumLiteral",
};

/* get last elem of array, undefined if array is empty */
function last(arr) {
  return arr[arr.length - 1];
}

/* is the string all digits? */
function isDigits(s) {
  for (let c of s) {
    if (!".0123456789".includes(c)) {
      return false;
    }
  }

  return true;
}

/* split a string '12+13' into ['12', '+', '13'] */
function verySimpleLexer(s) {
  let results = [];
  for (let c of s) {
    if (isDigits(c) && last(results) && isDigits(last(results))) {
      /* add character to a number we're building */
      results[results.length - 1] += c;
    } else if (c.trim().length > 0) {
      /* add new item, if it isn't whitespace */
      results.push(c);
    }
  }

  return results;
}

/* parse a list of tokens */
function parseTotal(remaining) {
  /* try each type of expression, see if it can consume entire input */
  for (let exprType in exps) {
    let [gotRemaining, gotResult] = parseRemaining(remaining, exprType);
    if (gotResult && gotRemaining.length === 0) {
      return gotResult;
    }
  }

  throw new Error("Could not parse the expression.");
}

/*
implement these rules:
    expPlus -> expMult + expMult + expMult...
    expMult -> expPower * expPower * expPower...
    expPower -> expNumOrGroup ^ expNumOrGroup ^ expNumOrGroup...
    expNumOrGroup -> numLiteral or ( expPlus )
    numLiteral -> 0123456789*
*/

/* recursively parse the tokens. */
function parseRemaining(remaining, exprType) {
  /* see if the remaining tokens can be recognized as a certain exprType */
  if (exprType === exps.Plus) {
    return parseOperation(remaining, "+", exps.Plus, exps.Mult);
  } else if (exprType === exps.Mult) {
    return parseOperation(remaining, "*", exps.Mult, exps.Power);
  } else if (exprType === exps.Power) {
    return parseOperation(remaining, "^", exps.Power, exps.NumOrGroup);
  } else if (exprType === exps.NumOrGroup) {
    return parseNumOrGroup(remaining);
  } else if (exprType === exps.NumLiteral) {
    return parseNumLiteral(remaining);
  } else {
    throw new Error("Unknown exprType " + exprType);
  }
}

/* expPlus, expMult, and expPower all work the same way
they can accept either 'exprChild + exprChild + ...' or 'exprChild'  */
function parseOperation(remaining, operator, exprParent, exprChild) {
  let newResult = { type: exprParent, parts: [operator] };
  [remaining, results] = parseRemaining(remaining, exprChild);
  if (results) {
    while (true) {
      newResult.parts.push(results);
      if (remaining[0] && remaining[0] === operator) {
        /* the next token is + so keep consuming */
        [remaining, results] = parseRemaining(remaining.slice(1), exprChild);
      } else {
        /* we don't see a + */
        break;
      }
    }

    return [remaining, newResult];
  } else {
    /* the input didn't start with an exprChild */
    return [null, null];
  }
}

/* accepts either a num literal or an expression in parentheses */
function parseNumOrGroup(remaining) {
  if (remaining.length && isDigits(remaining[0])) {
    let [gotRemaining, gotResult] = parseRemaining(remaining, exps.NumLiteral);
    if (gotResult) {
      /* we got a num literal */
      let newResult = { type: exps.NumOrGroup, parts: [gotResult] };
      return [gotRemaining, newResult];
    }
  } else if (remaining.length && remaining[0] === "(") {
    let [gotRemaining, gotResult] = parseRemaining(
      remaining.slice(1),
      exps.Plus
    );
    if (gotResult && gotRemaining.length && gotRemaining[0] === ")") {
      /* we got a ( expPlus ) */
      let newResult = { type: exps.NumOrGroup, parts: [gotResult] };
      return [gotRemaining.slice(1), newResult];
    }
  }

  /* could not be parsed as a NumOrGroup */
  return [null, null];
}

/* accepts a num literal */
function parseNumLiteral(remaining) {
  if (remaining.length && isDigits(remaining[0])) {
    /* first token is a num literal */
    let newResult = { type: exps.NumLiteral, parts: [remaining[0]] };
    return [remaining.slice(1), newResult];
  }

  /* could not be parsed as a NumOrGroup */
  return [null, null];
}