Re: my emails on identifying the first operand of OPTIONAL

Fred Zemke wrote:
> I first started puzzling over patterns of the form
> { P1 } UNION { P2 } OPTIONAL { P3 }.
> This seemingly has two binary operators in it, and the BNF
> does not indicate any obvious precedence relationship between them.

One comment specificallly on

{ P1 } UNION { P2 } OPTIONAL { P3 }

UNION takes a group on each side (very similar to a discussion in the telecon 
about forcing {})

So:

[ { P1 } UNION { P2 } ] OPTIONAL { P3 } }

is the only parsing because

{ { P1 } UNION  [ { P2 }  OPTIONAL { P3 } ] }

is illegal (wrong RHS to the UNION).

With a left-to-right parser this is natural (the grammar is claimed to be 
LL(1)).  For a right-to-left parser, all the tokens would have to change anyway.

However, if we make OPTIONAL == Left Join, and a group is a left-associative 
list of Joins and Left Joins then

("join" and "Left Join" will be SPARQL variants that handle unbounds 
appropriately as soft nulls).

I'll try to draft an outline for this soon as it may provide the most direct 
route to LC/CR/REC.

	Andy

> 
> I think my very first communication on this was
> http://lists.w3.org/Archives/Public/public-rdf-dawg/2006AprJun/0170.html
> in the attachment on page 15.  You will see that I arrived at the
> conclusion from the grammar that the first operand of OPTIONAL
> is always a FilteredBasicGraphPattern, because that is the BNF
> nonterminal that is necessarily recognized by a parser immediately
> before OPTIONAL.  See the tree that I drew at the top of page 15.
> If the first operand is necessarily a FilteredBasicGraphPattern, then
> the example above is actually to be processed as
> { {P1} UNION {P2}} . { OPTIONAL {P3} }
> which means that there is an implicit empty pattern before OPTIONAL.
> 
> Andy Seaborne sent me a personal email about this conclusion,
> pointing out that it was completely at odds with an existing prototype.
> So I revised my analysis to
> http://lists.w3.org/Archives/Public/public-rdf-dawg/2006AprJun/0174.html
> 
> Andy reviewed that email in
> http://lists.w3.org/Archives/Public/public-rdf-dawg/2006AprJun/0175.html
> and said I had it right.
> 
> In that email, Andy proposed rearranging the grammar a little
> to make it easier to find the first argument of OPTIONAL. 
> I initially thought this would help.  However, see my attachment to
> http://lists.w3.org/Archives/Public/public-rdf-dawg/2006JulSep/0277.html
> section 3.3.1, list item 2 on page 3, where I spotted a bug with Andy's
> solution.  So for that paper I fell back to my earlier definition in
> http://lists.w3.org/Archives/Public/public-rdf-dawg/2006AprJun/0174.html
> This, together with a desire to make the scope of FILTER be the
> GroupGraphPattern, which I support,
> made the syntactic analysis of a GroupGraphPattern
> very messy indeed (see the remainder of section 3.3 in that paper).
> 
> So Andy worked on it some more and came up with the current grammar.
> I have not done the corresponding work to revise my algorithm to
> convert a SPARQL query to a tree representation.  I believe it should
> be simpler now, but not dramatically simpler.  I conjecture that the only
> thing that will make it dramatically simpler is to require braces around 
> the
> first operand of OPTIONAL.  I also think that that would provide the
> user with guidance about how to conceive of OPTIONAL when
> formulating queries.
> 
> Fred
> 
> 
> 
>

Received on Wednesday, 18 October 2006 11:03:30 UTC