W3C home > Mailing lists > Public > public-rdf-dawg-comments@w3.org > March 2013

Re: SPARQL 1.0.3 and EBNF gems released

From: Andy Seaborne <andy.seaborne@epimorphics.com>
Date: Wed, 06 Mar 2013 11:03:19 +0000
Message-ID: <51372277.1070101@epimorphics.com>
To: "public-rdf-dawg-comments@w3.org >> public-rdf-dawg-comments" <public-rdf-dawg-comments@w3.org>
(this is not a formal reply)

Gregg,

I think this is an issue with the toolset.  Producing the HTML for the 
grammar is done using javacc which generates LL(1) grammars so every 
time the grammar is updated, the LL(1) condition is checked.

Making SolutionModifier optional actually creates an ambiguity because 
it is then unclear whether to enter the SolutionModifier rule when there 
are no modifiers because it matches the empty string in two ways.

There are two possible parse trees for the empty string at this point, 
with and without a SolutionModifier node in the abstract syntax tree.

(extracts reformatted for email):

SPARQL 1.1:

[7] SelectQuery ::=
      SelectClause DatasetClause* WhereClause SolutionModifier

[18] SolutionModifier ::=
     GroupClause? HavingClause? OrderClause? LimitOffsetClauses?

This has not changed fundamentally since SPARQL 1.0, which also had this 
form, just less modifiers:

[5] SelectQuery ::=
  	'SELECT' ( 'DISTINCT' | 'REDUCED' )? ( Var+ | '*' )
         DatasetClause*
         WhereClause
         SolutionModifier

[14] SolutionModifier ::=
    	OrderClause? LimitOffsetClauses?



The snapshot of the SPARQL 1.1 grammar state at the point of publication 
is [1].

	Andy


[1] 
https://svn.apache.org/repos/asf/jena/trunk/jena-arq/Grammar/Final/sparql_11-final.jj

On 06/03/13 07:43, Polleres, Axel wrote:
> Hi Gregg,
>
> To clarify: if I understand your comment correctly, you confirm that the rules in the spec are
> correct, but they don't work out-of-the box with the LL parser you are using.
> The "fix" you propose for your implementation seems reasonable and preserve the intended meaning.
> As far as I understand it, this is an implementation issue (in the sense that the spec needs
> to guarantee the correct and unambiguous meaning, rather than providing a grammar that works with
> specific parsers out-of-the box, such that your comment fits in my humble opinion better
> to the public-sparql-dev@w3.org list (in the sense that it might be useful information for other
> implementers), so I took the freedom to cc: that list.
>
> While this is a personal reply rather than an official group reply,
> please let us know whether this addresses you concern.
>
> Best regards,
> Axel
>
>
>
>
>> -----Original Message-----
>> From: Gregg Kellogg [mailto:gregg@greggkellogg.com] On Behalf Of Gregg Kellogg
>> Sent: Mittwoch, 06. März 2013 02:17
>> To: public-rdf-dawg-comments@w3.org
>> Subject: Fwd: SPARQL 1.0.3 and EBNF gems released
>>
>> This should be of general interest to the SPARQL community. Note, that to
>> parse the grammar as LL(1), I needed to re-write a couple of rules, e.g.:
>>
>>      [7]       SelectQuery       ::=   SelectClause DatasetClause*
>> WhereClause SolutionModifier?
>>
>> In the original rule SolutionModifier is not optional, but all of it's
>> productions are optional. Unfortunately, the standard LL(1) rules don't
>> propagate this optionally to SelectQuery. Making that rule optional solved my
>> problem, at least.
>>
>> Gregg
>>
>>
>> Begin forwarded message:
>>
>>> From: Gregg Kellogg <gregg@greggkellogg.net>
>>> Subject: SPARQL 1.0.3 and EBNF gems released
>>> Date: March 5, 2013 5:10:04 PM PST
>>> To: "public-rdf-ruby@w3.org" <public-rdf-ruby@w3.org>
>>>
>>> I've updated the SPARQL gem [1], which works with RDF.rb 1.0 and greater in
>> pure Ruby (>= 1.8.7). This version has no new functionality, but is based on
>> the SPARQL 1.1 grammar, rather than the SPARQL 1.0 grammar. In order to get
>> the SPARQL 1.1 grammar to compile, I needed to re-create my LL(1) toolchain,
>> which used some custom components along with some old SWAP rules. The new
>> version uses a new EBNF gem [2], which parses W3C EBNF and generates LL(1)
>> parser tables (first/follow and branch). It also includes a generic LL(1)
>> parser core, which is used both by Turtle and TriG parser gems as well as
>> SPARQL.
>>>
>>> The EBNF gem will probably be of more interest to spec writers in the
>> future, as it can validate EBNF grammars, turn them into BNF grammars and
>> create generally usable parser tables. It will also be useful as a web service
>> for generating grammar documentation, providing formatted HTML output of
>> compliant grammars.
>>>
>>> Having the SPARQL gem use the 1.1 grammar now enables the generation of more
>> algebra operators to support more the more advanced features of SPARQL 1.1
>> query and update.
>>>
>>> [1] https://rubygems.org/gems/sparql
>>> [2] https://rubygems.org/gems/ebnf
>>
>
>
Received on Wednesday, 6 March 2013 11:03:53 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Wednesday, 6 March 2013 11:03:53 GMT