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.
