[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: redundant merges for GLR
From: |
Paul Eggert |
Subject: |
Re: redundant merges for GLR |
Date: |
Sun, 21 Aug 2005 16:47:51 -0700 |
User-agent: |
Gnus/5.1007 (Gnus v5.10.7) Emacs/21.4 (gnu/linux) |
"Joel E. Denny" <address@hidden> 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 <address@hidden>
* 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 address@hidden
Jesse Thilo address@hidden
Jim Kent address@hidden
Jim Meyering address@hidden
+Joel E. Denny address@hidden
Juan Manuel Guerrero address@hidden
Kees Zeelenberg address@hidden
Keith Browne address@hidden
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