Re: Grammar for optional elements

torbenm@app-6.diku.dk (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.


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

Return to the comp.compilers page.
Search the comp.compilers archives again.