Re: Grammar for optional elements

anton@mips.complang.tuwien.ac.at (Anton Ertl)
Sat, 16 Jun 2007 18:27:10 GMT

          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)
[8 later articles]
| List of all articles for this month |

From: anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.compilers
Date: Sat, 16 Jun 2007 18:27:10 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
References: 07-06-019 07-06-020
Keywords: parse, design
Posted-Date: 16 Jun 2007 16:44:04 EDT

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/



Post a followup to this message

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