context free grammar parser. example.

context-free-grammar-example.js

// context free grammar parser. example.

// Alphabet: ()[]E
// E = nonterminal
/* rules:

E -> (E)
E -> [E]
E -> EE
E ->

*/

const T_BEGIN_BR = '(';
const T_END_BR = ')';
const T_BEGIN_BS = '[';
const T_END_BS = ']';
const NT_E = 'E';

function nodeE(str, start) {
  let idx = 0;
  let char;
  const len = str.length;
  const nodes = [];
  let node = null;
  
  while(idx < len) {
    char = str[idx];
    
    if (char === T_BEGIN_BR || char === T_BEGIN_BS) {
      let nnode = {
        source: '',
        end: start + idx,
        parent: null,
        start: start + idx,
        nodes: []
      };
      
      if (node) {
        nnode.parent = node;
        node.nodes.push(nnode);
        node = nnode;
      } else {
        node = nnode;
        nodes.push(nnode);
      }
      
    } else if (char === T_END_BR || char === T_END_BS) {
      if (!node) {
        throw new SyntaxError('unexpected char "' + char + '" at ' + (start + idx));
      }
      
      const startChar = str[(node.start - start)];
      const expectedEndChar = startChar === T_BEGIN_BR ? T_END_BR : T_END_BS;
      
      if (expectedEndChar !== char) {
        throw new SyntaxError('unexpected char "' + char + '" at ' + (start + idx));
      }
      
      node.end = start + idx;
      node.source = str.substr(node.start, node.end + 1 - node.start);
      
      if (node.parent) {
        node = node.parent;
      } else {
        node = null;
      }
    }
    
    idx++;
  }
  
  if (node !== null) {
    const unexpectedChar = str[(node.start - start)];
    throw new SyntaxError('unexpected char "' + unexpectedChar + '" at ' + node.start);
  }
  
  return nodes;
}

function line(str) {
  const nodes = nodeE(str, 0);
  console.dir(nodes, { depth: null });
}

line('()[]');