Re: Converting SPARQL syntax to trees

Fred Zemke wrote:

 > Attached please find my latest contribution to the formal
 > semantics of SPARQL, a paper on how to convert SPARQL
 > syntax to a tree representation.  The paper tackles some
 > non-trivial issues, the scope of FILTERs and identifiying
 > the first operand of OPTIONAL.  Enjoy.
 >
 > Fred

And the attached has:
> Andy Seaborne in
> http://lists.w3.org/Archives/Public/public-rdf-dawg/2006AprJun/0175.html
> proposed that the best way to identify the first operand of OPTIONAL is to
> rearrange the grammar, so that rule [19] becomes
> [19’] GroupGraphPattern ::=
> '{' GraphPattern
> ( ( OptionalGraphPattern ('.')? )+ GraphPattern )?
> '}'
> and rule [23] becomes
> [23’] GraphPatternNotTriples ::=
> GroupOrUnionGraphPattern | GraphGraphPattern
> I initially embraced this solution; however, I now believe that it is not equivalent to
> the current grammar. For example, it will not recognize this query:
> WHERE { ?x :y :z OPTIONAL { ?x :u :v }
>         ?x :y :z OPTIONAL { ?x :r :s } }

So the rules to full capture that should be

[19]  GroupGraphPattern ::= '{' GroupElement '}'

[19a] GroupElement      ::=
         GraphPattern ( OptionalGraphPattern '.'? GroupElement )?

that is, recurse on GroupElement not on GraphPattern.

I ran this on your example query and got the parse tree I expected:

   1 (query
   2   (prefix : <http://example/>)
   3   (select *)
   4   (group
   5     (optional
   6       (basicgraphpattern
   7         (triplepattern ?x :y :z))
   8       (group
   9         (basicgraphpattern
  10           (triplepattern ?x :u :v))))
  11     (optional
  12       (basicgraphpattern
  13         (triplepattern ?x :y :z))
  14       (group
  15         (basicgraphpattern
  16           (triplepattern ?x :r :s)))))
  17 )


I also ran the SPARQL syntax test suite with no problems encountered having 
added this example query to the syntax test suite.

It would be good to tidy up the grammar in various ways but this shows that 
the approach works.

	Andy

Received on Friday, 29 September 2006 13:25:53 UTC