4 ms·

I am aware this is an unpopular opinion, but I think the idea that recursive descent is inherently better suited to error reporting than table-driven LR is mass

I am aware this is an unpopular opinion, but I think the idea that recursive descent is inherently better suited to error reporting than table-driven LR is massively cargo-culted. You can handcraft error messages for an LR parser if you overspecify the grammar, meaning that you don't just write productions for the actual language; you also write productions for likely errors and have the predicates for those productions report your handcrafted error message. I'm guessing that a lot of people's first impression of that will be "That's insane, are you seriously suggesting writing two grammars in one?" But that's exactly what you do when you build custom error reporting code into a recursive descent parser. It's just less obvious because the code is procedural instead of declarative.

ckcheng 2y ago
That's a very interesting way of looking at errors. Wouldn’t the grammar of errors have to also be LR? Doesn’t that limit the kind of errors you can report?
- Calavar 2y ago
  Yes, it does have to be LR. Which can be a real PITA if you're working with a restrictive subset of LR, like LALR. But there are other options too. LR(1) is pretty powerful, and GLR even more so.
layer8 2y ago
Yes, that’s also not uncommon for lexical grammars to haven token classes that are more general than what is actually valid, for example for numerical constants. What would be useful is tooling that would check that one grammar is a sub-language of another grammar which is suitably connected (because in the general case that check is undecidable of course).
norir 2y ago
I see the appeal of adding error nodes, but I'm not a huge fan. If you do this rather than either bombing out immediately on the first error or storing a stack of errors, then the syntax errors pollute the generated tree. This will require you to either add a separate pass for building a new tree that is the same as the old except without the error nodes, or you will have to handle syntax errors downstream in the analysis or code gen phase. A recursive descent parser does not have to be procedural. I have written one in a functional language that I designed that has no mutable variables or loops (recursive functions handle both of these cases). Parser generators are great for iterating on language syntax design. Once you know the language syntax, handwriting the parser should be easy. If it isn't, then it is most likely that either your language design or parsing skills need work. Both require time and practice.
- Calavar 2y ago
  > If you do this rather than either bombing out immediately on the first error or storing a stack of errors, then the syntax errors pollute the generated tree. This will require you to either add a separate pass for building a new tree that is the same as the old except without the error nodes, or you will have to handle syntax errors downstream in the analysis or code gen phase. I don't see how this follows? There is no need to append an error node (or any node at all) to the AST when reducing an error production. You can just print an error message or push one onto a stack of error messages. > Parser generators are great for iterating on language syntax design. Once you know the language syntax, handwriting the parser should be easy. If it isn't, then it is most likely that either your language design or parsing skills need work. Both require time and practice. Parser generators aren't just for people who don't know how to write recursive descent parers; they are production ready tools. Python, Ruby, PHP, and Bash all use generated parsers. I think the aversion to parser generators in general and LR parser generators in particular is a combination of not-invented-here-syndrome and cargo-culting the idea that LR parsers can't emit handcrafted error messages.

ckcheng 2y ago

That's a very interesting way of looking at errors. Wouldn’t the grammar of errors have to also be LR? Doesn’t that limit the kind of errors you can report?

Calavar 2y ago
Yes, it does have to be LR. Which can be a real PITA if you're working with a restrictive subset of LR, like LALR. But there are other options too. LR(1) is pretty powerful, and GLR even more so.

layer8 2y ago

Yes, that’s also not uncommon for lexical grammars to haven token classes that are more general than what is actually valid, for example for numerical constants. What would be useful is tooling that would check that one grammar is a sub-language of another grammar which is suitably connected (because in the general case that check is undecidable of course).

norir 2y ago

I see the appeal of adding error nodes, but I'm not a huge fan. If you do this rather than either bombing out immediately on the first error or storing a stack of errors, then the syntax errors pollute the generated tree. This will require you to either add a separate pass for building a new tree that is the same as the old except without the error nodes, or you will have to handle syntax errors downstream in the analysis or code gen phase. A recursive descent parser does not have to be procedural. I have written one in a functional language that I designed that has no mutable variables or loops (recursive functions handle both of these cases). Parser generators are great for iterating on language syntax design. Once you know the language syntax, handwriting the parser should be easy. If it isn't, then it is most likely that either your language design or parsing skills need work. Both require time and practice.

Calavar 2y ago
> If you do this rather than either bombing out immediately on the first error or storing a stack of errors, then the syntax errors pollute the generated tree. This will require you to either add a separate pass for building a new tree that is the same as the old except without the error nodes, or you will have to handle syntax errors downstream in the analysis or code gen phase. I don't see how this follows? There is no need to append an error node (or any node at all) to the AST when reducing an error production. You can just print an error message or push one onto a stack of error messages. > Parser generators are great for iterating on language syntax design. Once you know the language syntax, handwriting the parser should be easy. If it isn't, then it is most likely that either your language design or parsing skills need work. Both require time and practice. Parser generators aren't just for people who don't know how to write recursive descent parers; they are production ready tools. Python, Ruby, PHP, and Bash all use generated parsers. I think the aversion to parser generators in general and LR parser generators in particular is a combination of not-invented-here-syndrome and cargo-culting the idea that LR parsers can't emit handcrafted error messages.