headers
Joel E. Denny | 3 May 00:27

Re: Multiple, different, %merge of a token sequence

On Mon, 1 May 2006, Derek M Jones wrote:

> I'm not sure if the following is a feature or a bug.
> 
> There are four parses of the C input (x)*sizeof(y);
> 
> (x) can be parsed as:
> 
>    1) a cast of the expression *sizeof(y) to the type x (not
>       possible semantically, but this is syntax)
>    2) the left operand of the multiplication operator *
> 
> sizeof(y) can be parsed as:
> 
>    1) the sizeof the expression (y)
>    2) the sizeof the type y
> 
> I put %merge on the production for sizeof (see below) and
> was expecting the sizeof ambiguity to  be 'fully' resolved.
> 
> What happens is that the bison generated parser builds
> all four parse stacks, resolves one pair of sizeof
> ambiguities by calling sizeof_merge (leaving three stacks)
> and then calls multiplicative_merge twice (leaving 1 stack).
> 
> I think there should be two calls to sizeof_merge and one to
> multiplicative_merge.

I've confirmed this behavior with both Bison 2.1 and the latest CVS 
sources.
(Continue reading)

Permalink | Reply | 8 comments |
headers
Derek M Jones | 3 May 02:19
Picon

Re: Multiple, different, %merge of a token sequence

Joel,

Thanks for the prompt reply.

> I've now given your code a much closer look.  This behavior is another 
> manifestation of a complex Bison GLR problem that I've known about for a 
> while and am still working on.  Unfortunately, I don't believe I've 
> previously posted about it.  It touches on many areas of the GLR 
> implementation, and I just haven't found the time yet to properly describe 
> what I know.

Ok.  It would be useful to add a warning to the documentation that
this kind of thing sometimes happens (at least for the moment).

> Unfortunately, it seems like the most obvious solution will worsen the 
> parser's time complexity.  I'm exploring a more sophisticated solution, 
> but I'm afraid it'll be a while before I return to it.

I can parse + other not very complicated stuff all the .c files in
the gcc/postgresql/openafs/openmotif/netscape (original C version)
source trees in under 30 cpu seconds.  Having this increased to 60
seconds would not be a problem.

> If your %merge functions eliminate subtrees, it appears that you are 
> right: this bug actually does increase subtree sharing for your example 
> input because it delays elimination until higher up.

For me this is not really a problem because it appears to be rare and I
can ignore the leaked memory caused by not doing the free's. A bigger
potential problem is that the high level merge has to do some analysis
(Continue reading)

Permalink | Reply | 2 comments |
headers
Paul Eggert | 4 May 01:31
Favicon

Re: Multiple, different, %merge of a token sequence

"Joel E. Denny" <jdenny <at> ces.clemson.edu> writes:

> One characteristic of the underlying problem is that Bison-generated 
> parsers are not careful about how they merge parse trees.

This all sounds vaguely familiar.  Have you read Scott et al, where
they talk about the bugs in Tomita's original algorithm?  It might be
worth a look-see, if only to catch similar bugs in Bison's GLR
implementation.

http://www.cs.rhul.ac.uk/research/languages/publications/tomita_style_1.ps
Permalink | Reply | 2 comments |
headers
Joel E. Denny | 6 May 20:51

Re: Multiple, different, %merge of a token sequence

On Wed, 3 May 2006, Derek M Jones wrote:

> Ok.  It would be useful to add a warning to the documentation that
> this kind of thing sometimes happens (at least for the moment).

Yes, I agree, but it's been an issue of finding time.

> > Unfortunately, it seems like the most obvious solution will worsen the
> > parser's time complexity.  I'm exploring a more sophisticated solution, but
> > I'm afraid it'll be a while before I return to it.
> 
> I can parse + other not very complicated stuff all the .c files in
> the gcc/postgresql/openafs/openmotif/netscape (original C version)
> source trees in under 30 cpu seconds.  Having this increased to 60
> seconds would not be a problem.

I don't know yet what the penalty would be.

> Would I be correct to say this subtree sharing would not occur if
> the grammar was left recursive?

Sorry, I don't follow.

Joel

_______________________________________________
help-bison <at> gnu.org http://lists.gnu.org/mailman/listinfo/help-bison
Permalink | Reply | 0 comments |
headers
Joel E. Denny | 6 May 21:03

Re: Multiple, different, %merge of a token sequence

On Wed, 3 May 2006, Paul Eggert wrote:

> This all sounds vaguely familiar.  Have you read Scott et al, where
> they talk about the bugs in Tomita's original algorithm?  It might be
> worth a look-see, if only to catch similar bugs in Bison's GLR
> implementation.
> 
> http://www.cs.rhul.ac.uk/research/languages/publications/tomita_style_1.ps

Thanks for the link.

I was aware that there were corrections, and I too had the feeling this 
might be more than just a Bison problem.  This will take some time to 
explore.  I'll do what I can.

Joel
Permalink | Reply | 0 comments |
headers
Anthony Heading | 9 May 01:36
Picon
Favicon

strange K&R expansion of yyparse()

Hi,

