4 ms·

The big plus of parser generators is that they report ambiguities. Handling conflicts is a pain but explicit. Do people who write predictive recursive descent

by plranw 2y ago

The big plus of parser generators is that they report ambiguities. Handling conflicts is a pain but explicit. Do people who write predictive recursive descent parsers (LL(k)) really calculate first/follow sets by hand? What if the grammar requires backtracking?

lolinder 2y ago
There's nothing to stop you from writing out a grammar in some form that is intelligible to a verification tool and then implementing the grammar by hand. I almost always write out the grammar anyway because that's the design—without it I'm flying blind. The cost of the generator isn't writing out the grammar, it's in using the runtime code it generates, which is optional even if you want to use it for verification.
int_19h 2y ago
Arbitrary backtracking in a recursive descent parser is very easy with exceptions. However, there's also an argument here that if the grammar is too complicated to be parsed with recursive descent, it's probably just too complicated in general and should be simplified if possible. Obviously you don't always have this option when you're dealing with an external grammar, but for your own PL, you can design around that. Most Wirth's languages are good examples; Pascal is famously LL(1).
- haberman 2y ago
  Recursive descent parsers can have ambiguities, but like PEGs, they just resolve the ambiguity by arbitrarily picking one of the alternatives. A famous example is ALGOL 60, which had the dangling else ambiguity (https://en.wikipedia.org/wiki/Dangling_else https://en.wikipedia.org/wiki/Dangling_else), but this was not discovered until the language had already been published. If they had been using a parser generator tool, it would have warned them that the grammar was not LL or LR. Overall I do still prefer hand-written recursive descent parsers, but I do find this to be one of the biggest downsides of not using parser generators.
  - fanf2 2y ago
    Of course the Algol 60 committee could not have used a parser generator tool because they were not invented until later in the 1960s, but your point is valid for anyone developing a language after that time.

by plranw 2y ago

lolinder 2y ago

There's nothing to stop you from writing out a grammar in some form that is intelligible to a verification tool and then implementing the grammar by hand. I almost always write out the grammar anyway because that's the design—without it I'm flying blind. The cost of the generator isn't writing out the grammar, it's in using the runtime code it generates, which is optional even if you want to use it for verification.

int_19h 2y ago

Arbitrary backtracking in a recursive descent parser is very easy with exceptions. However, there's also an argument here that if the grammar is too complicated to be parsed with recursive descent, it's probably just too complicated in general and should be simplified if possible. Obviously you don't always have this option when you're dealing with an external grammar, but for your own PL, you can design around that. Most Wirth's languages are good examples; Pascal is famously LL(1).

haberman 2y ago
Recursive descent parsers can have ambiguities, but like PEGs, they just resolve the ambiguity by arbitrarily picking one of the alternatives. A famous example is ALGOL 60, which had the dangling else ambiguity (https://en.wikipedia.org/wiki/Dangling_else https://en.wikipedia.org/wiki/Dangling_else), but this was not discovered until the language had already been published. If they had been using a parser generator tool, it would have warned them that the grammar was not LL or LR. Overall I do still prefer hand-written recursive descent parsers, but I do find this to be one of the biggest downsides of not using parser generators.
- fanf2 2y ago
  Of course the Algol 60 committee could not have used a parser generator tool because they were not invented until later in the 1960s, but your point is valid for anyone developing a language after that time.