From: François Pottier <firstname.lastname@example.org> To: menhir-list <email@example.com>, caml users <firstname.lastname@example.org> Subject: [Caml-list] [ANN] New release of Menhir, including bug fixes Date: Wed, 12 Feb 2020 16:36:27 +0100 Message-ID: <email@example.com> (raw) Dear users of OCaml & Menhir, It is my pleasure to announce a new release of Menhir. opam update opam upgrade menhir This release fixes two bugs in our implementation of Pager's algorithm. Menhir 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 cases) that 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. Happy parsing, -- François Pottier firstname.lastname@example.org http://cambium.inria.fr/~fpottier/ ## 2020/02/11 * Re-implement Menhir's default algorithm for constructing LR(1) automata, namely Pager's algorithm. This closes issue #21 (reported by Andrej Bauer), a bug that would sometimes cause unexplainable conflicts to appear, because states were merged too aggressively. This also removes an unreported bug that would cause the automaton to have too many states, because states were *not* merged aggressively enough. In summary, the old and new construction algorithms differ: in many cases, the resulting automaton is unchanged, but in some cases, the automaton produced by the new algorithm may have slightly 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* state `s'`. This method yields an automaton whose states form a subset of the states of the canonical LR(1) automaton. It usually has significantly fewer states than the canonical automaton, and significantly more states than the automaton produced by Pager's algorithm. The new construction method removes an unreported bug that would cause the automaton to have too many states. The automaton produced by the new algorithm will usually have significantly 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.
reply index Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions: You may reply publically to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: link
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