Re: My plans for Bison: history

[Akim Demaille]

> Le 17 févr. 2019 à 12:25, Akim Demaille <address@hidden> a écrit :
> 
> commit 93371999ee617644d56c82774b7af453cda05291
> Author: Eric S. Raymond <address@hidden>
> Date:   Wed Feb 13 10:39:54 2019 -0500
> 
>    doc: a history section
> 
>    * bison.texi (A Brief History of the Greater Ungulates): New section.

On top of it, I installed this:

commit cbf213915cca529c95f56da2005075469f45af6a
Author: Akim Demaille <address@hidden>
Date:   Sun Feb 17 12:20:40 2019 +0100

    doc: style changes
    
    * doc/bison.texi (Bibliography): Add [Corbett 1984] and [Johnson
    1978].
    (History): Use them.
    And other minor changes.

diff --git a/doc/bison.texi b/doc/bison.texi
index 62788e9f..631f27e4 100644
--- a/doc/bison.texi
+++ b/doc/bison.texi
@@ -379,7 +379,7 @@ Java Parsers
 A Brief History of the Greater Ungulates
 
 * Yacc::                        The original Yacc
-* yacchack::                    An obscure early implementation of re-entrancy
+* yacchack::                    An obscure early implementation of reentrancy
 * Byacc::                       Berkeley Yacc
 * Bison::                       This program
 * Other ungulates::             Similar programs
