djspiewak / parseback

A Scala implementation of parsing with derivatives
http://parseback.io
Apache License 2.0
197 stars 22 forks source link

Error recovery tokens #10

Open djspiewak opened 7 years ago

djspiewak commented 7 years ago

This falls into the "straight-up research" category. I'm pretty sure it's possible, and maybe even natural, to implement YACC-style error recovery using the derivative parsing algorithm. I think this falls out relatively naturally both due to the combinator-structure of the parse trail, and because derivative parsing (by definition) always parses to the end of the stream even when errors are hit early in the parse. So something like this might be possible:

lazy val expr: Parser[Expr] = (
    ...
  | "{" ~> error(expr) <~ "}"
  | ...
)

Or something to that effect. I say this is "straight-up research" because a practical and algorithmically coherent implementation of this idea (or something better!) is very much paper-worthy.