lib/parser.js
function dfsHelper(states, root, state, depth, tokens) {
  var edges;

  // Base case: we finished the root rule
  if (state === root.origin && depth === root.rule.length) {
    return [];
  }

  // If the current production symbol is a terminal
  if (root.rule[depth] instanceof RegExp) {
    if (root.rule[depth].test(tokens[state])) {
      let subMatch = dfsHelper(states, root, state + 1, depth + 1, tokens);

      if (subMatch) {
        return [tokens[state]].concat(subMatch);
      }
    }
    return null;
  } else if (typeof root.rule[depth] === 'string') {
    if (root.rule[depth] === tokens[state]) {
      let subMatch = dfsHelper(states, root, state + 1, depth + 1, tokens);

      if (subMatch) {
        return [tokens[state]].concat(subMatch);
      }
    }
    return null;
  }

  // Otherwise, it must be a non-terminal
  edges = states[state]
    .filter((item) => item.rule.lhs === root.rule[depth])
    .map((item) => {
      let subMatch = dfsHelper(states, root, item.origin, depth + 1, tokens);

      if (subMatch) {
        return [{
          item    : item.rule,
          children: dfsHelper(states, item, state, 0, tokens)
        }].concat(subMatch);
      }
      return null;
    })
    .filter((list) => list);

  if (edges.length > 1) {
    let diffs = edges.filter(
      (tree) => JSON.stringify(tree) !== JSON.stringify(edges[0])
    );

    if (diffs.length > 0) {
      //console.log('Ambiguity\n' + JSON.stringify(edges, null, 2));
      console.log('Ambiguous rules');
    }
  }

  return edges[0];
}
function dfsHelper(states, root, state, depth, tokens) {
  var edges;

  // Base case: we finished the root rule
  if (state === root.origin && depth === root.rule.length) {
    return [];
  }

  // If the current production symbol is a terminal
  if (root.rule[depth] instanceof RegExp) {
    if (root.rule[depth].test(tokens[state])) {
      let subMatch = dfsHelper(states, root, state + 1, depth + 1, tokens);

      if (subMatch) {
        return [tokens[state]].concat(subMatch);
      }
    }
    return null;
  } else if (typeof root.rule[depth] === 'string') {
    if (root.rule[depth] === tokens[state]) {
      let subMatch = dfsHelper(states, root, state + 1, depth + 1, tokens);

      if (subMatch) {
        return [tokens[state]].concat(subMatch);
      }
    }
    return null;
  }

  // Otherwise, it must be a non-terminal
  edges = states[state]
    .filter((item) => item.rule.lhs === root.rule[depth])
    .map((item) => {
      let subMatch = dfsHelper(states, root, item.origin, depth + 1, tokens);

      if (subMatch) {
        return [{
          item    : item.rule,
          children: dfsHelper(states, item, state, 0, tokens)
        }].concat(subMatch);
      }
      return null;
    })
    .filter((list) => list);

  if (edges.length > 1) {
    let diffs = edges.filter(
      (tree) => JSON.stringify(tree) !== JSON.stringify(edges[0])
    );

    if (diffs.length > 0) {
      //console.log('Ambiguity\n' + JSON.stringify(edges, null, 2));
      console.log('Ambiguous rules');
    }
  }

  return edges[0];
}
function dfsHelper ( states , root , state , depth , tokens ) { var edges ; // Base case: we finished the root rule if ( state === root . origin && depth === root . rule . length ) { return [ ] ; } // If the current production symbol is a terminal if ( root . rule [ depth ] instanceof RegExp ) { if ( root . rule [ depth ] . test ( tokens [ state ] ) ) { let subMatch = dfsHelper ( states , root , state + 1 , depth + 1 , tokens ) ; if ( subMatch ) { return [ tokens [ state ] ] . concat ( subMatch ) ; } } return null ; } else if ( typeof root . rule [ depth ] === 'string' ) { if ( root . rule [ depth ] === tokens [ state ] ) { let subMatch = dfsHelper ( states , root , state + 1 , depth + 1 , tokens ) ; if ( subMatch ) { return [ tokens [ state ] ] . concat ( subMatch ) ; } } return null ; } // Otherwise, it must be a non-terminal edges = states [ state ] . filter ( ( item ) => item . rule . lhs === root . rule [ depth ] ) . map ( ( item ) => { let subMatch = dfsHelper ( states , root , item . origin , depth + 1 , tokens ) ; if ( subMatch ) { return [ { item : item . rule , children : dfsHelper ( states , item , state , 0 , tokens ) } ] . concat ( subMatch ) ; } return null ; } ) . filter ( ( list ) => list ) ; if ( edges . length > 1 ) { let diffs = edges . filter ( ( tree ) => JSON . stringify ( tree ) !== JSON . stringify ( edges [ 0 ] ) ) ; if ( diffs . length > 0 ) { //console.log('Ambiguity\n' + JSON.stringify(edges, null, 2)); console . log ( 'Ambiguous rules' ) ; } } return edges [ 0 ] ; }
Recursive function that explores a specific earley item, constructs the parse
tree for it, then sends it up the chimney!

@function dfsHelper
@param {state[]} states - Set of lists of earley items
@param {earleyItem} root - Current earley item being explored, a tree for
which is to be constructed
@param {number} state - Current state/index of our current position in the
list of tokens
@param {number} depth - Index/position in the root's rule (RHS). In other
words, index of the next symbol to match or explore
@param {string[]} tokens - List of input tokens
@return {null|object[]} Null if the search provided NO results for the
given node, or a list of tree nodes, which are the respective parse trees
of each of the root rule's RHS symbols
Recursive function that explores a specific earley item constructs the parse tree for it then sends it up the chimney!