Re: [PATCH 0/4] Fix crash when generating IELR

[Dwight Guth]

Hi,

I can confirm that the version of bison downloaded from the link you
provided does not manifest the error in my real example, and valgrind no
longer reports any use-after-free errors on the larger example, so it looks
like it's been fixed. Since the grammar it was generated from originally,
as well as the code that generated it, is completely open source, I'd be
happy to sign some kind of waiver with respect to the intellectual property
on the bison grammar I provided you

About the original grammar: It is an automatically generated bison file,
but it is generated from a manually written grammar written in a language
called K (https://github.com/kframework/k). The grammars we generate tend
to have a large number of conflicts unless the user has chosen a grammar
carefully in order to ensure that it is LR(1), and the grammar this was
generated from is not LR(1), so bear in mind that the bison grammar we
generate from the original grammar is not one that is really suitable for
parsing that language, but I figured it shouldn't crash, either...
Basically the way it is constructed is by taking the original grammar,
duplicating certain nonterminals in order to introduce an explicit
precedence relationship between different productions (ie, that certain
productions cannot appear directly under certain nonterminals in certain
parent productions), and then automaticlaly encoding it into bison. This
seems to work well in many cases on real-world programming languages, but
obviously it becomes possible to write arbitrary grammars that you would
have to use GLR in order to parse with any real accuracy.

I am attaching the original bison grammar that the manually modified
grammar I sent you was derived from, but I think you will find that the
minimized grammar probably works better as a test case. I can also point
you to the original grammar written in K if you are curious...

On Fri, Jun 26, 2020 at 12:57 AM Akim Demaille <akim.demaille@gmail.com>
wrote:

> Hi Dwight,
>
> Thanks for the report.  I was very afraid it would be super hard to
> track and fix (I don't know much about the IELR part of Bison), but it
> turned out to be actually quite simple (the fix is the last commit,
> the shortest one).  And it's quite amazing that you are the first one
> to face this problem!
>
> Could you please try the fix to confirm it on your real case?  It's
> in:
>
> https://www.lrde.epita.fr/~akim/private/bison/bison-3.6.4.113-f6dd9.tar.gz
> https://www.lrde.epita.fr/~akim/private/bison/bison-3.6.4.113-f6dd9.tar.lz
> https://www.lrde.epita.fr/~akim/private/bison/bison-3.6.4.113-f6dd9.tar.xz
>
>
> I would like to use your (reduced) grammar as a test case, but it is
> not trivial, so I would need you to sign the FSF disclaimers.  Would
> you agree with that?
>
> About the grammar itself: it seems to be generated, isn't it?  How big
> is it?  Can you tell us more about how it is built?  Is it available
> somewhere?
>
> Thanks in advance.
>
> Cheers!
>
> Akim Demaille (4):
>   style: clean up ielr
>   style: clean up nullable
>   style: factor the access to a rule from its items
>   ielr: fix crash on memory management
>
>  THANKS               |   1 +
>  src/AnnotationList.c | 335 +++++++++++++++++++++----------------------
>  src/Sbitset.h        |   2 +
>  src/counterexample.c |   4 +-
>  src/gram.c           |  11 --
>  src/gram.h           |  10 +-
>  src/ielr.c           |  52 +++----
>  src/nullable.c       |  95 ++++++------
>  8 files changed, 239 insertions(+), 271 deletions(-)
>
> --
> 2.27.0
>
>

-- 

Dwight Guth

Director of Engineering

Email: dwight.guth@runtimeverification.com

<https://www.runtimeverification.com>

<https://github.com/dwightguth> <https://www.linkedin.com/company/3142238/>
  <https://twitter.com/rv_inc>

parser.y
Description: Binary data