0

I’m trying to write a parser in JavaScript that is able to be interrupted by the fact that the entire input source is not available during the parse. When subsequent chunks of the input become available, the parser should be able to pick up where it left off.

Tokens in the grammar being parsed includes multi-character keywords as well as identifiers of unknown length. Determining if the parse has failed due to invalid syntax or incomplete input is important.

There are a number of edge cases to consider and it seems that this type of thing should have been done before. Searching for ‘interruptible parser’ doesn’t provide much info. Is there another name for such a thing? What are some gotchas edge cases to be aware of?

  • Have a look at table-driven parsers which use an explicit stack for recursive grammar rules. Many current parser frameworks are based on recursive descent which wouldn't work well given how JavaScript deals with blocking. Older compiler construction books might explain how to do it. I'm not aware of a JavaScript framework that directly does this, though. – Hans-Martin Mosner Jul 22 '19 at 12:37
  • You could also use a continuation-passing style, and have your input provided by futures. – BobDalgleish Jul 22 '19 at 18:33
  • Table driven parsers. Awesome. That's what I wanted to see – oorst Jul 22 '19 at 20:13
2

It's generally a good idea not to couple a component to mechanisms that have nothing to do with its core purpose. A parser should concentrate on combining tokens into parse trees; "being interruptible" shouldn't be on the list of things it worries about.

Therefore, writing an interruptible parser usually involves supplying the input via a mechanism that blocks until the requested number of characters or tokens become available.

If it's important to know whether the parser is blocked due to incomplete input, this should be done by a component outside the parser: if the parsing thread/process/microservice etc. is blocked, the input was incomplete; if it has returned an error code, there was an error in the source code.

  • Ok. It would be straight forward to indicate to the parser whether or not the input was whole. I think the case the case of partially matched keywords at the end of the input needs to be handled in a specific way. I'm also thinking that an interruptible parser should also be an event based parser, where it doesn't return a parse tree, but emits certain structures when they are found. – oorst Jul 22 '19 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.