Re: Grammar for optional elements

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

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