backtracking yacc

[Tim Josling]

I and others had a look at btyacc during the very extended
analysis phase of the original GNU COBOL. The main issues were:

- Unpredictability of parse times (a bit reminiscent of
functional programs, usually OK, but sometimes very slow, and
always hard to know).
- Difficulty producing good error messages. Hard to even say
'parse error, expecting X'.
- BSD licence (this was a problem for some people; I express no
opinion).
- Only supported C++. The maintainer claimed that he would accept
patches to reinstate support for C, but when I sent them in,
there was no response.
- Even btyacc needed lexer feedback hacks anyway.
- Bison seemed more actively maintained, and much better
documented, and quite stable. I only ever hit one bug in bison.

All in all, Bison with hacks was good enough for COBOL parsing,
and btyacc didn't fix all the problems anyway. So why go onto the
bleeding edge (actually that may be exaggerated as they claim to
have done a COBOL parser in btyacc so it must be fairly
functional)?

This was about 18 months ago so it may be out of date.

The parser is only a miniscule part of a compiler unless you are
a masochist and do it by hand (eg Ada), so it may not be worth
converting to a new tool. If the language is that ugly a parser
generator will not save you (eg FORTRAN).

Tim Josling

> Subject: 
>        backtracking yacc
>    Date: 
>        Tue, 21 Nov 2000 13:20:18 +0800
>   From: 
>        "Anthony J Heading" <heading_anthony@jpmorgan.com>
>     To: 
>        gcc@gcc.gnu.org
> 
> 
> 
> Hi,
>      I was interested by the plan to replace the C++ parser with a hand-crafted
> recursive descent one.   Seemed to be a change in perspective from when I read
> the original Dragon book many years back, but my expertise is no deeper than a
> cursory read of that so I've not got anything to contribute.
> 
> But my attention was grabbed some time earlier this year though by "BackTracking
> Yacc"   http://www.siber.org/btyacc ,  and just thought I'd mention it in case it
> was of possible use as maybe an alternative solution
> 
> >From the readme:
> 
> > BTYACC is a modified version of yacc that supports automatic backtracking and
> semantic disambiguation to parse ambiguous grammars...
> 
> >  BTYACC was originally written to make it easy to write a
> >  C++ parser (my goal was to be able to use the grammar out
> >  of the back of the ARM with as few modifications as
> >  possible).  Anyone who has ever looked at Jim Roskind
> >  public domain C++ yacc grammar, or the yacc-based grammar
> >  used in g++ knows how difficult this is.
> 
> It may be that this doesn't help with any of the things that Gaby and Mark
> mentioned as desirables  - better error messages and so on.   But just in case
> it's of interest...
> 
> Anthony
> 
>