Re: Grammar for optional elements

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:


> 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.


The minimal DFA takes exactly 2^N states for N possible items (one
state for each possible subset), and I doubt a grammar would be
smaller, as there isn't really anything you can use the stack-like
behaviour of grammars for.


> 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.


An intersting idea, but I think I will stick to Johns suggestion about
checking it in the semantic actions. After all, semantic actions are
often used to check many other things that would be too cumbersome to
handle in the grammar (even if it is perfectly possible to do), such
as size of integer constants, range of exponents in floats, length of
variable names, number of fields in records (if these are limited),
and so on.


While you could add special grammar constructs for many of these,
there will nearly always be something you will have to defer to
semantic checking, so there is little point.


Torben

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