4 ms·

I tend to agree. Having done a bunch of DSL's over the years, and becoming extremely fluent with Bison+FLEX, I have to say that a hand-written LL parser with a

I tend to agree. Having done a bunch of DSL's over the years, and becoming extremely fluent with Bison+FLEX, I have to say that a hand-written LL parser with a couple of mutually recursive table-driving functions to parse expressions via precedence climbing is the way to go. Precedence climbing (or I think it is also called Pratt parsing?) is super simple and flexible. But the BIG bonus is in error reporting, and let's face it, most of the user interaction with your parser is with the error messages, otherwise it is push 'enter' and forget. Getting a reasonable error message out of an LR parser is about as much fun as poking yourself in the eye repeatedly with a sharp stick. With LL, you know what structure you are trying to build... with LR, you have to rummage around in parse stack looking for obscure clues.

Calavar 2y ago
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.
o11c 2y ago
I utterly reject hand-written parsers. You give up the ability to trust your grammar - all too often you can accidentally add an ambiguity. I like `bison --xml` for the fact that you can write your own code but trust the table.
- norir 2y ago
  Do you utterly reject essentially every mainstream language? Which languages do you use that do not use a handwritten parser?

Calavar 2y ago

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.

o11c 2y ago

I utterly reject hand-written parsers. You give up the ability to trust your grammar - all too often you can accidentally add an ambiguity. I like `bison --xml` for the fact that you can write your own code but trust the table.

norir 2y ago
Do you utterly reject essentially every mainstream language? Which languages do you use that do not use a handwritten parser?