Re: Grammar for optional elements

torbenm@app-2.diku.dk (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen)
Mon, 18 Jun 2007 14:06:02 +0200

          From comp.compilers

Related articles
Grammar for optional elements coolmohitz@gmail.com (Mohitz) (2007-06-12)
Re: Grammar for optional elements torbenm@app-6.diku.dk (2007-06-14)
Re: Grammar for optional elements anton@mips.complang.tuwien.ac.at (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 148f3wg02@sneakemail.com (Karsten Nyblad) (2007-06-17)
Re: Grammar for optional elements dot@dotat.at (Tony Finch) (2007-06-17)
Re: Grammar for optional elements torbenm@app-2.diku.dk (2007-06-18)
Re: Grammar for optional elements cfc@shell01.TheWorld.com (Chris F Clark) (2007-06-19)
Re: Grammar for optional elements dot@dotat.at (Tony Finch) (2007-06-19)
Re: Grammar for optional elements lowell@coasttocoastresearch.com (Lowell Thomas) (2007-06-19)
Re: Grammar for optional elements dot@dotat.at (Tony Finch) (2007-06-20)
Re: Grammar for optional elements Meyer-Eltz@t-online.de (Detlef Meyer-Eltz) (2007-06-20)
Re: Grammar for optional elements cfc@shell01.TheWorld.com (Chris F Clark) (2007-06-21)
[3 later articles]
| List of all articles for this month |

From: torbenm@app-2.diku.dk (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen)
Newsgroups: comp.compilers
Date: Mon, 18 Jun 2007 14:06:02 +0200
Organization: Department of Computer Science, University of Copenhagen
References: 07-06-019 07-06-020 07-06-024
Keywords: parse, design

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



Post a followup to this message

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