W3C home > Mailing lists > Public > public-rdf-dawg@w3.org > October to December 2006

Re: Grammar changes

From: Seaborne, Andy <andy.seaborne@hp.com>
Date: Sun, 15 Oct 2006 17:38:53 +0100
Message-ID: <4532641D.50603@hp.com>
To: Lee Feigenbaum <feigenbl@us.ibm.com>
Cc: RDF Data Access Working Group <public-rdf-dawg@w3.org>

Hi Lee,

Lee Feigenbaum wrote:
> 
> Hi Andy,
> 
> I'm working through these grammar changes -- probably won't get to most 
> of them until next week, but a comment:
> 
>  > First stage of grammar changes: rq24 has been updated but I haven't
>  > redeployed
>  > the new grammar in yacker or the sparql.org validator yet.
>  >
>  >    Andy
>  >
>  > 2/ Optional
>  >
>  > Optional moved to be clearer as to what it binds to for the left hand 
> side.
>  >
>  > http://lists.w3.org/Archives/Public/public-rdf-dawg/2006JulSep/0278
>  >
>  > Effect: Does not invalidate any CR1 legal query.
> 
> I'm not sure the new rules are that much clearer than the old ones. (OK, 
> they're probably somewhat clearer, but still not *clear*.) We now have:
> 
> [20]            GroupGraphPattern            ::=            '{' 
> GroupElement '}'
> [21]           GroupElement           ::=           GraphPattern ( 
> OptionalGraphPattern '.'? GroupElement )?
> [22]           GraphPattern           ::=           BasicGraphPattern? ( 
> GraphPatternNotTriples '.'? GraphPattern )?
> 
> So we can clearly read GroupElement such that the first argument of the 
> OptionalGraphPattern is the GraphPattern that comes right before it. The 
> problem is that the grammar token GraphPattern does not unambiguously 
> represent a single specific pattern. With all the question marks in 
> GraphPattern and the recursion, the GraphPattern token often represents 
> a whole subtree of nodes in a parse tree. The intended semantics are (I 
> guess?) that the first argument to OPTIONAL is the last BGP, 
> GraphGraphPattern, GroupGraphPattern, or OptionalGraphPattern that 
> precedes the OPTIIONAL, but that's not clear to me from this grammar. 
> (Also, the GraphPattern token can consume nothing more than a constraint 
> (FILTER clause), which is also unclear as to the semantics when a FILTER 
> immediately precedes the OPTIONAL.)
> 
> All this is to say that I think we either need prose explaining how to 
> determine the first argument to OPTIONAL, or else we need to take 
> another stab at the grammar here.
> 
> (I've updated my implementation to use this new grammar, but, for me at 
> least, it didn't change the already somewhat convoluted logic of 
> determining the first argument to OPTIONAL. The fact that this logic is 
> convoluted may be entirely my fault. :-) )
> 
> Lee

Yes - this still needs work.  The only changes I made were ones that had been 
discussed previously; this isn't a wholesale reorganisation of the grammar.

[22] comes about from BGPs - the grammar has to arrange things so that BGPs 
can't be adjacent to each other because of trailing DOTs.  A BGP need not end 
in a DOT so if they can be adjacent then

    { :s1 :p1 :o1 :s2 :p2 :o2 }

is legal (note about N3 and Turtle -you can drop all the DOTs unambiguously! 
It has been claimed you can drop one of ".", ";" or "," and still get an 
unambiguous grammar (for machines - for people, it's cryptic :).  The grammar 
has both low-level surface syntax matters and also high-level structural 
matters; this BGP handling is really low-level stuff and not to related to the 
  high-level structure to be extracted.

(If the grammar were locally lookahead 2 (for LL) here it would also be more 
cleaner but LALR(1) then needs to control the shift/reduce conflict.)

If we define FILTERs to have group scope we have another issue.  In this case, 
are not defined by the syntax exclusively so they get in the way of a syntax 
interpretation - they do end up getting in the way with the revised grammar.


Some alternatives : maybe it is better way to define optional is along the 
lines of:

1/ separate out low level from high level issues of the grammar (c.f. a 
language for the algebra) mixing of low-level and high-level concerns.  At a 
slightly higher level of the abstract syntax tree would enable a focus on the 
important structural form.  That makes it the "last" graph pattern processed 
(not filter) seen before the optional (bottom of a recursive GraphPattern).


2/ For optionals, it's everything to the left of the optional in the group. 
That handles the filter case.

A.OPT(B,C) is the same as OPT(A.B, C) because optional expanded out is "B.C 
otherwise B" so we get A.B.C otherwise A.B

This is half-way between the current tight binding binary OPTIONAL and the 
more unary style OPTIONAL from a long time ago where an OPTIONAL contributes 
to the group.

My first reaction (and I'd need work through some more examples to get a more 
solid view) to (2) is that it like thinking of OPTIONAL as in:

Q1: WHERE { ?X :n :p . ?Y :n :g OPTIONAL { ?X :c ?Z } }
==>
Q1: WHERE { { ?X :n :p . ?Y :n :g } OPTIONAL { ?X :c ?Z } }

from Fred's message
http://lists.w3.org/Archives/Public/public-rdf-dawg/2006OctDec/0064.html


Thoughts?

> 
> (I'll have more comments on the rest of the grammar changes next week, 
> I'd imagine. Most of it looks great and non-controversial to me.)
> 

I look forward to them

	Andy
Received on Sunday, 15 October 2006 16:39:07 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 16:15:27 GMT