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 -------------------------------------------------------- _______________________________________________ Help-bison@gnu.org http://lists.gnu.org/mailman/listinfo/help-bison