title: Is there an iterator-like pattern for parsing using recursive descent?
body: <p>I have a recursive descent parser <a href="https://github.com/grammarjs/recursive-parser/blob/master/index.js#L33" rel="nofollow noreferrer">here</a>:</p>
  
  <pre><code>Parser.prototype.parse = function(str){
    var val = this.visitExpression(str, this.grammar.root, this.grammar);
    this.reset();
    return val;
  };
  
  /**
   * Parse expression.
   *
   * @param {String} str
   * @param {Expression} exp
   * @param {Grammar} grammar
   *
   * @api private
   */
  
  Parser.prototype.visitExpression = function(str, exp, grammar){
    var val;
    this.expression = exp;
  
    for (var i = 0, n = exp.rules.length; i &lt; n; i++) {
      val = this.visitRule(str, exp.rules[i], grammar, exp);
      // blank string '' also counts
      if (null != val) return val;
    }
  };
  
  /**
   * Parse rule.
   *
   * @param {String} str
   * @param {Rule} rule
   * @param {Grammar} grammar
   *
   * @api private
   */
  
  Parser.prototype.visitRule = function(str, rule, grammar, exp){
    var pos = this.pos;
    var args = [];
    var val;
    this.rule = rule;
  
    for (var i = 0, n = rule.symbols.length - 1; i &lt; n; i++) {
      val = this.visitSymbol(str, rule.symbols[i], grammar, exp);
      if (null == val &amp;&amp; rule.symbols[i].matchAndIgnore) {
        args.push(val);
        continue;
      }
      // if we didnt get a value, and we don't have a flag to skip if not match
      if (null == val &amp;&amp; !rule.symbols[i].notMatchAndIgnore) {
        this.pos = pos; // reset
        return;
      }
      args.push(val);
    }
  
    return rule.apply(this, args);
  };
  
  /**
   * Parse symbol.
   *
   * @param {String} str
   * @param {Symbol} symbol
   * @param {Grammar} grammar
   *
   * @api private
   */
  
  Parser.prototype.visitSymbol = function(str, symbol, grammar, parentExp){
    this.symbol = symbol;
    if (symbol.isExpression) {
      return this.parseExpression(symbol, str, grammar, parentExp);
    } else if (symbol.isString) {
      return this.parseString(symbol, str);
    } else if (symbol.isRegExp) {
      return this.parseRegExp(symbol, str);
    }
  };
  
  /**
   * Parse expression.
   *
   * @param {Symbol} symbol
   * @param {String} str
   * @param {Object} parser
   * @api private
   */
  
  Parser.prototype.parseExpression = function(symbol, str, grammar, parentExp){
    var prev = this.expression;
    var exp = grammar.rules[symbol.expression];
    if (!exp) throw error("Expression '%s' is undefined (referenced in '%s')", symbol.expression, parentExp.name);
  
    if (symbol.many) {
      var pos = this.pos;
      var res = [];
      var val;
  
      while (val = this.visitExpression(str, exp, grammar)) {
        res.push(val);
      }
  
      this.expression = prev;
  
      if (symbol.onePlus &amp;&amp; !res.length) {
        this.pos = pos;
        return;
      }
      return res;
    } else if (symbol.optional) {
      var res = this.visitExpression(str, exp, grammar) || '';
      this.expression = prev;
      return res;
    } else {
      var pos = this.pos;
      var res = this.visitExpression(str, exp, grammar);
      if (res &amp;&amp; symbol.matchAndIgnore) {
        this.pos = pos;
        res = null;
      }
      this.expression = prev;
      return res;
    }
  };
  
  /**
   * Parse string.
   *
   * @param {Symbol} symbol
   * @param {String} str
   * @api private
   */
  
  Parser.prototype.parseString = function(symbol, str){
    if (symbol.val === str.substr(this.pos, symbol.val.length)) {
      this.pos += symbol.val.length;
      return symbol.val;
    }
  };
  
  /**
   * Parse RegExp.
   *
   * @param {Symbol} symbol
   * @param {String} str
   * @api private
   */
  
  Parser.prototype.parseRegExp = function(symbol, str){
    if (symbol.many) {
      var pos = this.pos;
      var res = [];
  
      while (symbol.pattern.test(str.charAt(this.pos))) {
        res.push(str.charAt(this.pos));
        this.pos++;
      }
  
      // reset if we want to match one or more but didn't find matches.
      if (symbol.onePlus &amp;&amp; !res.length) {
        this.pos = pos;
        return;
      }
  
      return res.join('');
    } else if (symbol.pattern.test(str.charAt(this.pos))) {
      return str.charAt(this.pos++);
    } else if (symbol.optional) {
      return '';
    }
  };
  </code></pre>
  
  <p>It's relatively simple as I could muster at the time. But I'm wondering nowadays if there is a way to simplify this and make it use a sort of <em>iterator</em> like you would see when implementing iteration. For example, with an iterator you can traverse a <strong>list</strong>, a <strong>tree</strong>, and a <strong>graph</strong> all the same way, without worrying about their unique oddities and implementation details.</p>
  
  <pre><code>for (var item of iterator) { ... }
  </code></pre>
  
  <p>Nice and simple. I would like to now apply this to parsers, but can't quite read <a href="http://lambda-the-ultimate.org/node/1599" rel="nofollow noreferrer">this code</a>:</p>
  
  <pre><code>class sequence_parser implements parser {
      list parsers;
      iterator parse(iterator input) {
          foreach(p, parser) {
              input = p.parse(input);
          }
          return input;
      }
  }
  
  class choice_parser implements parser {
      list parsers;
      iterator parse(iterator input) {
          foreach(p, parser) {
              iterator output = p.parse(input);
              if (output != null) return output;
          }
          return null;
      }
  }
  
  class loop_parser implements parser {
      parser other;
      iterator parse(iterator input) {
          input = other.parse(input);
          return parse(input);
      }
  }
  </code></pre>
  
  <p>I can't imagine how it would handle backing up if it fails down a particular path, and stuff like that. Any ideas how to do this or if it's possible? What is the interface required basically, like the iterator example?</p>