I've just started to trip over a problem where a parser is not compiling
using MSVC 2005.  I'm not sure why I just started encountering this now -
maybe cygwin has only just upgraded to bison 2.1?  Anyhow, for any parser
at all, the bison=2.1 / m4=1.4.4  yacc.c skeleton code looks like this:

	/*----------.
	| yyparse.  |
	`----------*/

	#ifdef YYPARSE_PARAM
	# if defined (__STDC__) || defined (__cplusplus)
	int yyparse (void *YYPARSE_PARAM)
	# else
	int yyparse (YYPARSE_PARAM)
	void *YYPARSE_PARAM;
	# endif
	#else /* ! YYPARSE_PARAM */
	#if defined (__STDC__) || defined (__cplusplus)
	int
	yyparse (void)
	#else
	int
	yyparse ()
	    ;		<==========  should this semicolon be here?
	#endif
	#endif
	{
(Continue reading)

Permalink | Reply | 2 comments |
headers
Tim Van Holder | 9 May 08:42
Picon
Favicon

Re: strange K&R expansion of yyparse()

Anthony Heading wrote:
> Hi,
> 
> I've just started to trip over a problem where a parser is not compiling
> using MSVC 2005.  I'm not sure why I just started encountering this now -
> maybe cygwin has only just upgraded to bison 2.1?  Anyhow, for any parser
> at all, the bison=2.1 / m4=1.4.4  yacc.c skeleton code looks like this:
> 
> 
> 	/*----------.
> 	| yyparse.  |
> 	`----------*/
> 
> 	#ifdef YYPARSE_PARAM
> 	# if defined (__STDC__) || defined (__cplusplus)
> 	int yyparse (void *YYPARSE_PARAM)
> 	# else
> 	int yyparse (YYPARSE_PARAM)
> 	void *YYPARSE_PARAM;
> 	# endif
> 	#else /* ! YYPARSE_PARAM */
> 	#if defined (__STDC__) || defined (__cplusplus)
> 	int
> 	yyparse (void)
> 	#else
> 	int
> 	yyparse ()
> 	    ;		<==========  should this semicolon be here?
> 	#endif
> 	#endif
(Continue reading)

Permalink | Reply | 0 comments |
headers
Paul Eggert | 9 May 09:07
Favicon

Re: strange K&R expansion of yyparse()

Anthony Heading <aheading <at> jpmorgan.com> writes:

> 	int
> 	yyparse ()
> 	    ;		<==========  should this semicolon be here?

No.  Thanks for reporting it.  That bug is fixed in the latest
test version of Bison <ftp://alpha.gnu.org/gnu/bison/bison-2.1a.tar.gz>
and the fix should appear in the next stable release.

> (As a sidenote, I was a bit surprised to see that this was falling through
> a K&R code path using Microsoft's latest compiler!

We have a workaround for this in 2.1a as well.

> Given it's 2006, should K&R support maybe not be relegated to
> a special YY_ANCIENT_KR_COMPILER type of symbol?)

Maybe after 2.2 comes out; I don't want to jinx things by making
changes now.

> This communication is for informational purposes only.

It would help the rest of us a bit if you found a more congenial place
to send public email from, one that doesn't append time-wasting (and
inadvertently hilarious) disclaimers like that.
Permalink | Reply | 0 comments |
headers
Jon Nall | 9 May 22:08
Picon

Re: redefining malloc and free throw exceptions in bison 2.1

Hi all,
Regarding the patch mentioned at:
http://lists.gnu.org/archive/html/bug-bison/2006-04/msg00023.html

I find that I still get a compiler error when I specify the -pedantic flag
to g++.

I'm attaching a trivial input file, test.ypp. I can reproduce this error
with:
bison test.ypp -o test.cpp
g++ -pedantic -o test test.cpp

nall:~ [1304]$ g++ -pedantic -o test test.cpp
test.cpp:184: error: declaration of 'void* malloc(long unsigned int)' throws
different exceptions
/usr/include/stdlib.h:589: error: from previous declaration 'void*
malloc(size_t) throw ()'
test.cpp:191: error: declaration of 'void free(void*)' throws different
exceptions
/usr/include/stdlib.h:603: error: from previous declaration 'void
free(void*) throw ()'

Versions:
g++: (GCC) 4.1.0 20060304 (Red Hat 4.1.0-3)
bison: 2.1 (with the patch from the URL above applied)
glibc: 2.4.4

Can other reproduce this? Please CC me on any responses as I'm not
subscribed to the mailing list.
(Continue reading)

Permalink | Reply | 0 comments |
headers
Jon Nall | 10 May 19:02
Picon

Re: redefining malloc and free throw exceptions in bison 2.1

Hi all,
Regarding the patch mentioned at:
http://lists.gnu.org/archive/html/bug-bison/2006-04/msg00023.html

I find that I still get a compiler error when I specify the -pedantic flag
to g++.

I'm attaching a trivial input file, test.ypp. I can reproduce this error
with:
bison test.ypp -o test.cpp
g++ -pedantic -o test test.cpp

nall:~ [1304]$ g++ -pedantic -o test test.cpp
test.cpp:184: error: declaration of 'void* malloc(long unsigned int)' throws
different exceptions
/usr/include/stdlib.h:589: error: from previous declaration 'void*
malloc(size_t) throw ()'
test.cpp:191: error: declaration of 'void free(void*)' throws different
exceptions
/usr/include/stdlib.h:603: error: from previous declaration 'void
free(void*) throw ()'

Versions:
g++: (GCC) 4.1.0 20060304 (Red Hat 4.1.0-3)
bison: 2.1 (with the patch from the URL above applied)
glibc: 2.4.4

Can other reproduce this? Please CC me on any responses as I'm not
subscribed to the mailing list.
(Continue reading)

Permalink | Reply | 501 comments |

Gmane