Re: Grammar for optional elements

"Lowell Thomas" <lowell@coasttocoastresearch.com>
Tue, 19 Jun 2007 15:09:58 -0400

          From comp.compilers

Related articles
[4 earlier articles]
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)
Re: Grammar for optional elements dot@dotat.at (Tony Finch) (2007-06-21)
Re: Grammar for optional elements lowell@coasttocoastresearch.com (Lowell Thomas) (2007-06-22)
Re: Grammar for optional elements cfc@shell01.TheWorld.com (Chris F Clark) (2007-07-02)
| List of all articles for this month |

From: "Lowell Thomas" <lowell@coasttocoastresearch.com>
Newsgroups: comp.compilers
Date: Tue, 19 Jun 2007 15:09:58 -0400
Organization: Compilers Central
References: 07-06-019 07-06-029
Keywords: parse, design
Posted-Date: 19 Jun 2007 21:51:09 EDT

Tony Finch <dot@dotat.at> wrote:
>>Mohitz <coolmohitz@gmail.com> wrote:
>>
>>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...
>
>You can do this with Parsing Expression Grammars.
>http://pdos.csail.mit.edu/~baford/packrat/
>
>start = attr*
>attr = attr1 / attr2 / attr3
>attr1 = "attribute1" COLON value SEMICOLON !(attr* attr1 attr*)
>attr2 = "attribute2" COLON value SEMICOLON !(attr* attr2 attr*)
>attr3 = "attribute3" COLON value SEMICOLON !(attr* attr3 attr*)


Parsing Expression Grammars are an interesting solution to the problem,
but I don't think this one quite succeeds. In the term


!(attr* attr1 attr*)


it is my understanding is that the "*" operator is "greedy" and
will always consume the entire remainder of the string,
assuming all attributes are syntactically correct. Then
the concatenation with attr1 will always fail (and hence the
negative syntactic predicate will always succeed.) Even if it works
it has the inefficiency that all parts of all of the remaining attributes
have to be parsed out in their entirety and then discarded.
I would like to suggest an alternative. Using ABNF, which
differs only slightly in this example in its repetitions and ranges, and
adding line enders for readability of the input string:


start = *attr
attr = attr1 / attr2 / attr3
attr1 = name1 ":" value ";" CRLF !suffix1
attr2 = name2 ":" value ";" CRLF !suffix2
attr3 = name3 ":" value ";" CRLF !suffix3
name1 = "attribute1"
name2 = "attribute2"
name3 = "attribute3"
suffix1 = *(!name1 any) name1
suffix2 = *(!name2 any) name2
suffix3 = *(!name3 any) name3
any = %d10-127
value = alpha *alphanum
alpha = %d65-90 / %d97-122
alphanum = alpha / %d48-57
CRLF = %d13.10


This one works (I've tried it) and the remaining string is simply skipped
over, instead of actually parsing out each remaining attribute.


This interesting problem and its solution will appear
(with a citation to this thread) as a sample application in the upcoming
release of APG - an ABNF Parser Generator, version 5.0.


Lowell Thomas
www.coasttocoastresearch.com


Post a followup to this message

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