|Grammar for optional elements email@example.com (Mohitz) (2007-06-12)|
|Re: Grammar for optional elements firstname.lastname@example.org (2007-06-14)|
|Re: Grammar for optional elements email@example.com (2007-06-16)|
|Re: Grammar for optional elements bobduff@shell01.TheWorld.com (Robert A Duff) (2007-06-16)|
|Re: Grammar for optional elements cfc@shell01.TheWorld.com (Chris F Clark) (2007-06-16)|
|Re: Grammar for optional elements firstname.lastname@example.org (Karsten Nyblad) (2007-06-17)|
|Re: Grammar for optional elements email@example.com (Tony Finch) (2007-06-17)|
|Re: Grammar for optional elements firstname.lastname@example.org (2007-06-18)|
|Re: Grammar for optional elements cfc@shell01.TheWorld.com (Chris F Clark) (2007-06-19)|
|[8 later articles]|
|From:||email@example.com (Anton Ertl)|
|Date:||Sat, 16 Jun 2007 18:27:10 GMT|
|Organization:||Institut fuer Computersprachen, Technische Universitaet Wien|
|Posted-Date:||16 Jun 2007 16:44:04 EDT|
firstname.lastname@example.org (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen) writes:
>Even though the size of the grammar is > 2^N when the order is free,
>[I think the size of the grammar is only N! but that's still way too big. -John]
Well, N! > 2^N for N>=4. However, N! only covers the case where all
options are present; you need even more variants for the 2^N different
ways in which options can be present of absent. I don't think this
adds a big factor, though. Also, by factoring the grammar you
probably can reduce the size quite a bit, especially for large N, but
that does not make the approach practical.
If such problems occur often enough (and I think they do), one might
consider adding a special grammar construct for this kind of stuff.
Should be relatively easy to implement and use.
M. Anton Ertl
Return to the
Search the comp.compilers archives again.