>From b14d8d11cedf6d56941477fa48d8caaf00199cf8 Mon Sep 17 00:00:00 2001 From: "Eric S. Raymond" Date: Wed, 13 Feb 2019 20:29:03 -0500 Subject: [PATCH] bison.texi: Edits to "A Brief History of the Greater Ungulates" --- doc/bison.texi | 82 ++++++++++++++++++++++++++++---------------------- 1 file changed, 46 insertions(+), 36 deletions(-) diff --git a/doc/bison.texi b/doc/bison.texi index ab67dcd2..2d4ea090 100644 --- a/doc/bison.texi +++ b/doc/bison.texi @@ -13010,54 +13010,60 @@ The exceptions thrown by user-supplied parser actions and @node Yacc @section The ancestral Yacc -Bison originated as a workalike of a program called YACC - Yet Another -Compiler Compiler. YACC was written at Bell Labs as part of the very early -development of Unix; one of its first uses was to decelop the original -Portable C Compiler. The same person, Steven C. Johnson, wrote YACC and -the original pcc. +Bison originated as a workalike of a program called Yacc - Yet Another +Compiler address@hidden(Because of the acronym, the name is sometimes +given as ``YACC'', but Johnson used ``Yacc'' in the descriptive paper +included in the address@hidden://s3.amazonaws.com/plan9-bell-labs/7thEdMan/v7vol2b.pdf, Version +7 Unix Manual}} Yacc was written at Bell Labs as part of the very early +development of Unix; one of its first uses was to develop the original +Portable C Compiler. The same person, Steven C. Johnson, wrote Yacc and the +original pcc. This was so long ago that the exact year of origin is difficult to pin down. -Johnson published ``A Portable Compiler: Theory and Practice'' in the -Proceedings of the 5th ACM POPL Symposium in 1978; the YACC program itself -is generally said to have been developed in the early Seventies. +Johnson published @url{https://dx.doi.org/10.1145/512760.512771, A Portable +Compiler: Theory and Practice} in the Proceedings of the 5th ACM POPL +Symposium in 1978; the Yacc program itself is generally said to have been +developed in the early Seventies. -YACC was not itself originally written in C but in its predecessor language, +Yacc was not itself originally written in C but in its predecessor language, B. This goes far to explain its odd interface, which exposes a large number of global variables rather than bundling them into a C struct. All other -Yacc-like programs are descended from the C port of YACC. +Yacc-like programs are descended from the C port of Yacc. -YACC, through both its deployment in pcc and as a standalone tool for -generating other parsers, helped drive the early spread of Unix. YACC +Yacc, through both its deployment in pcc and as a standalone tool for +generating other parsers, helped drive the early spread of Unix. Yacc itself, however, passed out of use after around 1990 when workalikes with less restrictive licenses and more features begame available. -Original YACC became generally available when Caldera released the sources +Original Yacc became generally available when Caldera released the sources old versions of Unix up to V7 and 32V in 2002. By that time it had been -long superseded in practical use by Bison even on YACC's native Unix +long superseded in practical use by Bison even on Yacc's native Unix variants. @node yacchack @section yacchack -One of the deficiencies of original YACC was its inability to produce +One of the deficiencies of original Yacc was its inability to produce re-entrant parsers. This was first remedied by a set of drop-in modifications called ``yacchack'', published by Eric S. Raymond on USENET -around 1983. This code was quickly forgotten when zoo and Berkeley YACC +around 1983. This code was quickly forgotten when zoo and Berkeley Yacc became available a few years later. @node Byacc @section Berkeley Yacc -Berkeley YACC was originated in 1985 by Robert Corbett. It was originally -named ``zoo'', but by October 1989 it became known as Berkeley Yacc or -byacc. +Berkeley Yacc was originated in 1985 by address@hidden://apps.dtic.mil/dtic/tr/fulltext/u2/a611756.pdf, Robert Corbett}. +It was originally named ``zoo'', but by October 1989 it became known as +Berkeley Yacc or byacc. -Berkely Yacc had three advantages over the ancestral Yacc: it generated +Berkeley Yacc had three advantages over the ancestral Yacc: it generated faster parsers, it could generate re-entrant parsers, and the source cade was released to the public domain rather than being under an AT&T proprietary license. The better performance game from implementing techniques from DeRemer and Penello's seminal 1982 paper on LALR parsing; -more on this in the next entry; +more on this in the next entry. Use of byacc spread rapidly due to its public domain license. However, once Bison became available, byacc itself passed out of general use. @@ -13065,10 +13071,10 @@ Bison became available, byacc itself passed out of general use. @node Bison @section Bison -Robert Corbett actually wrote two LALR parses in 1985, both using the +Robert Corbett actually wrote two LALR parsers in 1985, both using the DeRemer/Penello techniques. One was zoo, the other was ``Byson''. In 1987 Richard Stallman began working on Byson; the name changed to Bison and the -interface became YACC-compatible. +interface became Yacc-compatible. The main difference between Yacc and Byson/Bison is that Bison supports the @@N construction (giving access to @@ -13080,34 +13086,38 @@ the conflicts if there are N shift/reduce conflicts and no reduce/reduce conflicts. In more recent versions of Bison, %expect and an %expect-rr variant for reduce-reduce conficts can be applied to individual rules. -Bison error reporting has been improved in varuous ways. Notably. ancestral -YACC and Byson did not have carets in error messages. +Bison error reporting has been improved in various ways. Notably. ancestral +Yacc and Byson did not have carets in error messages. -Compared to YACC Bison uses a faster but less space-efficient encoding for the -parse tables (see Corbett's PhD thesis from Berkeley, ``Static -Semantics in Compiler Error Recovery'', June 1985, Report No. UCB/CSD -85/251), and more modern technique for generating the lookahead sets. -See Frank DeRemer and Thomas Pennello, ``Efficient Computation of -LALR(1) Look-Ahead Sets'', ACM Transactions on Programming Languages -and Systems (TOPLAS) 4, 4 (October 1982), 615-649. Their +Compared to Yacc Bison uses a faster but less space-efficient encoding for +the parse tables (see Corbett's PhD thesis from Berkeley, ``Static Semantics +in Compiler Error Recovery'', June 1985, Report No. UCB/CSD 85/251), and +more modern technique for generating the lookahead sets. See Frank DeRemer +and Thomas Pennello, @url{https://dx.doi.org/10.1145/69622.357187, Efficient +Computation of LALR(1) Look-Ahead Sets}, ACM Transactions on Programming +Languages and Systems (TOPLAS) 4, 4 (October 1982), 615-649. Their technique has been the standard one since . +(It has also been plausibly alleged the differences in the algorithms stem +mainly from the horrible kludges that Johnson had to perpetrate to make +the original Yacc fit in a PDP-11.) + Named references, semantic predicates, %locations, %glr-parser, %printer, %destructor, dumps to DOT, %parse-param, %lex-param, and dumps to XSLT, LAC, and IELR(1) generation are new in Bison. Bison also has many features to support C++ that were not present in the -ancestral YACC or Byson. +ancestral Yacc or Byson. -Bison obsolesced all previous YACC variants and workalikes generating C by +Bison obsolesced all previous Yacc variants and workalikes generating C by 1995. @node Other ungulates @section Other ungulates -The YACC concept has frequently been ported to other languages. Some of the +The Yacc concept has frequently been ported to other languages. Some of the early ports are extinct along with the languages that hosted them; others -have been supseded by parser skeletons shipped with Bison. +have been superseded by parser skeletons shipped with Bison. However, independent implementations persist. One of the best-known still in use is David Beazley's ``PLY'' (Python Lex-Yacc) for -- 2.17.1