How to write an *interruptible* recursive(?) descent parser

Question

I have a pretty standard recursive descent parser. The algorithm is straightforward: each function reads characters from a stream and either returns FAIL or calls subsequent parse functions (specified by a corresponding grammar rule):

function parseFoo() {
  var ret = parseBar(stream);
  if (ret == FAIL) {
    ret = parseQuax(stream);
    ...
  }
  ...
  return ret;
}

I would like to solve a situation where I don't have the full stream at once - I get its pieces asynchronously. Therefore what I need is a feature of "interruptability" - I must be able to save a state of the parser and later continue from that point on.

Sadly, this is one thing that is impossible to do with nested function calls, because all the state of a parser is "stored" on the call stack (in the order of functions and in their local variables).

So I have to construct the parse* functions differently.

The language I use is JavaScript.

Can someone point me o any ideas how to proceed?

EDITs:

• It seems clear to me that I need some sort of state machine(s). I can't wrap my head around generators or continuations-passing-style, it looks to me that there are so many glitches in the saving of a state and resuming. To me most clear pathway I can think of is to convert the nested calls into some sort of stack, rewrite the local variables to some hashmap stored at the stack item and construct the parsing code in a different, linear fashion so I can easily "goto" to some state.

• One of the sub-problems I see is might be this: Since I don't have the full stream I think I have to try multiple paths and store all the partially-parsed attempts. For example if the grammar says a = b | c then b might be so long that it is not fully in the stream. So I can't "hang" in parsing b, I have to try both and save the partial computations. Am I right?

Answer 1

It depends upon the programming language used.

You basically need some support of continuations (which you could understand as the abstraction of the call stack). In other words, you may want to code in continuation passing style (CPS).

If coding in C, you might be interested by CPC.

If coding in Javascript, you'll probably need to hand-code in CPS. See also this, this, this question, this pages etc....