full.js

class MachineNode {
  static create(node) {
    switch (node.type) {
      case 'group':
        return new GroupNode(node.g);
      case 'char':
        return new CharacterNode(node.c);
      case 'alt':
        return new AlternativeNode(node.l, node.r);
      case 'list':
        return new ListNode(node.d);
      default:
        return new MachineNode();
    }
  }
  
  process(input) {
    return (input.length == 0);
  }
}

class StringMatchMachine extends MachineNode {
  constructor(pattern) {
    super();
    console.log('Creating StringMatchMachine');
    this.root = MachineNode.create(pattern);
  }
  
  process(input) {
    return this.root.process(input);
  }
}

class ListNode extends MachineNode {
  constructor(d) {
    super();
    console.log('Creating ListNode');
    this.d = d.map(MachineNode.create);
  }
  
  process(input) {
    console.log('ListNode received', input);
    let next = input;
    for (let node of this.d) {
      if ((next = node.process(next)) === false) {
        return false;
      }
    }
    
    return true;
  }
}

class AlternativeNode extends MachineNode {
  constructor(a, b) {
    super();
    console.log('Creating AlternativeNode');
    this.a = MachineNode.create(a);
    this.b = MachineNode.create(b);
  }
  
  process(input) {
    let ra = this.a.process(input);
    if (ra !== false) {
      console.log('AlternativeNode', input, 'matched a');
      return ra;
    }
    
    let rb = this.b.process(input);
    if (rb !== false) {
      console.log('AlternativeNode', input, 'matched b');
      return rb;
    }
    
    return false;
  }
}

class CharacterNode extends MachineNode {
  constructor(c) {
    super();
    console.log('Creating CharacterNode');
    this.c = c;
  }
  
  process(input) {
    if (input[0] === this.c) {
      return input.substr(1);
    } else {
      return false;
    }
  }
}

class GroupNode extends MachineNode {
  constructor(child) {
    super();
    console.log('Creating GroupNode');
    this.child = MachineNode.create(child);
  }
  
  process(input) {
    let r = this.child.process(input);
    console.log('GroupNode processed', input, r);
    return r;
  }
}

// ast for '(aaaa|(abab|aacc))'
let ast = {
   "type": "group",
   "g": {
      "type": "alt",
      "l": {
         "type": "list",
         "d": [
            {
               "type": "char",
               "c": "a"
            },
            {
               "type": "char",
               "c": "a"
            },
            {
               "type": "char",
               "c": "a"
            },
            {
               "type": "char",
               "c": "a"
            }
         ]
      },
      "r": {
         "type": "group",
         "g": {
            "type": "alt",
            "l": {
               "type": "list",
               "d": [
                  {
                     "type": "char",
                     "c": "a"
                  },
                  {
                     "type": "char",
                     "c": "b"
                  },
                  {
                     "type": "char",
                     "c": "a"
                  },
                  {
                     "type": "char",
                     "c": "b"
                  }
               ]
            },
            "r": {
               "type": "list",
               "d": [
                  {
                     "type": "char",
                     "c": "a"
                  },
                  {
                     "type": "char",
                     "c": "a"
                  },
                  {
                     "type": "char",
                     "c": "c"
                  },
                  {
                     "type": "char",
                     "c": "c"
                  }
               ]
            }
         }
      }
   }
};

let fsm = new StringMatchMachine(ast);
let testStrings = ['aaaa', 'abab', 'cccc'];
for (let test of testStrings) {
  console.log(test, fsm.process(test) ? 'matches' : 'doesn\'t match');
}

grammar.peg

expr 
  = g:group { return g; }
  / l:list { return l; }

list
  = d:char+ { return {type: 'list', d: d}; }

group = '(' g:group_body ')' { return {type: 'group', g: g}; }

group_body 
  = alt
  / expr

alt = l:expr '|' r:expr { return {type: 'alt', l: l, r: r}; }

char = c:[a-z] { return {type: 'char', c: c}; }

input-ast.json

