1

When it comes to using an LR parser generated by a tool, such as Bison, a disadvantage that often comes up as counterarguments is that the resulting parser will be unreadable and complicated to debug, which is true.

However, I don't really understand this argument since we just use one or two functions in the generated output, and that this last one is not supposed to contain any bugs (a priori).

This sounds to me like saying that we shouldn't use a compiler, because the generated assembler is not readable and difficult to certify as bug-free; but, I may not be aware of all the worries this could cause in a project needing a parser... so why should we care about this argument in the plan to use a a generated LR parser?

  • 5
    Your argument is spot on. Generated code is not meant to be readable. If it were readable, it would also be modifiable (directly), and generated code is not meant to be modifiable either. – Robert Harvey Aug 2 at 20:56
  • 1
    (1) "since we just use one or two functions in the generated output" - in which context? In general? Or in one specific project you have in mind? And (2): who told you so when you say "often"? Any reference from literature? Or is this a specific group of people you have in mind? – Doc Brown Aug 2 at 20:59
  • 1
    I wonder whether some of this criticism is also based in limited experience. For example, a lot of the criticism people have of OO is really actually criticism of Java or C++ and doesn't apply to languages like Self, Newspeak, Scala. The people making these judgements simply never bothered to learn any language other than Java and extrapolate from this sample size of 1 to all OO languages that were ever created, and will ever be created. – Jörg W Mittag Aug 2 at 22:07
  • 2
    Yacc is 50 years old, and surely, it can be improved upon (and has been), but failures of yacc do not necessarily have to be failures of parser generators in general. I wonder how many parser generators the people who generalize their criticism of yacc to all parser generators have actually used. – Jörg W Mittag Aug 2 at 22:10
  • 1
    @RobertHarvey - Re Generated code is not meant to be readable. What the bleep? I occasionally still read the assembly generated by a compiler, and I regularly read code generated in a higher level language. Utter lack of readability has been my number one reason to reject code generation tools. This may require an ability to be read code that if written by a human author might result in the author being drawn and quartered, but still, the code should be readable. A much better way of writing what I think you meant to write is that generated code is not meant to be modifiable. – David Hammen Aug 3 at 13:27
3

Enh... it isn’t a solid argument, but it isn’t something you should just ignore. Parsers are already a pain and a half to debug, so making them even more difficult to debug isn’t a great idea.

There’s also the occasional desire to edit the parser with certain rules that can’t be easily defined in grammars - sometimes for academic reasons, sometimes for performance reasons, sometimes because someone thinks it is easier to do the check there rather than as a post-parsing step.

Mostly though, when I hear this argument it isn’t so much that the parsing code is ugly, but that the output tree is ugly. This isn’t unique to LR parsers of course, but generated parsers do tend towards outputting unwieldy (but technically correct) parse trees. Some see the work to massage that into a nice tree to be nearly as much work as parsing in the first place.

Again, not strong arguments but situations that can make the generator a worse option than it first appears.

| improve this answer | |
3

Perhaps the most important aspect of debugging the result of a parser generator happens when you're still developing the language. If you have a language grammar fully formed and ready to go, then debugging the output may not matter.

But if you're developing the grammar itself, that's going to mean a lot of iterating on the grammar. Part of that means that you're going to have grammars that are themselves buggy, that don't represent the language you intended for them to represent. But those bugs will manifest as getting the wrong result from the parsing. And that parsing ultimately comes from the generated code.

So at some point, you're going to have to go stepping through the generated parser code to get to the place where it's parsing the section of interest, then reading through the generated code's data structures and trying to figure out what all of that code is doing and how it relates to the grammar. The more confused and difficult to read the generated code is, the more difficult this process becomes.

So I would not take this issue lightly.

| improve this answer | |
-1

Put differently, what are the odds of a bug in a custom-built parser versus in a generated parser and the library code that Bison includes in your system? The Bison library code has had literally millions of uses, for decades. The generated parser will be peculiar to your input grammar, but again, Bison's generator has been used for 35 years.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.