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

[Michel Rosien]

Hello,

I have managed to produce a reasonable small piece of code that still
contains the infinite loop. It consists of 3 files which I have included 
below.
The files are: parser.y, scanner.y and input.txt

Below that I've included the commands necessary to make the program.
Below that I've included the versions of the software that I used.

The grammar in the parser.y file is a hugely simplified version of the one 
that I need. It
only consists of the rules necessary to reproduce the loop for the specific 
input string in
input.txt

One observation: If I change the following subset of the grammar rules:


  NT5 : NT4              %merge<MergeRule>
  ;

  NT6 : P1 NT1 O1 T3 P2 %merge<MergeRule>
          | NT5                        %merge<MergeRule>
  ;

to:

  NT6 : P1 NT1 O1 T3 P2 %merge<MergeRule>
          | NT4                       %merge<MergeRule>
  ;

then the program does NOT go into an infinite loop. If I leave it, it DOES 
go into an infinite loop.
This is kind of strange since the NT5 : NT4 rule seems like a useless rule.

Regards,

Michel

<<<FILES AND OTHER STUFF BELOW>>>


***********
** FILES   **
***********

**************
** parser.y       **
**  START      **
**************

%{
#include <stdio.h>
#include <assert.h>
#include "parser.tab.h"

YYSTYPE MergeRule (YYSTYPE x0, YYSTYPE x1);
void yyerror(char const * s);
extern int yylex();
extern FILE* yyin;
%}

%defines
%error-verbose
%glr-parser

%token BAD_CHAR
%token P1 P2 T1 T2 T3 T4 O1 O2

%%

S : P1 T4 O2 NT6 P2  %merge<MergeRule>
;

NT1 : P1 T1 O1 T2 P2 %merge<MergeRule>
;

NT2 : NT1             %merge<MergeRule>
   | P1 NT1 O1 T3 P2 %merge<MergeRule>
;

NT3 : T3              %merge<MergeRule>
   | P1 NT1 O1 T3 P2 %merge<MergeRule>
;

NT4 : NT3              %merge<MergeRule>
   | NT2              %merge<MergeRule>
   | P1 NT2 O1 NT3 P2 %merge<MergeRule>
;

NT5 : NT4              %merge<MergeRule>
;

NT6 : P1 NT1 O1 T3 P2 %merge<MergeRule>
   | NT5             %merge<MergeRule>
;

%%

YYSTYPE MergeRule (YYSTYPE x0, YYSTYPE x1) {
 fprintf(stderr,"merging %d, %d -> %d\n",x0,x1,x0);
 return x0;
}

void yyerror(char const * s) {
 fprintf(stderr,"error: %s\n",s);
}

int main() {
 yyin = fopen("input.txt","r");
 assert(yyin);
 fprintf(stderr,"starting parse.\n");
 if (yyparse()) {
   fprintf(stderr,"parse failed.\n");
 }
 else {
   fprintf(stderr,"parse OK.\n");
 }
 fprintf(stderr,"done.\n");
}

**************
** parser.y       **
**   END          **
**************

***************
** scanner.y       **
**   START       **
***************

%{
#include "parser.tab.h"
#include <assert.h>
#include <stdio.h>
%}

%option noyywrap
%option yylineno
%option never-interactive

MACRO_DIGIT [0-9]
MACRO_INTEGER -?{MACRO_DIGIT}+
MACRO_IDENTIFIER [a-zA-Z_]([a-zA-Z0-9_])*

%%

"p1"  {return P1;}
"p2"  {return P2;}
"o1" {return O1;}
"o2" {return O2;}
"t1" {return T1;}
"t2" {return T2;}
"t3" {return T3;}
"t4" {return T4;}

[ \t\n]+ /* Eat up whitespace */

. {return BAD_CHAR;}

%%

***************
** scanner.y       **
**    END          **
***************

***************
** input.txt         **
**   START       **
***************

p1 t4 o2 p1 p1 t1 o1 t2 p2 o1 t3 p2 p2


***************
** input.txt         **
**    END          **
***************


***************************
** COMMANDS TO BUILD **
***************************

$ dos2unix *
a.exe: done.
go: done.
input.txt: done.
lex.yy.c: done.
parser.tab.c: done.
parser.tab.h: done.
parser.y: done.
scanner.y: done.

$ bison parser.y
parser.y: conflicts: 1 shift/reduce, 1 reduce/reduce

$ flex scanner.y

$ gcc lex.yy.c parser.tab.c

***************************
** SOFTWARE VERSIONS **
***************************

$ bison --version
bison (GNU Bison) 2.0
Written by Robert Corbett and Richard Stallman.

Copyright (C) 2004 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ flex --version
flex 2.5.31

$ gcc --version
gcc (GCC) 3.3.3 (cygwin special)
Copyright (C) 2003 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.