Berkeley Yacc

Berkeley Yacc (byacc) is a Unix parser generator designed to be compatible with Yacc. It was originally written by Robert Corbett and released in 1989.[2] Due to its liberal license and because it was faster than the AT&T Yacc, it quickly became the most popular version of Yacc.[3] It has the advantages of being written in ANSI C89 and being public domain software.

Berkeley Yacc
Original author(s)Robert Corbett
Developer(s)Thomas Dickey
Initial releaseSeptember 2, 1989 (1989-09-02)[1]
Stable release
20200330 / March 30, 2020 (2020-03-30)
Repository
Written inANSI C89
Operating systemUnix-like
TypeParser generator
Licensepublic domain
Websiteinvisible-island.net/byacc/

It contains features not available in Yacc, such as reentrancy, which is implemented in a way that is broadly compatible with GNU Bison.[4][5]

History

In 1985, Robert Corbett developed an original LALR parser generator based on a 1982 paper by DeRemer and Pennello.[6] Corbett wrote it as part of his research towards the Ph.D. he received from University of California, Berkeley in June 1985.[7][8] 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 derived another Yacc-compatible LALR parser generator originally named Zeus but subsequently renamed Zoo.[9] 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.[1] There was discussion about renaming it and by October 1989 it had become known as Berkeley Yacc (byacc).[10]

In 1995, Chris Dodd developed BtYacc, a backtracking derivative of Berkeley Yacc to support parsing context-sensitive languages like C++,[11][12] based on a 1993 paper by Merrill describing similar modifications to AT&T Yacc.[13][14] It offers backtracking and semantic disambiguation for parsing ambiguous grammar. A rule parsed but rejected by semantic information can be rolled back, so that the parser can try another rule.[15][16] However, it has also been criticized for needing side-effect free trial actions and its inflexible handling of shift-reduce conflicts.[17]

In 1997, Vadim Maslov took over maintenance of BtYacc to support a COBOL parser developed by his company.[18] By 1999, the last 3.0 release, had been converted to C++, no longer supporting from C.[19]

In 2000, Thomas E. Dickey, ported Berkeley Yacc to VMS to facilitate porting tin to VMS. After failing to find another maintainer, Dickey has maintained Berkeley Yacc since February 2002.[20] A significant update was the conversion from K&R C to ANSI C89.[20]

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.[21]

See also
  • GNU Bison - another free software replacement for Yacc, sharing the same author as Berkeley Yacc.

References
  1. Corbett, Robert (September 2, 1989). "PD LALR(1) parser generator". Newsgroup: comp.compilers. Usenet: 1989Sep2.134244.1611@esegue.uucp. Retrieved 2017-08-26.
  2. Doug Brown; John Levine; Tony Mason (October 1992), lex & yacc (2 ed.), O'Reilly Media
  3. John Levine (August 2009), flex & bison, O'Reilly Media
  4. "Berkeley Yacc". invisible-island.net. Archived from the original on 2020-10-19. Retrieved 2020-11-10. ...support for reentrant code, which has evolved in byacc to the point where it can be compared and tuned against bison.
  5. "Berkeley Yacc Change log, see entry "2010-06-07 Andres.Meji"". 2010-06-07. Archived from the original on 2020-11-10. Retrieved 2020-11-10.
  6. DeRemer, Frank; Pennello, Thomas (October 1982). "Efficient Computation of LALR(1) Look-Ahead Sets" (PDF). ACM Trans. Program. Lang. Syst. ACM. 4 (4): 615–649. doi:10.1145/69622.357187. ISSN 0164-0925. S2CID 52833742. Retrieved 2017-08-26.
  7. Corbett, Robert (September 24, 1998). "Re: Anyone extended MAXTABLE in yacc parsers?". Newsgroup: comp.compilers. Usenet: 98-09-125@comp.compilers. Retrieved 2017-08-26.
  8. Corbett, Robert Paul (June 1985). Static Semantics and Compiler Error Recovery (Ph.D.). University of California, Berkeley. DTIC ADA611756.
  9. Corbett, Robert (September 6, 1989). "Name that PD parser generator". Newsgroup: comp.compilers. Usenet: 1989Sep6.152554.318@esegue.segue.boston.ma.us. Retrieved 2017-08-26.
  10. Corbett, Robert (October 3, 1989). "Berkeley Yacc (new version)". Newsgroup: comp.compilers. Usenet: 1989Oct3.230634.1007@esegue.segue.boston.ma.us. Retrieved 2017-08-26.
  11. Dodd, Chris (March 7, 1995). "BTYACC -- yacc with backtracking and inherited attributes". Newsgroup: comp.compilers. Usenet: 95-03-044@comp.compilers. Retrieved 2020-05-18.
  12. "README.txt". BtYacc: BackTracking Yacc. Siber Systems. Retrieved 2020-05-14.
  13. "README.BYACC". Backtracking yacc. GitHub. Retrieved 2020-05-14.
  14. Merrill, Gary H. (August 1, 1993). "Parsing Non-LR(k) grammars with yacc". Softw. Pract. Exp. 23 (8): 829–850. CiteSeerX 10.1.1.14.1958. doi:10.1002/spe.4380230803. ISSN 0038-0644. S2CID 14695500. Retrieved 2020-05-14.
  15. "btyacc(1)". Debian stretch — Debian Manpages.
  16. Dodd, Chris (13 February 2019). "ChrisDodd/btyacc". GitHub.
  17. Thurston, Adrian D.; Cordy, James R. (2006). "A Backtracking LR Algorithm for Parsing Ambiguous Context-Dependent Languages" (PDF). In Erdogmus, Hakan; Stroulia, Eleni; Stewart, Darlene A. (eds.). Proceedings of the 2006 conference of the Centre for Advanced Studies on Collaborative Research, October 16-19, 2006, Toronto, Ontario, Canada. CASCON 2006. pp. 39–53. CiteSeerX 10.1.1.518.7094. doi:10.1145/1188966.1188972. Retrieved 2020-05-14.
  18. Maslov, Vadim (October 8, 1997). "Version 1.1 of BtYacc (Backtracking Yacc) is available". Newsgroup: comp.compilers. Usenet: 97-10-039@comp.compilers. Retrieved 2020-05-18.
  19. "BtYacc: BackTracking Yacc Parser Generator". Siber Systems. Retrieved 2020-05-18.
  20. "BYACC - BERKELEY YACC". invisible-island.net. Archived from the original on 2002-04-06. Retrieved 2020-11-10.
  21. "Release t20140407". ThomasDickey/byacc-snapshots. GitHub. Retrieved 2020-05-18.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.