glr-parser: Infinite loop in yymergeOptionSets: yySemanticOption linked list doesn't terminate with NULL

[Michel Rosien]

Hello,

I am trying to make a glr parser with bison version 2.0
But the generated code ends up in an infinite loop in the
yymergeOptionSets function. After looking at that code I see
that it is iterating over a yysemanticOption linked list that
ends with a NULL.
But it never reaches NULL because at some point the
"current pointer" and "next pointer" are the same so the statement
yyz = yyz->next continues for ever.

See code below.


<code start>

/** Assuming identicalOptions (Y0,Y1), (destructively) merge the
*  alternative semantic values for the RHS-symbols of Y1 into the
*  corresponding semantic value sets of the symbols of Y0. */
static void
yymergeOptionSets (yySemanticOption* yyy0, yySemanticOption* yyy1)
{
 yyGLRState *yys0, *yys1;
 int yyn;
 for (yys0 = yyy0->yystate, yys1 = yyy1->yystate,
      yyn = yyrhsLength (yyy0->yyrule);
      yyn > 0;
      yys0 = yys0->yypred, yys1 = yys1->yypred, yyn -= 1)
   if (yys0 == yys1)
     break;
   else if (! yys0->yyresolved && ! yys1->yyresolved)
     {
yySemanticOption* yyz;
for (yyz = yys0->yysemantics.yyfirstVal; yyz->yynext != NULL;
     yyz = yyz->yynext)
  continue;
yyz->yynext = yys1->yysemantics.yyfirstVal;
     }

}

<code end>

when i put an assert (yyz != yyz->next) in the for body like this:

for (yyz = yys0->yysemantics.yyfirstVal; yyz->yynext != NULL;
     yyz = yyz->yynext)
       {
         assert(yyz != yyz->next);
  continue;
       }

the assertion will fail at some point and thus the loop will never end.

I looked at it some more and saw that the list is also bad in the functions:
yyresolveValue
yyresolveStates
yyresolveAction

at some point the yyGLRState.yysemantics.yyfirstVal linked list is not a 
proper NULL
terminated linked list.

I have not yet figured out what exactly is causing this. I'm still working 
on it.
But i'm trying to make the code & the grammar as small as possible while 
still producing
the error. I can send that as well if i'm ready with that.

But i'm wondering if somebody could give me some advice, or has any idea 
what might cause this
error.

Maybe it is worth mentioning that my grammar has a huge ammount (hundreds) 
of reduce-reduce and
shift-reduce conflicts. (I did that on purpose and rewriting the grammar is 
not an option)
Also, I compile the code with a c++ compiler. I read something about 
semantic differences between
C and C++ (page 81 of the manual) and
that the stack cannot grow if I compile the generated code with a c++ 
compiler
(unless YYSTYPE & YYLTYPE are trivial it seems which is not mentioned in the 
manual).

#if (! defined (YYSTACKEXPANDABLE) \
    && (! defined (__cplusplus) \
 || (defined (YYLTYPE_IS_TRIVIAL) && YYLTYPE_IS_TRIVIAL \
     && defined (YYSTYPE_IS_TRIVIAL) && YYSTYPE_IS_TRIVIAL)))
#define YYSTACKEXPANDABLE 1
#else
#define YYSTACKEXPANDABLE 0
#endif

Could the semantic differences between C and C++ also be a problem here?

Regards,

--Michel