Next: , Previous: , Up: A Brief History of the Greater Ungulates   [Contents][Index]


11.4 Bison

Robert Corbett actually wrote two (closely related) 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.

The main visible difference between Yacc and Byson/Bison at the time of Byson’s first release is that Byson supported the @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 its %expect-rr variant for reduce/reduce conflicts can be applied to individual rules.

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 1984), and more modern techniques for generating the lookahead sets (see 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.

Bison also has many features to support C++ that were not present in the ancestral Yacc or Byson.

Bison obsolesced all previous Yacc variants and workalikes generating C by 1995.


Next: Other Ungulates, Previous: Berkeley Yacc, Up: A Brief History of the Greater Ungulates   [Contents][Index]