* [Caml-list] [ANN] New release of Menhir, including bug fixes
@ 2020-02-12 15:36 François Pottier
0 siblings, 0 replies; 1+ messages in thread
From: François Pottier @ 2020-02-12 15:36 UTC (permalink / raw)
To: menhir-list, caml users
Dear users of OCaml & Menhir,
It is my pleasure to announce a new release of Menhir.
opam upgrade menhir
This release fixes two bugs in our implementation of Pager's algorithm.
relies on this algorithm to build an LR automaton and to decide which states
can safely be merged, where "safely" means "without creating unexplainable
conflicts". One bug (which had been known for a long time, but not fixed)
would cause Menhir to sometimes make an unsafe merge decision, thereby
creating an unexplainable conflict. The other bug (which had never been
discovered until now) would cause Menhir to sometimes miss a safe merge
decision, thereby creating an automaton with needlessly many states.
In summary, after upgrading to this version, you may find (in some
the parser produced by Menhir for your grammar has changed. It may have
slightly more or slightly fewer states than the parser produced by previous
versions of Menhir. Even in cases where the parser hasn't changed, the
numbering of the states can be different.
Feedback is welcome.
* Re-implement Menhir's default algorithm for constructing LR(1) automata,
namely Pager's algorithm. This closes issue #21 (reported by Andrej
a bug that would sometimes cause unexplainable conflicts to appear,
states were merged too aggressively. This also removes an unreported bug
that would cause the automaton to have too many states, because
*not* merged aggressively enough. In summary, the old and new
algorithms differ: in many cases, the resulting automaton is
in some cases, the automaton produced by the new algorithm may have
more or slightly fewer states.
* Re-implement Menhir's algorithm for constructing automata in `--no-pager`
mode. In this (undocumented) mode, Menhir does not merge any states, but
allows itself to redirect a transition from a state `s` to a *larger*
`s'`. This method yields an automaton whose states form a subset of the
states of the canonical LR(1) automaton. It usually has significantly
states than the canonical automaton, and significantly more states
automaton produced by Pager's algorithm. The new construction method
an unreported bug that would cause the automaton to have too many states.
The automaton produced by the new algorithm will usually have
fewer states than the automaton produced by the previous algorithm.
* Re-implement Menhir's algorithms for constructing automata in `--lalr` and
`--canonical` modes. The previous algorithms were correct, as far as we
know, so the output of the new algorithms is the same, up to a possible
renumbering of the states. The new algorithms are slightly faster.
* Increase the maximum length of a production, which used to be 127,
up to 1023. Display a polite error message if this length is exceeded.
(Problem reported by Andreas Abel.)
* The new switch `--timings-to <filename>` causes internal timing
information to be written to the file `<filename>`.
* A version of the library `fix` is now vendored (included) inside Menhir.
This should have no impact for end users, but implies that `dune` 2.2.0
or later is required.
^ permalink raw reply [flat|nested] 1+ messages in thread
only message in thread, back to index
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-02-12 15:36 [Caml-list] [ANN] New release of Menhir, including bug fixes François Pottier
caml-list - the Caml user's mailing list
Archives are clonable: git clone --mirror https://inbox.ocaml.org/caml-list
AGPL code for this site: git clone https://public-inbox.org/ public-inbox