redundant merges for GLR

[Joel E. Denny]

I am attempting to use bison's %glr-parser and %merge to construct parse
forests.  I'm getting duplicate representations of some trees within the
forest.  Both bison 1.875 and 2.0 give the same results.

The problem is that, for some grammars, the parser invokes some semantic
actions and my merge function more times than I expect.  Moreover, the
number of actual invocations of my merge function is more than the number
of merges listed in the parser trace.  In general, the parser trace seems
correct to me.

At the end of this email is a simple bison spec that demonstrates the
problem.  The bison-generated code is a complete C program with yylex(),
yyerror(), and main() already defined, so it is easy to try out.  Below
the bison spec, I have placed the bison compilation output and the parser
trace.

Reformatted for readability, the following is the output I would expect
from the start production's semantic action:

  merge{
    S <- merge{
      A <- A1 <- 'a' and A <- A2 <- 'a'
    } and S <- B <- 'a'
  }

Reformatted for readability, the actual output is:

  merge{
    merge{
      S <- merge{
        A <- A1 <- 'a' and A <- A2 <- 'a'
      } and S <- B <- 'a'
    } and S <- A <- A2 <- 'a'
  }

Notice that the tree S <- A <- A2 <- 'a' is represented twice.  If this is
the appropriate output, I would very much appreciate some enlightenment.
If not, is there a bug in bison's GLR implementation?

Thanks.

Joel Denny

--------------------------------------------------------
%union { char * ptr; }
%type <ptr> S A A1 A2 B
%glr-parser

%{
  #include <stdio.h>
  char * merge( union YYSTYPE s1, union YYSTYPE s2 );
  char * make_value( char * parent, char * child );
  void yyerror( char * msg );
  int yylex();
%}

%%

tree: S { printf( "%s\n", $1 ); } /* rule 1 */

S:
  A   %merge<merge> { $$ = make_value( "S", $1 ); } /* rule 2 */
  | B %merge<merge> { $$ = make_value( "S", $1 ); } /* rule 3 */
  ;

A:
  A1   %merge<merge> { $$ = make_value( "A", $1 ); } /* rule 4 */
  | A2 %merge<merge> { $$ = make_value( "A", $1 ); } /* rule 5 */
  ;

A1: 'a' { $$ = make_value( "A1", "'a'" ); } /* rule 6 */
A2: 'a' { $$ = make_value( "A2", "'a'" ); } /* rule 7 */
B:  'a' { $$ = make_value( "B", "'a'" );  } /* rule 8 */

%%

int yylex() {
  static int once = 0;
  if ( !once ) { once = 1; return 'a'; }
  return 0;
}

int main() {
  yydebug = 1;
  yyparse();
  return 0;
}

char * make_value( char * parent, char * child ) {
  char * value = malloc( 1024 );
  sprintf( value, "%s <- %s", parent, child );
  return value;
}

char * merge( union YYSTYPE s1, union YYSTYPE s2 ) {
  char * value = malloc( 1024 );
  sprintf( value, "merge{ %s and %s }", s1.ptr, s2.ptr );
  return value;
}

void yyerror( char * msg ) {
  printf( "%s\n", msg );
}
--------------------------------------------------------


--------------------------------------------------------
glr_merge.bison: conflicts: 1 reduce/reduce
Starting parse
Entering state 0
Reading a token: Next token is token 'a' ()
Shifting token 'a' ()
Entering state 1
Reading a token: Next token is token $end ()
Stack 0 Entering state 1
Splitting off stack 1 from 0.
Reduced stack 1 by rule #7; action deferred. Now in state 6.
Stack 1 Entering state 6
Reduced stack 1 by rule #5; action deferred. Now in state 4.
Stack 1 Entering state 4
Reduced stack 1 by rule #2; action deferred. Now in state 3.
Stack 1 Entering state 3
Reduced stack 1 by rule #1; action deferred. Now in state 2.
Stack 1 Entering state 2
On stack 1, shifting token $end ()
, now in state #8
Splitting off stack 2 from 0.
Reduced stack 2 by rule #8; action deferred. Now in state 7.
Stack 2 Entering state 7
Reduced stack 2 by rule #3; action deferred. Now in state 3.
Stack 2 Entering state 3
Reduced stack 2 by rule #1; action deferred. Now in state 2.
Merging stack 2 into stack 1.
Reduced stack 0 by rule #6; action deferred. Now in state 5.
Stack 0 Entering state 5
Reduced stack 0 by rule #4; action deferred. Now in state 4.
Stack 0 Entering state 4
Reduced stack 0 by rule #2; action deferred. Now in state 3.
Stack 0 Entering state 3
Reduced stack 0 by rule #1; action deferred. Now in state 2.
Merging stack 0 into stack 1.
Removing dead stacks.
Rename stack 1 -> 0.
Returning to deterministic operation.
Entering state 8
--------------------------------------------------------