Berkeley Yacc

In 1985, Robert Corbett developed an original LALR parser generator based on a 1982 paper by DeRemer and Pennello.{{cite journal |last1=DeRemer |first1=Frank |last2=Pennello |first2=Thomas |date=October 1982 |title=Efficient Computation of LALR(1) Look-Ahead Sets |url=http://3e8.org/pub/scheme/doc/parsing/Efficient%20Computation%20of%20LALR%281%29%20Look-Ahead%20Sets.pdf |journal=ACM Trans. Program. Lang. Syst. |volume=4 |issue=4 |pages=615–649 |publisher=ACM |issn=0164-0925 |doi=10.1145/69622.357187 |s2cid=52833742 |access-date=2017-08-26}} Corbett wrote it as part of his research towards the Ph.D. he received from University of California, Berkeley in June 1985.{{cite newsgroup |last1=Corbett |first1=Robert |date=1998-09-24 |df=mdy |title=Re: Anyone extended MAXTABLE in yacc parsers? |newsgroup=comp.compilers |message-id=98-09-125@comp.compilers |url=https://compilers.iecc.com/comparch/article/98-09-125 |access-date=2017-08-26}}{{cite thesis |last1=Corbett |first1=Robert Paul |date=June 1985 |title=Static Semantics and Compiler Error Recovery |type=Ph.D. |publisher=University of California, Berkeley |id=DTIC [https://web.archive.org/web/20170608112235/http://www.dtic.mil/docs/citations/ADA611756 ADA611756]{{cbignore|bot=medic}}}} It was originally named Byson and was incompatible with Yacc but it was subsequently renamed Bison and became the basis of GNU Bison.

Later in 1985, Corbett developed his LALR parser generator, making it Yacc-compatible and naming it Zeus but subsequently renaming it Zoo.{{cite newsgroup |last1=Corbett |first1=Robert |date=1989-09-06 |df=mdy |title=Name that PD parser generator |newsgroup=comp.compilers |message-id=1989Sep6.152554.318@esegue.segue.boston.ma.us |url=https://compilers.iecc.com/comparch/article/89-09-007 |access-date=2017-08-26}} Corbett published the source code for Zoo in a Usenet newsgroup but it went mostly unnoticed until later in September 1989 when Corbett posted on the comp.compilers newsgroup about putting the source code on an FTP server. There was discussion about renaming it and by October 1989 it had become known as Berkeley Yacc (byacc).{{cite newsgroup |last1=Corbett |first1=Robert |date=1989-10-03 |df=mdy |title=Berkeley Yacc (new version) |newsgroup=comp.compilers |message-id=1989Oct3.230634.1007@esegue.segue.boston.ma.us |url=https://compilers.iecc.com/comparch/article/89-10-002 |access-date=2021-09-17}}

In 1995, Chris Dodd developed BtYacc, a backtracking derivative of Berkeley Yacc to support parsing context-sensitive languages like C++,{{cite newsgroup |last1=Dodd |first1=Chris |date=1995-03-07 |df=mdy |title=BTYACC -- yacc with backtracking and inherited attributes. |newsgroup=comp.compilers |message-id=95-03-044@comp.compilers |url=https://compilers.iecc.com/comparch/article/95-03-044 |access-date=2021-09-17}}{{cite web |title=README.txt |url=https://www.siber.com/btyacc/README.txt |department=BtYacc: BackTracking Yacc |website=Siber Systems |access-date=2020-05-14}} based on a 1993 paper by Merrill describing similar modifications to AT&T Yacc.{{cite web |title=README.BYACC |url=https://github.com/ChrisDodd/btyacc/blob/master/README.BYACC |department=Backtracking yacc |website=GitHub |access-date=2022-08-12}}{{cite journal |last1=Merrill |first1=Gary H. |title=Parsing Non-LR(k) grammars with yacc |journal=Software: Practice and Experience |volume=23 |issue=8 |date=1993-08-01 |df=mdy |pages=829–850 |issn=0038-0644 |doi=10.1002/spe.4380230803 |citeseerx=10.1.1.14.1958 |s2cid=14695500 }} Its backtracking and semantic disambiguation capabilities allow it to generate parsers for ambiguous grammars. A rule parsed but rejected by semantic information can be rolled back, so that the parser can try another rule.{{cite web |title=btyacc(1) |url=https://manpages.debian.org/stretch/btyacc/btyacc.1.en.html |website=Debian stretch — Debian Manpages}}{{cite web |last1=Dodd |first1=Chris |title=ChrisDodd/btyacc |url=https://github.com/ChrisDodd/btyacc |website=GitHub |date=13 February 2019}} However, it has also been criticized for needing side-effect free trial actions and its inflexible handling of shift-reduce conflicts.{{cite conference |last1=Thurston |first1=Adrian D. |last2=Cordy |first2=James R. |title=A Backtracking LR Algorithm for Parsing Ambiguous Context-Dependent Languages |editor1-last=Erdogmus |editor1-first=Hakan |editor2-last=Stroulia |editor2-first=Eleni |editor3-last=Stewart |editor3-first=Darlene A. |book-title=Proceedings of the 2006 conference of the Centre for Advanced Studies on Collaborative Research, October 16–19, 2006, Toronto, Ontario, Canada |conference=CASCON 2006 |year=2006 |pages=39–53 |citeseerx=10.1.1.518.7094 |doi=10.1145/1188966.1188972 |url=http://research.cs.queensu.ca/home/cordy/Papers/TC_CASCON_Parsing.pdf |access-date=2020-05-14}}

In 1997, Vadim Maslov took over maintenance of BtYacc to support a COBOL parser developed by his company.{{cite newsgroup |last1=Maslov |first1=Vadim |date=1997-10-08 |df=mdy |title=Version 1.1 of BtYacc (Backtracking Yacc) is available |newsgroup=comp.compilers |message-id=97-10-039@comp.compilers |url=https://compilers.iecc.com/comparch/article/97-10-039 |access-date=2021-09-17}} By 1999, the last 3.0 release, had been converted to C++, making it no longer implemented in C.{{cite web |title=BtYacc: BackTracking Yacc Parser Generator |url=https://www.siber.com/btyacc/ |website=Siber Systems |access-date=2020-05-18}}

In 2000, Thomas E. Dickey ported Berkeley Yacc to OpenVMS to facilitate porting tin to VMS. After failing to find another maintainer, Dickey has maintained Berkeley Yacc since February 2002.{{

cite web

|url=http://invisible-island.net/byacc/byacc.html

|title=BYACC - BERKELEY YACC

|website=invisible-island.net

|access-date=2020-11-10

|url-status=live

|archive-url=https://web.archive.org/web/20020406011256/http://invisible-island.net/byacc/byacc.html

|archive-date=2002-04-06

}} A significant update was the conversion from K&R C to ANSI C89.

In 2014, Tom Shields integrated BtYacc backtracking into Berkeley Yacc effectively subsuming BtYacc and again supporting C (instead of only C++) in Dickey releases since April 2014.{{cite web |title=Release t20140407 |url=https://github.com/ThomasDickey/byacc-snapshots/releases/tag/t20140407 |department=ThomasDickey/byacc-snapshots |website=GitHub |access-date=2020-05-18}}

Parser generators typically deal with three languages: the language a generator is implemented in, the language a generated parser is implemented in and of course the metalanguage that describes whatever a generated parser should parse. A fourth language could be considered whatever language a generated parser parses but parser generators do not handle such directly, instead just focusing on generating a parser from a given description while letting the generated parser deal with such. Yacc is written in C and generates parsers in C from its own Yacc metalanguage descriptions. This is also how Berkely Yacc works (thus its compatibility), however, a number of derivatives have been created to allow it to generate parsers in languages other than C.

Ray Lischner developed perl-byacc (pbyacc) from byacc 1.6, so that it could also generate parsers in Perl. Later Richard "Rick" Ohnemus ported the patches from byacc 1.6 to byacc 1.8.{{cite web |url=https://github.com/elfprince13/PyByacc/blob/36bc89c6233f69565dae67bdb076bf45a99c6ec7/ACKNOWLEDGEMENTS |title=ACKNOWLEDGEMENTS |department=elfprince13/PyByacc |website=GitHub |date=2013-01-14 |access-date=2021-11-01}} And later in 1996, Jake Donham developed p5yacc from perl-yacc 1.8.2 so that its generated Perl parsers would use Perl 5 classes.

In 1994, Mike Kleyn developed tyacc from perl-yacc 1.8.2 so that it could also generate parsers in Tcl{{cite web |url=http://ftp.funet.fi/pub/languages/tcl/ibp/tyacc-0.9.README |title=tyacc-0.9.README |department=pub/languages/tcl/ibp |website=ftp.funet.fi |access-date=2021-11-01}}

In 1997, Bob Jamison developed BYACC/Java (later called BYACC/J or byaccj) from byacc 1.8, so that it could also generate parsers in Java.{{cite web |url=http://lincom-asg.com/~rjamison/byacc/ |title=BYACC/Java Home Page |department=Bob Jamison |website=LinCom Innovations ASG |archive-url=https://web.archive.org/web/19981205145212/http://lincom-asg.com/~rjamison/byacc/ |archive-date=1998-12-05}}{{cite web |url=https://sourceforge.net/p/byaccj/git/ci/master/tree/src/skeleton.c |title=master/src/skeleton.c |department=byacc/j |website=SourceForge |access-date=2021-10-28}}

In 2000, Bruce Bahnsen merged in the Java parser capabilities of BYACC/J into perl-yacc and added the ability to generate parsers in Python.{{cite web |url=https://sourceforge.net/projects/byacc/ |title=Berkeley Yacc |website=SourceForge |date=8 March 2013 |access-date=2021-11-01}} In 2013, Thomas Dickerson made further improvements on it deeming it PyByacc.{{cite web |url=https://github.com/elfprince13/PyByacc |title=elfprince13/PyByacc |website=GitHub |date=2013-01-14 |access-date=2021-11-01}}

In 2003, Dave Bodenstab merged tyacc and p5yacc to develop a PERL-TCL-YACC rebasing it from 4.8 release of yacc from FreeBSD (a byacc derivative).{{cite web |url=http://www.bodenstab.org/#YACC |title=BYACC which produces Perl/Tcl parsers |website=Dave Bodenstab's Home Page |archive-url=https://web.archive.org/web/20210501051500/http://www.bodenstab.org/#YACC |archive-date=2021-05-01}}

• Comparison of parser generators

{{reflist|30em}}

• {{Official website}}

Category:Compiling tools

Category:Parser generators

Category:Free software programmed in C

Category:Public-domain software with source code