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

Re: SPARQL 1.0.3 and EBNF gems released

From: Gregg Kellogg <gregg@greggkellogg.com>
Date: Wed, 6 Mar 2013 12:53:33 -0800
Cc: "gregg@greggkellogg.net" <gregg@greggkellogg.net>, "public-rdf-dawg-comments@w3.org" <public-rdf-dawg-comments@w3.org>, "public-sparql-dev@w3.org" <public-sparql-dev@w3.org>
Message-Id: <337B317B-45A4-499E-8F84-9B73FBF131BC@greggkellogg.com>
To: "Polleres, Axel" <axel.polleres@siemens.com>

On Mar 5, 2013, at 11:43 PM, "Polleres, Axel" <axel.polleres@siemens.com> 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.

Yes, but it may be that I have an overly strict understanding of how the FIRST set for SolutionModifier is created in this particular case. I raised it only as a point of interest, not to claim that the grammar is incorrect, just that from my understanding, it may fall outside of the strict definition of LL(1) table generation rules.

> The "fix" you propose for your implementation seems reasonable and preserve the intended meaning.

Andy points out that this generates a conflict, which is probablly true, but I think it is only of a theoretical nature.

> 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.

Fair enough. From my understanding, it's not strictly required that W3C EBNF grammars be LL(1), but it is probably a best practice. The fact that (also from my perspective) it comes as far as it does, and the remaining issue (in my specific case) is debatable, makes this a non-issue.

Other developers may benefit from this analysis, but I suspect that most rely on more sophisticated tool chains, such as JavaCC or YACC, and that this issue may not be of consequence to them.

> While this is a personal reply rather than an official group reply,
> please let us know whether this addresses you concern.

Thanks, the dev list probably would have been better, as it's not a formal concern about the spec, but really more of an implementation consideration. I don't think the WG need take any further action.

Gregg

> 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 20:54:03 GMT

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