Discussion about nicer error messages

[gvanrossum]

Creating this issue to preserve links to our discussion on this topic in #7:

• Change SyntaxError messages to match the current parser #43 (comment)
• Change SyntaxError messages to match the current parser #43 (comment)

[lysnikolaou]

See also #123.

[gvanrossum]

A few more papers we might look into:

PIKA parsing (Hutchison): https://arxiv.org/abs/2005.06444

• Hm... "although for a complex grammar implementing the Java language specification, a large constant performance impact was incurred per input character for the pika parser, which allowed Parboiled2 and ANTLR4 to perform significantly better than the pika parser for this grammar (in spite of ANTLR4’s parsing time scaling between quadratically and cubically in the length of the input with the Java grammar)." -- does not sound great for Python.

• The only bits relevant to error recovery are sec. 3.2 and Fig. 5. (Though you need some earlier sections to understand the notation; I found sec. 1.7 a useful starting point.) I am somewhat underwhelmed by the error recovery, it just identifies a region that is in error (it doesn't generate "missing ')' here" messages).

• There's also an interesting idea for precedence parsing (i.e. 23+45), see sec. 3.3 and Listings 2-4. Basically the rules E0, E1, E2 are renamed E[0], E[1], etc. and referenced as just E in the RHSs. Plus a flag for associativity.

• Anyway, I think the search for better error messages is still on. :-)

PetitParser (Rüfenacht): http://scg.unibe.ch/news/2016-08-11_16-15-01Ruef16a

• While the 2018 Lua paper cites this and quotes performance problems, it looks like it has useful ideas for us, as it builds on our existing concept of "farthest failure" as the location of the error. I haven't read the whole thing yet (it's a Master's thesis) but I think it's more likely to help us than the Lua paper. I found the latter rather a letdown since all the work has to be done by the grammar author, while Rüfenacht seems to automatically generate data structures (from the grammar) that help the parser recover from errors.

• I was quick-reading Chapter 4 and I find quite intriguing the 'set extension' that it proposes (First Set, Dynamic Follow Set and Recovery Set). It seems that having the first two may help us as well in automatically introducing lookaheads/cut points

• Something that we need to benchmark is how costly is to compute the dynamic follow sets, as these depend on the story of the parser. We may be able to do somo memory/time tradeoffs there

• An idea may be to only activate this mechanism once we know something went wrong: it will do a first pass, detect a failure and then do a second pass with error recovery activated.

• Oh, this is how they implemented it:

  To clarify the inner workings of of our implementation and bridge the gap to the theoretical elaborations, it seems worth explaining the basic workflow of the error handler. The error handler initiates the concrete error handling if the original parser fails.