SPARQL grammar... in BNF? N3?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

SPARQL grammar... in BNF? N3?

Dan Connolly

Yosi, Tim, Eric,

The SPARQL parser in cwm... it seems to be built from EricP's
BNF...


|    if web:
|        File = urllib.urlopen('http://www.w3.org/2005/01/yacker/uploads/sparqlTest/bnf')
 -- http://www.w3.org/2000/10/swap/sparql/sparql-grammar.py

In the DAWG, the editors added a .jj version of the grammar
and are considering what other formats to publish.
  http://www.w3.org/2001/sw/DataAccess/rq23/parsers/sparql.jj
  <- http://www.w3.org/2001/sw/DataAccess/rq23/parsers/
  <- http://www.w3.org/2001/sw/DataAccess/rq23/#sparqlGrammar

Is BNF the one we want/need?

EricP, have you generated a turtle/n3 version of the SPARQL grammar?

Yosi, what's the status of N3 parsers based on n3.n3? Do they
work yet? What about using that approach for the SPARQL parser?

--
Dan Connolly, W3C http://www.w3.org/People/Connolly/
D3C2 887B 0F92 6005 C541  0875 0F91 96DE 6E52 C29E


Reply | Threaded
Open this post in threaded view
|

Re: SPARQL grammar... in BNF? N3?

Seaborne, Andy

A few details:

Dan Connolly wrote:
> Yosi, Tim, Eric,
>
> The SPARQL parser in cwm... it seems to be built from EricP's
> BNF...
>
>
> |    if web:
> |        File = urllib.urlopen('http://www.w3.org/2005/01/yacker/uploads/sparqlTest/bnf')

Now:

http://www.w3.org/2005/01/yacker/uploads/SPARQL/bnf

>  -- http://www.w3.org/2000/10/swap/sparql/sparql-grammar.py
>
> In the DAWG, the editors added a .jj version of the grammar

I hope we will add all the parsers - adding the .jj is just a start.  We just
need a place outside yacker (where they can be mutated) and put somewhere that
can be linked to for publication.

> and are considering what other formats to publish.
>   http://www.w3.org/2001/sw/DataAccess/rq23/parsers/sparql.jj
>   <- http://www.w3.org/2001/sw/DataAccess/rq23/parsers/
>   <- http://www.w3.org/2001/sw/DataAccess/rq23/#sparqlGrammar
>
> Is BNF the one we want/need?
>
> EricP, have you generated a turtle/n3 version of the SPARQL grammar?

The grammars in yacker (grammar name = SPARQL) are up to date, including the
BNF (which is the same as rq23 - because it is extracted from rq23 and then
1/ All \ are escaped.
2/ @terminals added).

