http://invisible-island.net/
Copyright © 2002-2013,2014 by Thomas E. Dickey


BYACC – Berkeley Yacc – generate LALR(1) parsers

Synopsis

Berkeley Yacc (byacc) is generally conceded to be the best yacc variant available. In contrast to bison, it is written to avoid dependencies upon a particular compiler.

History

Byacc was written around 1990 by Robert Corbett who is the original author of bison. Byacc is noted in Lex & Yacc by John Levine et al (O'Reilly, 1992) for its compatibility with the original yacc program.

Later, in Flex & Bison (O'Reilly, 2009), John Levine states that because Corbett's implementation was faster than Bell (AT&T) yacc, and because it was distributed under the BSD license, "it quickly became the most popular version of yacc". See below for comments on licensing.

My Involvement

Originally written in K&R C, I have modified it to conform to ANSI C, and made other improvements.

See the changelog for details:

Early (when byacc was first released), Alex Blakemore told me that byacc was "the cleanest piece of code that (he) had ever seen". At the time, I was not interested in byacc in particular, although it was around the time that I started working on cproto. Since byacc was compatible with yacc, there was nothing to change.

Later, I was reminded of the differences between byacc and bison, when the latter dumped core attempting to build the bind program. Since that point, I have used byacc except for those programs that have been modified to rely upon bison.

My motivation for working on byacc was to use it in a port of the tin newsreader on VMS, early in 2000. The compiler reminded me that the source was K&R, so I converted it to ANSI C, and submitted it along with the other programs I was working on at that point to the VMS freeware cdrom. For instance, here is an abstract referencing that port.

ANSI C of course refers to c89, not c99 or gcc. The latter have features which are useful in a few specific applications, but none of those include programs such as byacc. In contrast, bison in its different versions has dependencies on gcc or c99.

I started by modifying the original byacc 1.9 distribution. For reference, there is an unmodified copy on my ftp site. That done, I took a look around for a maintainer, to "own" the changes. There was none. Alternatively, I could continue to maintain it. So I looked further, found a different variant with some possibly useful changes for MS-DOS. (I set that aside and did not return to it).

Initially, I ignored the source repositories for FreeBSD, NetBSD and the like, for the usual reasons:

However, I did make a note in 2005 to review the FreeBSD vs bison use of YYPARSE_PARAM (a similar idea implemented in two incompatible ways). Eventually I wrote my own version, which bridges the two.

Licensing

The original distribution of byacc states in its README file:

Berkeley Yacc is in the public domain. The data structures and algorithms used in Berkeley Yacc are all either taken from documents available to the general public or are inventions of the author. Anyone may freely distribute source or binary forms of Berkeley Yacc whether unchanged or modified. Distributers may charge whatever fees they can obtain for Berkeley Yacc. Programs generated by Berkeley Yacc may be distributed freely.

As a rule, I'm license-neutral unless someone offers some reason to change it. For instance, I relicensed dialog to address user requests. Byacc is public domain. If I were to change it, e.g., to reflect my improvements, then it would likely be to the same MIT X11 license which I use the most.

Perry Metzger mentioned in correspondence during 2008 that having it remain public domain would suit his goals. On the other hand, Xin LI (a FreeBSD packager) asked me late in 2009 to add a copyright notice (license), and that making it on the same terms as FreeBSD's would suit his goals.

After discussing it with Perry, I did investigate further. Here is a recap:

I've found no reliable source which states that byacc must bear a UCB copyright.

Here is a summary of the amount of change prompted by the discussion of licensing in 2009. For context, see this mailing list discussion.


Future Plans

Some additional amount of compatibility with bison would be useful (to me, and others), with the caveat that bison itself is no longer compatible with yacc. The most obvious difference was the support for reentrant code, which has evolved in byacc to the point where it can be compared and tuned against bison.

However, even after factoring out that feature, there are a few of the half-dozen or so programs that I have seen using bison's reentrancy feature which are also relying upon inferences which do not appear to match yacc (and some investigation is needed to isolate the exact problem). Ironically, one of bison's maintainers advised the developers of "new" flex to avoid making their program incompatible with the POSIX lex. Again, my motivation for working on relocalizable flex was that "new" flex was incompatible with both "old" flex and POSIX lex.

Another area to explore would be integrating the Perl feature, which appears to have no maintainer.

Documentation


Download

There are numerous references on the net to byacc. Here are a few of the more interesting ones: