[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Bison 3.7.2 released

From: Akim Demaille
Subject: Bison 3.7.2 released
Date: Sat, 5 Sep 2020 18:40:45 +0200

Bison 3.7.2 is a bug fix release of Bison 3.7.  See the NEWS below for
more details.

Bison 3.7 introduced the generation of counterexamples for conflicts,
contributed by Vincent Imbimbo.  For instance on a grammar featuring the
infamous "dangling else" problem, "bison -Wcounterexamples" now gives:

    $ bison -Wcounterexamples else.y
    else.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
    else.y: warning: shift/reduce conflict on token "else" [-Wcounterexamples]
      Example: "if" exp "then" "if" exp "then" exp • "else" exp
      Shift derivation
        ↳ "if" exp "then" exp
                          ↳ "if" exp "then" exp • "else" exp
      Reduce derivation
        ↳ "if" exp "then" exp                     "else" exp
                          ↳ "if" exp "then" exp •

which actually proves that the grammar is ambiguous by exhibiting a text
sample with two parse trees.



Here are the compressed sources:   (5.1MB)   (3.1MB)   (3.1MB)

Here are the GPG detached signatures[*]:

Use a mirror for higher download bandwidth:

[*] Use a .sig file to verify that the corresponding file (without the
.sig suffix) is intact.  First, be sure to download both the .sig file
and the corresponding tarball.  Then, run a command like this:

  gpg --verify bison-3.7.2.tar.gz.sig

If that command fails because you don't have the required public key,
then run this command to import it:

  gpg --keyserver --recv-keys 0DDCAA3278D5264E

and rerun the 'gpg --verify' command.

This release was bootstrapped with the following tools:
  Autoconf 2.69b.24-e9bfc
  Automake 1.16b
  Flex 2.6.4
  Gnulib v0.1-3863-ga83f488ba


GNU Bison is a general-purpose parser generator that converts an annotated
context-free grammar into a deterministic LR or generalized LR (GLR) parser
employing LALR(1) parser tables.  Bison can also generate IELR(1) or
canonical LR(1) parser tables.  Once you are proficient with Bison, you can
use it to develop a wide range of language parsers, from those used in
simple desk calculators to complex programming languages.

Bison is upward compatible with Yacc: all properly-written Yacc grammars
work with Bison with no change.  Anyone familiar with Yacc should be able to
use Bison with little trouble.  You need to be fluent in C, C++ or Java
programming in order to use Bison.

Bison and the parsers it generates are portable, they do not require any
specific compilers.

GNU Bison's home page is


* Noteworthy changes in release 3.7.2 (2020-09-05) [stable]

  This release of Bison fixes all known bugs reported for Bison in MITRE's
  Common Vulnerabilities and Exposures (CVE) system.  These vulnerabilities
  are only about bison-the-program itself, not the generated code.

  Although these bugs are typically irrelevant to how Bison is used, they
  are worth fixing if only to give users peace of mind.

  There is no known vulnerability in the generated parsers.

** Bug fixes

  Fix concurrent build issues (introduced in Bison 3.5).

  Push parsers always use YYMALLOC/YYFREE (no direct calls to malloc/free).

  Fix portability issues of the test suite, and of bison itself.

  Some unlikely crashes found by fuzzing have been fixed.  This is only
  about bison itself, not the generated parsers.

* Noteworthy changes in release 3.7.1 (2020-08-02) [stable]

** Bug fixes

  Crash when a token alias contains a NUL byte.

  Portability issues with libtextstyle.

  Portability issues of Bison itself with MSVC.

** Changes

  Improvements and fixes in the documentation.

  More precise location about symbol type redefinitions.

* Noteworthy changes in release 3.7 (2020-07-23) [stable]

** Deprecated features

  The YYPRINT macro, which works only with yacc.c and only for tokens, was
  obsoleted long ago by %printer, introduced in Bison 1.50 (November 2002).
  It is deprecated and its support will be removed eventually.

  In conformance with the recommendations of the Graphviz team, in the next
  version Bison the option `--graph` will generate a *.gv file by default,
  instead of *.dot.  A transition started in Bison 3.4.

** New features

*** Counterexample Generation

  Contributed by Vincent Imbimbo.

  When given `-Wcounterexamples`/`-Wcex`, bison will now output
  counterexamples for conflicts.

**** Unifying Counterexamples

  Unifying counterexamples are strings which can be parsed in two ways due
  to the conflict.  For example on a grammar that contains the usual
  "dangling else" ambiguity:

    $ bison else.y
    else.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
    else.y: note: rerun with option '-Wcounterexamples' to generate conflict 

    $ bison else.y -Wcex
    else.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
    else.y: warning: shift/reduce conflict on token "else" [-Wcounterexamples]
      Example: "if" exp "then" "if" exp "then" exp • "else" exp
      Shift derivation
        ↳ "if" exp "then" exp
                          ↳ "if" exp "then" exp • "else" exp
      Example: "if" exp "then" "if" exp "then" exp • "else" exp
      Reduce derivation
        ↳ "if" exp "then" exp                     "else" exp
                          ↳ "if" exp "then" exp •

  When text styling is enabled, colors are used in the examples and the
  derivations to highlight the structure of both analyses.  In this case,

    "if" exp "then" [ "if" exp "then" exp • ] "else" exp


    "if" exp "then" [ "if" exp "then" exp • "else" exp ]

  The counterexamples are "focused", in two different ways.  First, they do
  not clutter the output with all the derivations from the start symbol,
  rather they start on the "conflicted nonterminal". They go straight to the
  point.  Second, they don't "expand" nonterminal symbols uselessly.

**** Nonunifying Counterexamples

  In the case of the dangling else, Bison found an example that can be
  parsed in two ways (therefore proving that the grammar is ambiguous).
  When it cannot find such an example, it instead generates two examples
  that are the same up until the dot:

    $ bison foo.y
    foo.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
    foo.y: note: rerun with option '-Wcounterexamples' to generate conflict 
    foo.y:4.4-7: warning: rule useless in parser due to conflicts [-Wother]
        4 | a: expr
          |    ^~~~

    $ bison -Wcex foo.y
    foo.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
    foo.y: warning: shift/reduce conflict on token ID [-Wcounterexamples]
      First example: expr • ID ',' ID $end
      Shift derivation
        ↳ s                      $end
          ↳ a                 ID
            ↳ expr
              ↳ expr • ID ','
      Second example: expr • ID $end
      Reduce derivation
        ↳ s             $end
          ↳ a        ID
            ↳ expr •
    foo.y:4.4-7: warning: rule useless in parser due to conflicts [-Wother]
        4 | a: expr
          |    ^~~~

  In these cases, the parser usually doesn't have enough lookahead to
  differentiate the two given examples.

**** Reports

  Counterexamples are also included in the report when given
  `--report=counterexamples`/`-rcex` (or `--report=all`), with more
  technical details:

    State 7

      1 exp: "if" exp "then" exp •  [$end, "then", "else"]
      2    | "if" exp "then" exp • "else" exp

      "else"  shift, and go to state 8

      "else"    [reduce using rule 1 (exp)]
      $default  reduce using rule 1 (exp)

      shift/reduce conflict on token "else":
          1 exp: "if" exp "then" exp •
          2 exp: "if" exp "then" exp • "else" exp
        Example: "if" exp "then" "if" exp "then" exp • "else" exp
        Shift derivation
          ↳ "if" exp "then" exp
                            ↳ "if" exp "then" exp • "else" exp
        Example: "if" exp "then" "if" exp "then" exp • "else" exp
        Reduce derivation
          ↳ "if" exp "then" exp                     "else" exp
                            ↳ "if" exp "then" exp •

*** File prefix mapping

  Contributed by Joshua Watt.

  Bison learned a new argument, `--file-prefix-map OLD=NEW`.  Any file path
  in the output (specifically `#line` directives and `#ifdef` header guards)
  that begins with the prefix OLD will have it replaced with the prefix NEW,
  similar to the `-ffile-prefix-map` in GCC.  This option can be used to
  make bison output reproducible.

** Changes

*** Diagnostics

  When text styling is enabled and the terminal supports it, the warnings
  now include hyperlinks to the documentation.

*** Relocatable installation

  When installed to be relocatable (via `configure --enable-relocatable`),
  bison will now also look for a relocated m4.

*** C++ file names

  The `filename_type` %define variable was renamed `api.filename.type`.
  Instead of

    %define filename_type "symbol"


    %define api.filename.type {symbol}

  (Or let `bison --update` do it for you).

  It now defaults to `const std::string` instead of `std::string`.

*** Deprecated %define variable names

  The following variables have been renamed for consistency.  Backward
  compatibility is ensured, but upgrading is recommended.

    filename_type       -> api.filename.type
    package             -> api.package

*** Push parsers no longer clear their state when parsing is finished

  Previously push-parsers cleared their state when parsing was finished (on
  success and on failure).  This made it impossible to check if there were
  parse errors, since `yynerrs` was also reset.  This can be especially
  troublesome when used in autocompletion, since a parser with error
  recovery would suggest (irrelevant) expected tokens even if there were

  Now the parser state can be examined when parsing is finished.  The parser
  state is reset when starting a new parse.

** Documentation

*** Examples

  The bistromathic demonstrates %param and how to quote sources in the error

    > 123 456
    1.5-7: syntax error: expected end of file or + or - or * or / or ^ before 
        1 | 123 456
          |     ^~~

** Bug fixes

*** Include the generated header (yacc.c)

  Historically, when --defines was used, bison generated a header and pasted
  an exact copy of it into the generated parser implementation file.  Since
  Bison 3.4 it is possible to specify that the header should be `#include`d,
  and how.  For instance

    %define api.header.include {"parse.h"}


    %define api.header.include {<parser/parse.h>}

  Now api.header.include defaults to `"header-basename"`, as was intended in
  Bison 3.4, where `header-basename` is the basename of the generated
  header.  This is disabled when the generated header is ``, to
  comply with Automake's ylwrap.

*** String aliases are faithfully propagated

  Bison used to interpret user strings (i.e., decoding backslash escapes)
  when reading them, and to escape them (i.e., issue non-printable
  characters as backslash escapes, taking the locale into account) when
  outputting them.  As a consequence non-ASCII strings (say in UTF-8) ended
  up "ciphered" as sequences of backslash escapes.  This happened not only
  in the generated sources (where the compiler will reinterpret them), but
  also in all the generated reports (text, xml, html, dot, etc.).  Reports
  were therefore not readable when string aliases were not pure ASCII.
  Worse yet: the output depended on the user's locale.

  Now Bison faithfully treats the string aliases exactly the way the user
  spelled them.  This fixes all the aforementioned problems.  However, now,
  string aliases semantically equivalent but syntactically different (e.g.,
  "A", "\x41", "\101") are considered to be different.

*** Crash when generating IELR

  An old, well hidden, bug in the generation of IELR parsers was fixed.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]