Comment by IvanK_net | Hacker News Reader

Comment by IvanK_net | Hacker News Reader

Parent Full thread

What "Error recovery" means in your software? You usually want the parser to accept the input when it corresponds the grammar and refuse input, when it does not.

I think that user should modify his grammar in order to accept errors (e.g. missing colon in your example). If you do it for him, then you must specify, what you mean by tolerable and intolerable errors. I think your specification may get very large and confusing.

EDIT: I just found out what you mean by "error recovery". However I still think, that user should specify accepted errors inside a grammar, so he has bigger control over it. Your "error recovery" can never be prepared to all kinds of rerrors, that user may want to recover from.

BTW. PEG.js can generate a parser "object", which is directly usable in the same JS "process". I have never seen any parser code while working with PEG.js.

BTW2. generating the parser code can also be very useful, when you don't want to distribute your grammar alongside with your app.

The use case of only handling valid input is a very common one, Particularly during compiler construction.

But what about the use case of building an Editor (IDE) ? In this context it would highly beneficial to be able to handle invalid inputs as the user would still expect outline/navigation/formatting/.../ to work even when there are syntax errors.

Error Recovery algorithms are heuristics, they can never solve all the possible kinds of errors. Automatic error recovery is also not mutually exclusive with expanding the grammar to support some "tolerable" errors, Both can be used to improve the "robustness" of the grammar when fault tolerance is needed.

Also note that expanding the grammar will work best for simple common errors (missing semicolon), but what about when you need to re-sync an unknown number of tokens and unwind the parser call stack?

Also note these "heuristics" are not "mine", they are based on heuristics used in Antlr 3. Which is itself based on Academic studies in this topic: Specifically:

Josef Grosch. Efficient and comfortable error recovery in recursive descent parsers. Structured Programming, 11(3):129–140, 1990.

Rodney W. Topor. A note on error recovery in recursive descent parsers. SIGPLAN Not., 17(2):37–40, 1982.

Niklaus Wirth. Algorithms + Data Structures = Programs. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1978.

Having the parser recover from errors is very useful if you want to build a text editing environment for your language, for example. It would allow you to highlight errors to the user, and to provide context-sensitive help, even beyond the position of the first error of the user's input.

Answer to BTW: But what about debugging and stepping through the grammar execution? I assume that in the case you are describing EVAL is performed on text generated "in memory". If you want to debug your code snippets (grammar actions) or just the grammar flow itself you still can't escape the generated code, even if you can escape generating an actual file.

Answer to BTW2: Could you describe such a use case? what would be the motivation for it?

Reply on news.ycombinator.com