Add btyacc(1) - yacc(1) compiled with backtracking support

[cem]

Summary

Some yacc-using tools depend on the features in the backtracking version
of byacc. Enable it as a second yacc build, rather than making the
default yacc backtracking.

PR: 244149

[emaste]

Seems reasonable to me, although I'm curious about the use cases

[cem]

In D24948#549363, @emaste wrote:

Seems reasonable to me, although I'm curious about the use cases

I wanted it for something in February but don’t recall what.

[emaste]

OK, fair enough. Another question, what is the downside of building regular yacc with YYBTYACC?

[cem]

Hm, if it's anything like regular expression engines, it means the generated parser could have exponential running time instead of some more limited running time? I don't really know, though. A quick grep shows many many conditional ifdefs and I have not investigated it much yet.

[cem]

Here's more on btyacc, maybe? https://www.siber.com/btyacc/README.txt

[markj]

In D24948#549382, @cem wrote:

Here's more on btyacc, maybe? https://www.siber.com/btyacc/README.txt

This suggests that backtracking is only done when the parser hits an error. But it also causes the parser to save some state when it hits a conflict, and it's pretty common for yacc grammars to contain such conflicts, so using btyacc might introduce some overhead. Then, if the parser raises an error, it will automatically backtrack and try alternate parses, which seems like behaviour you'd want to enable explicitly.

The notes also say that btyacc version 3.0 dropped compatibility with C, i.e., the parser has to be in C++. This all indicates to me that it should be a separate executable.

It'd be nice to see a concrete use-case before adding it to the tree though.