"Joel E. Denny" <[EMAIL PROTECTED]> writes: >> I haven't seen any response to my posts last month on problems I'm having >> with bison GLR: >> >> http://lists.gnu.org/archive/html/help-bison/2005-07/msg00013.html >> http://lists.gnu.org/archive/html/help-bison/2005-07/msg00040.html >> http://lists.gnu.org/archive/html/help-bison/2005-07/msg00017.html >> >> Were my explanations unclear? Am I correct that this is unintended >> behavior? Should I post these to bug-bison instead?
bug-bison would have been better, but I think the main problem is that Paul Hilfinger (the GLR go-to guy) is probably on vacation. > resolveValue() invokes mergeOptionSets() but doesn't remove the merged > SemanticOption's. Thus, within `if (yymerge)', resolveAction() and > userMerge() are invoked for each of several identical SemanticOption's. > This produces the redundant trees. I'm a bit worried about the storage management for the deleted nodes (did you look into that?) but the basic idea seems sound, and we can worry about any memory leaks later. I installed this patch, which doesn't quite match yours exactly but which uses the same idea. I also added the test case as you suggested. Thanks. 2005-08-21 Paul Eggert <[EMAIL PROTECTED]> * data/glr.c (yyresolveValue): Fix redundant parse tree problem reported by Joel E. Denny in <http://lists.gnu.org/archive/html/bison-patches/2005-08/msg00004.html> (trivial change). * tests/glr-regression.at (Duplicate representation of merged trees): New test, from Joel E. Denny in: <http://lists.gnu.org/archive/html/help-bison/2005-07/msg00013.html>. * THANKS: Add Joel E. Denny. Index: THANKS =================================================================== RCS file: /cvsroot/bison/bison/THANKS,v retrieving revision 1.60 diff -p -u -r1.60 THANKS --- THANKS 22 Jul 2005 21:20:58 -0000 1.60 +++ THANKS 21 Aug 2005 23:42:26 -0000 @@ -34,6 +34,7 @@ Jan Nieuwenhuizen [EMAIL PROTECTED] Jesse Thilo [EMAIL PROTECTED] Jim Kent [EMAIL PROTECTED] Jim Meyering [EMAIL PROTECTED] +Joel E. Denny [EMAIL PROTECTED] Juan Manuel Guerrero [EMAIL PROTECTED] Kees Zeelenberg [EMAIL PROTECTED] Keith Browne [EMAIL PROTECTED] Index: data/glr.c =================================================================== RCS file: /cvsroot/bison/bison/data/glr.c,v retrieving revision 1.111 diff -p -u -r1.111 glr.c --- data/glr.c 25 Jul 2005 04:20:39 -0000 1.111 +++ data/glr.c 21 Aug 2005 23:42:26 -0000 @@ -1606,35 +1606,44 @@ yyresolveValue (yySemanticOption* yyopti YYSTYPE* yyvalp, YYLTYPE* yylocp]b4_user_formals[) { yySemanticOption* yybest; - yySemanticOption* yyp; + yySemanticOption** yypp; yybool yymerge; yybest = yyoptionList; yymerge = yyfalse; - for (yyp = yyoptionList->yynext; yyp != NULL; yyp = yyp->yynext) + for (yypp = &yyoptionList->yynext; *yypp != NULL; ) { + yySemanticOption* yyp = *yypp; + if (yyidenticalOptions (yybest, yyp)) - yymergeOptionSets (yybest, yyp); + { + yymergeOptionSets (yybest, yyp); + *yypp = yyp->yynext; + } else - switch (yypreference (yybest, yyp)) - { - case 0: - yyreportAmbiguity (yybest, yyp, yystack]b4_pure_args[); - break; - case 1: - yymerge = yytrue; - break; - case 2: - break; - case 3: - yybest = yyp; - yymerge = yyfalse; - break; - } + { + switch (yypreference (yybest, yyp)) + { + case 0: + yyreportAmbiguity (yybest, yyp, yystack]b4_pure_args[); + break; + case 1: + yymerge = yytrue; + break; + case 2: + break; + case 3: + yybest = yyp; + yymerge = yyfalse; + break; + } + yypp = &yyp->yynext; + } } if (yymerge) { + yySemanticOption* yyp; int yyprec = yydprec[yybest->yyrule]; YYCHK (yyresolveAction (yybest, yystack, yyvalp, yylocp]b4_user_args[)); for (yyp = yybest->yynext; yyp != NULL; yyp = yyp->yynext) Index: tests/glr-regression.at =================================================================== RCS file: /cvsroot/bison/bison/tests/glr-regression.at,v retrieving revision 1.12 diff -p -u -r1.12 glr-regression.at --- tests/glr-regression.at 18 Jul 2005 18:39:01 -0000 1.12 +++ tests/glr-regression.at 21 Aug 2005 23:42:26 -0000 @@ -327,3 +327,96 @@ AT_CHECK([[echo p1 t4 o2 p1 p1 t1 o1 t2 ]], []) AT_CLEANUP + + +## ---------------------------------------------------------------------- ## +## Duplicate representation of merged trees ## +## Thanks to Joel E. Denny for this test; see ## +## <http://lists.gnu.org/archive/html/help-bison/2005-07/msg00013.html>. ## +## ---------------------------------------------------------------------- ## + +AT_SETUP([Duplicate representation of merged trees]) + +AT_DATA_GRAMMAR([glr-regr4.y], +[[%union { char *ptr; } +%type <ptr> S A A1 A2 B +%glr-parser + +%{ + #include <stdio.h> + #include <stdlib.h> + #include <string.h> + static char *merge (YYSTYPE, YYSTYPE); + static char *make_value (char *, char *); + static void yyerror (char const *); + static int yylex (void); +%} + +%% + +tree: S { printf ("%s\n", $1); } ; + +S: + A %merge<merge> { $$ = make_value ("S", $1); } + | B %merge<merge> { $$ = make_value ("S", $1); } + ; + +A: + A1 %merge<merge> { $$ = make_value ("A", $1); } + | A2 %merge<merge> { $$ = make_value ("A", $1); } + ; + +A1: 'a' { $$ = make_value ("A1", "'a'"); } ; +A2: 'a' { $$ = make_value ("A2", "'a'"); } ; +B: 'a' { $$ = make_value ("B", "'a'"); } ; + +%% + +static int +yylex (void) +{ + static char const *input = "a"; + return *input++; +} + +int +main (void) +{ + return yyparse (); +} + +static char * +make_value (char *parent, char *child) +{ + char const format[] = "%s <- %s"; + char *value = malloc (strlen (parent) + strlen (child) + sizeof format); + sprintf (value, format, parent, child); + return value; +} + +static char * +merge (YYSTYPE s1, YYSTYPE s2) +{ + char const format[] = "merge{ %s and %s }"; + char *value = malloc (strlen (s1.ptr) + strlen (s2.ptr) + sizeof format); + sprintf (value, format, s1.ptr, s2.ptr); + return value; +} + +static void +yyerror (char const *msg) +{ + printf ("%s\n", msg); +} +]]) + +AT_CHECK([[bison -o glr-regr4.c glr-regr4.y]], 0, [], +[glr-regr4.y: conflicts: 1 reduce/reduce +]) +AT_COMPILE([glr-regr4]) + +AT_CHECK([[./glr-regr4]], 0, +[[merge{ S <- merge{ A <- A1 <- 'a' and A <- A2 <- 'a' } and S <- B <- 'a' } +]], []) + +AT_CLEANUP _______________________________________________ [EMAIL PROTECTED] http://lists.gnu.org/mailman/listinfo/help-bison