[comp.sys.amiga] Bison mystery

dtsteen@dahlia.waterloo.edu (06/21/89)

Recently, I have been playing with Bison and Flex (from Fred Fish disks
160-170 or thereabouts).  Wonderful programs!  I was able to build the
ANSI C grammar from one of those disks with no problems.  I tried rebuilding
"CDecl", which had originally been built with yacc and lex, and not only
did it work, but the resulting executable was 12K smaller than the
original one (same compiler).  I was ecstatic, and ready to place absolute
faith in these programs, until I tried to process the following grammar:

------------------------------
%token DING DONG DELL
%%
rhyme   :   sound place
        ;
sound   :   DING DONG
        ;
place   :   DELL
        ;
------------------------------

This is from a mini-tutorial on yacc in an AT&T book.  Surprise!  It
didn't work.  Without an instant's hesitation, Bison reported that it
was out of memory.  A quick check yielded 650K free, and barely any of
it touched before the error occurred.

I've been experimenting for a while now, and have come to the following
conclusion:  Any grammar I write myself and try (i.e. anything short)
will bomb, whereas any grammar taken from elsewhere (usually complex)
will work just fine.  Am I crazy or what?  Has anyone else been playing
with these programs and observed similar results?

The Bison executable is 63356 bytes long.  I have tried stack sizes
from 50K to 200K with no avail.  Memory fragmentation is unlikely to
be the problem.  And both Yacc and the (presumably newer) version of
Bison on this Unix system compile the above grammar just fine.

Markus Wandel
(519) 884-9669

dtsteen@dahlia.waterloo.edu (06/23/89)

In article <14622@watdragon.waterloo.edu> I write:

>Recently, I have been playing with Bison and Flex (from Fred Fish disks
>160-170 or thereabouts)...

>...This is from a mini-tutorial on yacc in an AT&T book.  Surprise!  It
>didn't work.  Without an instant's hesitation, Bison reported that it
>was out of memory.  A quick check yielded 650K free, and barely any of
>it touched before the error occurred.

Apparently I was not the only one who noticed this bug.  Well, I found
it and here's the scoop:

Bison uses the calloc() function to obtain its memory.  When the grammar
it processes is very simple, one or more calls to calloc() are made
requesting that it allocate zero bytes of memory.

On Unix this is OK -- each request to allocate zero bytes results in a
valid pointer, and the pointers are all different.  With Lattice C,
a calloc(0,1) returns zero.  This causes Bison to believe that it has
run out of memory, and thus the problem.  Clearly a bug in Bison, but
one which only shows with this particular implementation of calloc().

Fortunately, the fix is easy.  Just make the change below to the file
"allocate.c" and recompile.

  block = calloc(n,1);
  if (block == NULL && n != 0)
                   ^^^^^^^^^^
    {
      fprintf(stderr, "bison: memory exhausted\n");
      done(1);
    }

Note that apart from this but, Bison appears to be a *very* solid port.
I went from initially removing it from its Zoo archive to compiling and
trying several large grammars, totalling four hours or so, without a
single crash or reboot.  We need more programs like this.

Markus Wandel
(519) 884-9669