{
   "type": "group",
   "g": {
      "type": "alt",
      "l": {
         "type": "list",
         "d": [
            {
               "type": "char",
               "c": "a"
            },
            {
               "type": "char",
               "c": "a"
            },
            {
               "type": "char",
               "c": "a"
            },
            {
               "type": "char",
               "c": "a"
            }
         ]
      },
      "r": {
         "type": "group",
         "g": {
            "type": "alt",
            "l": {
               "type": "list",
               "d": [
                  {
                     "type": "char",
                     "c": "a"
                  },
                  {
                     "type": "char",
                     "c": "b"
                  },
                  {
                     "type": "char",
                     "c": "a"
                  },
                  {
                     "type": "char",
                     "c": "b"
                  }
               ]
            },
            "r": {
               "type": "list",
               "d": [
                  {
                     "type": "char",
                     "c": "a"
                  },
                  {
                     "type": "char",
                     "c": "a"
                  },
                  {
                     "type": "char",
                     "c": "c"
                  },
                  {
                     "type": "char",
                     "c": "c"
                  }
               ]
            }
         }
      }
   }
}

input.txt

(aaaa|(abab|aacc))

nodes.js

class MachineNode {
  static create(node) {
    switch (node.type) {
      case 'group':
        return new GroupNode(node.g);
      case 'char':
        return new CharacterNode(node.c);
      case 'alt':
        return new AlternativeNode(node.l, node.r);
      case 'list':
        return new ListNode(node.d);
      default:
        return new MachineNode();
    }
  }
  
  process(input) {
    return (input.length == 0);
  }
}

class StringMatchMachine extends MachineNode {
  constructor(pattern) {
    super();
    console.log('Creating StringMatchMachine');
    this.root = MachineNode.create(pattern);
  }
  
  process(input) {
    return this.root.process(input);
  }
}

class ListNode extends MachineNode {
  constructor(d) {
    super();
    console.log('Creating ListNode');
    this.d = d.map(MachineNode.create);
  }
  
  process(input) {
    console.log('ListNode received', input);
    let next = input;
    for (let node of this.d) {
      if ((next = node.process(next)) === false) {
        return false;
      }
    }
    
    return true;
  }
}

class AlternativeNode extends MachineNode {
  constructor(a, b) {
    super();
    console.log('Creating AlternativeNode');
    this.a = MachineNode.create(a);
    this.b = MachineNode.create(b);
  }
  
  process(input) {
    let ra = this.a.process(input);
    if (ra !== false) {
      console.log('AlternativeNode', input, 'matched a');
      return ra;
    }
    
    let rb = this.b.process(input);
    if (rb !== false) {
      console.log('AlternativeNode', input, 'matched b');
      return rb;
    }
    
    return false;
  }
}

class CharacterNode extends MachineNode {
  constructor(c) {
    super();
    console.log('Creating CharacterNode');
    this.c = c;
  }
  
  process(input) {
    if (input[0] === this.c) {
      return input.substr(1);
    } else {
      return false;
    }
  }
}

class GroupNode extends MachineNode {
  constructor(child) {
    super();
    console.log('Creating GroupNode');
    this.child = MachineNode.create(child);
  }
  
  process(input) {
    let r = this.child.process(input);
    console.log('GroupNode processed', input, r);
    return r;
  }
}

output.txt

Creating StringMatchMachine
Creating GroupNode
Creating AlternativeNode
Creating ListNode
Creating CharacterNode
Creating CharacterNode
Creating CharacterNode
Creating CharacterNode
Creating GroupNode
Creating AlternativeNode
Creating ListNode
Creating CharacterNode
Creating CharacterNode
Creating CharacterNode
Creating CharacterNode
Creating ListNode
Creating CharacterNode
Creating CharacterNode
Creating CharacterNode
Creating CharacterNode
ListNode received aaaa
AlternativeNode aaaa matched a
GroupNode processed aaaa true
aaaa matches
ListNode received abab
ListNode received abab
AlternativeNode abab matched a
GroupNode processed abab true
AlternativeNode abab matched b
GroupNode processed abab true
abab matches
ListNode received cccc
ListNode received cccc
ListNode received cccc
GroupNode processed cccc false
GroupNode processed cccc false
cccc doesn't match

test.js

let fsm = new StringMatchMachine(ast);
let testStrings = ['aaaa', 'abab', 'cccc'];
for (let test of testStrings) {
  console.log(test, fsm.process(test) ? 'matches' : 'doesn\'t match');
}