The Python one is currently broken ("RuntimeError: maximum recursion limit
exceeded").  I don't know enough about yapps to know how to avoid it - it used
to work!

        Andy

>
> Yosi, what's the status of N3 parsers based on n3.n3? Do they
> work yet? What about using that approach for the SPARQL parser?
>


Reply | Threaded
Open this post in threaded view
|

Re: SPARQL grammar... in BNF? N3?

Yosi Scharf
In reply to this post by Dan Connolly

Dan Connolly wrote:

>Yosi, Tim, Eric,
>
>The SPARQL parser in cwm... it seems to be built from EricP's
>BNF...
>
>
>|    if web:
>|        File = urllib.urlopen('http://www.w3.org/2005/01/yacker/uploads/sparqlTest/bnf')
> -- http://www.w3.org/2000/10/swap/sparql/sparql-grammar.py
>
>  
>
Wow. That line, and indeed that entire file, appears to be an incredible
red herring. sparql-grammar.py is not used anywhere, and never worked.
It was an early attempt of mine, before I switched to yacker.

I used yacker on a file I had modified to be LL(0). I think this was
http://www.w3.org/2005/01/yacker/uploads/yosiJune28a/bnf . Running that
through yacker (almost) got me
http://www.w3.org/2000/10/swap/grammar/sparql . I manually rewrote some
of the worst regexps in it for speed, however, the last of those
modifications being on July 28. Therefore, any changes to the SPARQL
grammar after that time have not been tracked. Cwm's sparql support uses
this. The was this works is shown in
http://www.w3.org/2000/10/swap/sparql/Makefile


Yosi

>In the DAWG, the editors added a .jj version of the grammar
>and are considering what other formats to publish.
>  http://www.w3.org/2001/sw/DataAccess/rq23/parsers/sparql.jj
>  <- http://www.w3.org/2001/sw/DataAccess/rq23/parsers/
>  <- http://www.w3.org/2001/sw/DataAccess/rq23/#sparqlGrammar
>
>Is BNF the one we want/need?
>
>EricP, have you generated a turtle/n3 version of the SPARQL grammar?
>
>Yosi, what's the status of N3 parsers based on n3.n3? Do they
>work yet? What about using that approach for the SPARQL parser?
>
>  
>


Reply | Threaded
Open this post in threaded view
|

Re: SPARQL grammar... in BNF? N3?

Tim Berners-Lee
In reply to this post by Dan Connolly


On Feb 8, 2006, at 10:40, Dan Connolly wrote:

> Yosi, Tim, Eric,
>
> The SPARQL parser in cwm... it seems to be built from EricP's
> BNF...
>
>
> |    if web:
> |        File = urllib.urlopen('http://www.w3.org/2005/01/yacker/ 
> uploads/sparqlTest/bnf')
>  -- http://www.w3.org/2000/10/swap/sparql/sparql-grammar.py
>
> In the DAWG, the editors added a .jj version of the grammar
> and are considering what other formats to publish.
>   http://www.w3.org/2001/sw/DataAccess/rq23/parsers/sparql.jj
>   <- http://www.w3.org/2001/sw/DataAccess/rq23/parsers/
>   <- http://www.w3.org/2001/sw/DataAccess/rq23/#sparqlGrammar
>
> Is BNF the one we want/need?
>

Yes, please.  This has been a long-standing informal request.

> EricP, have you generated a turtle/n3 version of the SPARQL grammar?
>
> Yosi, what's the status of N3 parsers based on n3.n3?


AFAIK, there are several. Sean Palmer's n3p is built from n3.n3.
I think Yosi's sparql parser is dervied from n3p.
There is my predictiveParser.py which validates the test suite  
against n3.n3
but does not have the code to generate RDF triples.

> Do they
> work yet?

basically.
There is a test harness Yosi built
which seeems to have been used on 8 parsers. See the results table
http://www.w3.org/WWW/2000/10/swap/test/n3/test_results.html
The harness seems ready to be used to make a more refined answer to  
that question.

> What about using that approach for the SPARQL parser?
>

That is what Yosi basically did.
As I understood it, there was some human intervention in converting
the BNF.  I seem to remember that it was passed back to the DAWG
as a comment, and may have been fixed.

There is sparql parsing in the cwm regression test I think.

> --
> Dan Connolly, W3C http://www.w3.org/People/Connolly/
> D3C2 887B 0F92 6005 C541  0875 0F91 96DE 6E52 C29E


Reply | Threaded
Open this post in threaded view
|

Re: SPARQL grammar... in BNF? N3?

Dan Connolly

On Wed, 2006-02-08 at 13:12 -0500, Tim Berners-Lee wrote:

> On Feb 8, 2006, at 10:40, Dan Connolly wrote:
>
> > Yosi, Tim, Eric,
> >
> > The SPARQL parser in cwm... it seems to be built from EricP's
> > BNF...
> >
> >
> > |    if web:
> > |        File = urllib.urlopen('http://www.w3.org/2005/01/yacker/ 
> > uploads/sparqlTest/bnf')
> >  -- http://www.w3.org/2000/10/swap/sparql/sparql-grammar.py
> >
> > In the DAWG, the editors added a .jj version of the grammar
> > and are considering what other formats to publish.
> >   http://www.w3.org/2001/sw/DataAccess/rq23/parsers/sparql.jj
> >   <- http://www.w3.org/2001/sw/DataAccess/rq23/parsers/
> >   <- http://www.w3.org/2001/sw/DataAccess/rq23/#sparqlGrammar
> >
> > Is BNF the one we want/need?
> >
>
> Yes, please.  This has been a long-standing informal request.

I'm surprised.

To be clear: you do _not_ want n3/turtle?

By BNF I mean this format:

[1]     Query    ::=     Prolog
( SelectQuery | ConstructQuery | DescribeQuery | AskQuery )
[2]   Prolog  ::=   BaseDecl? PrefixDecl*
[3]   BaseDecl  ::=   'BASE' Q_IRI_REF
[4]   PrefixDecl  ::=   'PREFIX' QNAME_NS Q_IRI_REF
  -- http://www.w3.org/2005/01/yacker/uploads/SPARQL/bnf

I thought you wanted n3/turtle, i.e. this format:

verb cfg:mustBeOneSequence (
                ( expression )
                ( "@has" expression )
                ( "@is" expression "@of" )
                ( "@a" )
                ( "=" )
                ( "=>" )
                ( "<=" )
        ).
  -- http://www.w3.org/2000/10/swap/grammar/n3.n3


(does turtle include @keywords and omitted colons these days?)

> > EricP, have you generated a turtle/n3 version of the SPARQL grammar?
> >
> > Yosi, what's the status of N3 parsers based on n3.n3?
>
>
> AFAIK, there are several. Sean Palmer's n3p is built from n3.n3.
> I think Yosi's sparql parser is dervied from n3p.
> There is my predictiveParser.py which validates the test suite  
> against n3.n3
> but does not have the code to generate RDF triples.
>
> > Do they
> > work yet?
>
> basically.
> There is a test harness Yosi built
> which seeems to have been used on 8 parsers. See the results table
> http://www.w3.org/WWW/2000/10/swap/test/n3/test_results.html
> The harness seems ready to be used to make a more refined answer to  
> that question.
>
> > What about using that approach for the SPARQL parser?
> >
>
> That is what Yosi basically did.
> As I understood it, there was some human intervention in converting
> the BNF.  I seem to remember that it was passed back to the DAWG
> as a comment, and may have been fixed.
>
> There is sparql parsing in the cwm regression test I think.

--
Dan Connolly, W3C http://www.w3.org/People/Connolly/
D3C2 887B 0F92 6005 C541  0875 0F91 96DE 6E52 C29E


Reply | Threaded
Open this post in threaded view
|

Re: SPARQL grammar... in BNF? N3?

Dave Beckett-2

Dan Connolly wrote:
> (does turtle include @keywords and omitted colons these days?)

No and no.

Dave

Reply | Threaded
Open this post in threaded view
|

Re: SPARQL grammar... in BNF? N3?

Tim Berners-Lee
In reply to this post by Dan Connolly


On Feb 8, 2006, at 13:26, Dan Connolly wrote:

> On Wed, 2006-02-08 at 13:12 -0500, Tim Berners-Lee wrote:
>> On Feb 8, 2006, at 10:40, Dan Connolly wrote:
>>
>>> Yosi, Tim, Eric,
>>>
>>> The SPARQL parser in cwm... it seems to be built from EricP's
>>> BNF...
>>>
>>>
>>> |    if web:
>>> |        File = urllib.urlopen('http://www.w3.org/2005/01/yacker/
>>> uploads/sparqlTest/bnf')
>>>  -- http://www.w3.org/2000/10/swap/sparql/sparql-grammar.py
>>>
>>> In the DAWG, the editors added a .jj version of the grammar
>>> and are considering what other formats to publish.
>>>   http://www.w3.org/2001/sw/DataAccess/rq23/parsers/sparql.jj
>>>   <- http://www.w3.org/2001/sw/DataAccess/rq23/parsers/
>>>   <- http://www.w3.org/2001/sw/DataAccess/rq23/#sparqlGrammar
>>>
>>> Is BNF the one we want/need?
>>>
>>
>> Yes, please.  This has been a long-standing informal request.
>
> I'm surprised.
>
> To be clear: you do _not_ want n3/turtle?

On the contrary, yes, I would like it in RDF, using the same
context-free grammar ontology please, but any syntax out of RDF/XML or
any subset of N3.


Reply | Threaded
Open this post in threaded view
|

Re: SPARQL grammar... in BNF? N3?

Dan Connolly

On Thu, 2006-02-09 at 16:21 -0500, Tim Berners-Lee wrote:
[...]
> >>>   <- http://www.w3.org/2001/sw/DataAccess/rq23/parsers/
> ...I would like it in RDF, using the same
> context-free grammar ontology please, but any syntax out of RDF/XML or
> any subset of N3.

OK. I couldn't help working on that for much of today:
  http://www.w3.org/2001/sw/DataAccess/rq23/parsers/sparql.rdf
  http://www.w3.org/2001/sw/DataAccess/rq23/parsers/sparql.ttl

The .ttl looks like:

[[
@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>.
@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#>.
@prefix : <http://www.w3.org/2001/sw/DataAccess/rq23/parsers/sparql#>.
@prefix g:
<http://www.w3.org/2001/sw/DataAccess/rq23/parsers/grammar@@#>.
#@@ case insensitivity of 'BASE' and the like is not expressed.

:Query rdfs:label "Query"; rdf:value "1";
 rdfs:comment "[1]      Query     ::=           Prolog( SelectQuery |
ConstructQuery | DescribeQuery | AskQuery )";
 a g:NonTerminal;
  g:seq (
    :Prolog
    [ g:alt (
      :SelectQuery
      :ConstructQuery
      :DescribeQuery
      :AskQuery
     ) ]
   )
.

:Prolog rdfs:label "Prolog"; rdf:value "2";
 rdfs:comment "[2]      Prolog    ::=           BaseDecl? PrefixDecl*";
 a g:NonTerminal;
  g:seq (
    [ g:opt
      :BaseDecl
     ]
    [ g:star
      :PrefixDecl
     ]
   )
.

]]


I haven't done a conversion back to BNF from RDF; it should
be a simple --strings thingy or XSLT transformation. I don't
think I can argue to throw away the BNF and use the RDF as the
source; it's pretty unwieldy and verbose, even in turtle format.

(DAWG business:
There's the question of the full URI of terms like :Query
and :Prolog themselves. If this thing is to become part
of the SPARQL Recommendation, I guess their URIs will have
to be approved by the WG. I suppose a namespace outside /DataAccess/
and outside /TR/... somewhere in /2006/02/... like the SPARQL
protocol namespace, is best. )

I made up my own EBNF ontology because I couldn't figure out
the swap/grammar one; I suspect the terms match 1-1. I like
mine better. :) Let's switch, shall we? Perhaps: first one
to make a decent write-up wins?

I saw somebody... Bjoren H. maybe... ask that the BNF notation
section of the XML spec get published independently. Maybe
this would be the way to do it. I wrote a converter:

  http://www.w3.org/2001/sw/DataAccess/rq23/bnf2turtle.py

Anyway... so this .rdf version has not been checked against
the SPARQL test suite.

Yosi, do you think you could update the SPARQL parser you
put in cwm to be mechanically generated from sparql{.ttl,.rdf}
and try it against some of the tests? It would involve
compiling the :Terminal nodes to regexs, probably in python.

Jos, it might be fun to have euler derive proofs that strings
are in the language generated by this grammar.


I grabbed
  http://www.w3.org/2005/01/yacker/uploads/SPARQL/bnf
and checked that in; as I understand it, that's the "truth"
that EricP and/or AndyS and/or Yosi work from.


I check that the .ttl doesn't have anything that goes beyond
RDF expressiveness like this:

connolly@dirk:~/w3ccvs/WWW/2001/sw/DataAccess/rq23$ make check-gram
python bnf2turtle.py parsers/sparql.bnf >parsers/sparql.ttl
python ../../../../2000/10/swap/cwm.py parsers/sparql.ttl --rdf
>parsers/sparql.rdf
python ../../../../2000/10/swap/cwm.py parsers/sparql.ttl --n3 >,g1.n3
python ../../../../2000/10/swap/cwm.py parsers/sparql.rdf --n3 >,g2.n3
diff -u ,g1.n3 ,g2.n3
[[some diffs in comments about base URI;
is there a way to suppres those comments in N3 output?]]



--
Dan Connolly, W3C http://www.w3.org/People/Connolly/
D3C2 887B 0F92 6005 C541  0875 0F91 96DE 6E52 C29E


Reply | Threaded
Open this post in threaded view
|

Re: SPARQL grammar... in BNF? N3?

Dave Beckett-2

Dan Connolly wrote:
> OK. I couldn't help working on that for much of today:

> ...

> I wrote a converter:
>   http://www.w3.org/2001/sw/DataAccess/rq23/bnf2turtle.py

and it didn't take long to apply it to the Turtle EBNF, the result being:
  http://www.dajobe.org/2004/01/turtle/grammar.ttl

or as DanC put it:
  <DanC> turtle in turtle... it's turtles all the way down. ;-)

The EBNF in the document remains the definition of the language.

Dave