Re: Grammar for optional elements

Torben Fgidius Mogensen wrote:
> Mohitz <coolmohitz@gmail.com> writes:
>
>> I need to create a parser for a language something like this.
>>
>> attribute1: value;
>> attribute2: value;
>> attribute3: value;
>>
>> All the attributes are optional but can occur only once...
>>
>> One way is to specify the grammar as follows: This doesn't do the
>> 'SINGLE occurence check'
>>
>> attribute_list : attribute_list attribute | attribute
>> attribute : ATTRIBUTE1 ':' IDENTIFIER | ATTRIBUTE2 ':' IDENTIFIER |
>> ATTRIBUTE3 ':' IDENTIFIER
> [I think the size of the grammar is only N! but that's still way too big.
-John]


Well Torben is closer to the truth than John. Assume that you want to
recognize 10 attributes called 0 to 9, and you have already defined
non terminals A0 to A9 together with productions A0 -> ... and A1 ->
... and so on such that each production recognize one attribute. Now
you define 2^10-11 non terminals called AM where M is a number
consisting of the digits are sorted and occurs only once in the number
and M is longer than one digits. Examples are A04, A56, A0123456789,
but A65 and A are not examples and A3 has already been defined. These
new symbols have productions like


A137 -> A13 A7 | A17 A3 | A37 A1 ;
A2368 -> A236 A8 | A238 A6 | A268 A3 | A368 A2 ;


Thus each nonterminal AM recognizes the attributes of the digits in M
and the attributes may occur in any order.


At last you define a non terminal Attributes which is the union of of
the empty production and all the AM non terminals, i.e.:


Attributes -> | A0 | A1 | A2 | ... | A9 | A01 | A02 | ... | A0123456789


This grammar has 2^10 non terminals and about (1+10)*2^10 productions
when we count each alternative in the above productions as separate a
production. N*2^N is much closer to 2^N than to N! when N is big.


Karsten Nyblad
148f3wg02 at sneakemail dot com

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