@@ -13010,20 +13010,21 @@ 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 address@hidden(Because of the acronym, the name is sometimes
+Bison originated as a workalike of a program called Yacc --- Yet Another
+Compiler address@hidden of the acronym, the name is sometimes
 given as ``YACC'', but Johnson used ``Yacc'' in the descriptive paper
 included in the
 @url{https://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
+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.
+Portable C Compiler, pcc. The same person, Steven C. Johnson, wrote Yacc and
+the original pcc.
 
-According to the author, Yacc was first invented in 1971 and reached a
-form recognizably similar to the C version in 1973.  Johnson published
address@hidden://dx.doi.org/10.1145/512760.512771, A Portable Compiler: Theory
-and Practice} in the Proceedings of the 5th ACM POPL Symposium in 1978.
+According to the author
address@hidden@url{https://lists.gnu.org/archive/html/bison-patches/2019-02/msg00061.html}},
+Yacc was first invented in 1971 and reached a form recognizably similar to
+the C version in 1973.  Johnson published @cite{A Portable Compiler: Theory
+and Practice} (@pxref{Bibliography,,Johnson 1978}).
 
 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
@@ -13052,17 +13053,16 @@ became available a few years later.
 @node Byacc
 @section Berkeley Yacc
 
-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.
+Berkeley Yacc was originated in 1985 by Robert Corbett
+(@pxref{Bibliography,,Corbett 1984}).  It was originally named ``zoo'', but
+by October 1989 it became known as Berkeley Yacc or byacc.
 
 Berkeley Yacc had three advantages over the ancestral Yacc: it generated
-faster parsers, it could generate reentrant parsers, and the source cade
+faster parsers, it could generate reentrant parsers, and the source code
 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.
+proprietary license.  The better performance came from implementing
+techniques from DeRemer and Penello's seminal paper on LALR parsing
+(@pxref{Bibliography,,DeRemer 1982}).
 
 Use of byacc spread rapidly due to its public domain license. However, once
 Bison became available, byacc itself passed out of general use.
@@ -13071,41 +13071,39 @@ Bison became available, byacc itself passed out of 
general use.
 @section Bison
 
 Robert Corbett actually wrote two (closely related) LALR parsers in 1985,
-both using the DeRemer/Penello techniques. One was zoo, the other was
+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.
 
 The main visible difference between Yacc and Byson/Bison at the time of
-Byson's fiest release is that Byson supported the @@N construction (giving
-access to the starting and ending line number and character number
+Byson's first release is that Byson supported the @code{@@@var{n}} construct
+(giving access to the starting and ending line number and character number
 associated with any of the symbols in the current rule).
 
-There was also the command '%expect N' which said not to mention
-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.
+There was also the command @samp{%expect @var{n}} which said not to mention the
+conflicts if there are @var{n} shift/reduce conflicts and no reduce/reduce
+conflicts.  In more recent versions of Bison, @code{%expect} and its
address@hidden variant for reduce-reduce conflicts can be applied to
+individual rules.
 
-Later version of Bison added nany more new features.
+Later versions of Bison added many more new features.
 
 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, @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 .
+the parse tables (@pxref{Bibliography,,Corbett 1984}), and more modern
+techniques for generating the lookahead sets (@pxref{Bibliography,,DeRemer
+1982}).  This approach is the standard one since then.
 
 (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.
+Named references, semantic predicates, @code{%locations},
address@hidden, @code{%printer}, %destructor, dumps to DOT,
address@hidden, @code{%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.
@@ -14303,7 +14301,24 @@ resolution.  @xref{Unreachable States}.
 @node Bibliography
 @unnumbered Bibliography
 
address@hidden Please follow the followint canvas to add more references.
+
 @table @asis
address@hidden [Corbett 1984]
address@hidden author
+Robert Paul Corbett,
address@hidden title
+Static Semantics in Compiler Error Recovery
address@hidden in
+Ph.D. Dissertation, Report No. UCB/CSD 85/251,
address@hidden where
+Departement of Electrical Engineering and Computer Science, Compute Science
+Division, University of California, Berkeley, California
address@hidden when
+(June 1985).
address@hidden url
address@hidden://xtf.lib.berkeley.edu/reports/TRWebData/accessPages/CSD-85-251.html}
+
 @item [Denny 2008]
 Joel E. Denny and Brian A. Malloy, IELR(1): Practical LR(1) Parser Tables
 for Non-LR(1) Grammars with Conflict Resolution, in @cite{Proceedings of the
@@ -14328,6 +14343,14 @@ Look-Ahead Sets, in @cite{ACM Transactions on 
Programming Languages and
 Systems}, Vol.@: 4, No.@: 4 (October 1982), pp.@:
 615--649. @uref{http://dx.doi.org/10.1145/69622.357187}
 
address@hidden [Johnson 1978]
+Steven C. Johnson,
+A portable compiler: theory and practice,
+in @cite{Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on
+Principles of programming languages} (POPL '78),
+pp.@: 97--104.
address@hidden://dx.doi.org/10.1145/512760.512771}.
+
 @item [Knuth 1965]
 Donald E. Knuth, On the Translation of Languages from Left to Right, in
 @cite{Information and Control}, Vol.@: 8, Issue 6 (December 1965), pp.@:
@@ -14360,8 +14383,8 @@ London, Department of Computer Science, TR-00-12 
(December 2000).
 @c LocalWords: NUM exp subsubsection kbd Ctrl ctype EOF getchar isdigit nonfree
 @c LocalWords: ungetc stdin scanf sc calc ulator ls lm cc NEG prec yyerrok rr
 @c LocalWords: longjmp fprintf stderr yylloc YYLTYPE cos ln Stallman Destructor
address@hidden LocalWords: symrec val tptr FUN func struct sym enum IEC syntaxes
address@hidden LocalWords: fun putsym getsym arith funs atan ptr malloc sizeof 
Lex
address@hidden LocalWords: symrec val tptr FUN func struct sym enum IEC 
syntaxes Byacc
address@hidden LocalWords: fun putsym getsym arith funs atan ptr malloc sizeof 
Lex pcc
 @c LocalWords: strlen strcpy fctn strcmp isalpha symbuf realloc isalnum DOTDOT
 @c LocalWords: ptypes itype YYPRINT trigraphs yytname expseq vindex dtype Unary
 @c LocalWords: Rhs YYRHSLOC LE nonassoc op deffn typeless yynerrs nonterminal
@@ -14410,7 +14433,11 @@ London, Department of Computer Science, TR-00-12 
(December 2000).
 @c LocalWords: fdiagnostics setlocale nullptr ast srcdir copyable iff drv
 @c LocalWords: deftypefunx pragma Wnull dereference Wdocumentation elif ish
 @c LocalWords: Wdeprecated Wregister noinput yyloc yypos PODs sstream Wsign
address@hidden LocalWords:  typename emplace Wconversion Wshorten
address@hidden LocalWords: typename emplace Wconversion Wshorten yacchack 
reentrancy
address@hidden LocalWords: Relocatability exprs fixit Wyacc parseable fixits 
ffixit
address@hidden LocalWords: DNDEBUG cstring Wzero workalike POPL workalikes 
byacc UCB
address@hidden LocalWords: Penello's Penello Byson Byson's Corbett's CSD TOPLAS 
PDP
address@hidden LocalWords: Beazley's goyacc ocamlyacc
 
 @c Local Variables:
 @c ispell-dictionary: "american"