Fwd: SPARQL 1.0.3 and EBNF gems released

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

Fwd: SPARQL 1.0.3 and EBNF gems released

Gregg Kellogg-3
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 <[hidden email]>
> Subject: SPARQL 1.0.3 and EBNF gems released
> Date: March 5, 2013 5:10:04 PM PST
> To: "[hidden email]" <[hidden email]>
>
> 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


Reply | Threaded
Open this post in threaded view
|

RE: SPARQL 1.0.3 and EBNF gems released

Polleres, Axel
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 [hidden email] 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:[hidden email]] On Behalf Of Gregg Kellogg
> Sent: Mittwoch, 06. März 2013 02:17
> To: [hidden email]
> 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 <[hidden email]>
> > Subject: SPARQL 1.0.3 and EBNF gems released
> > Date: March 5, 2013 5:10:04 PM PST
> > To: "[hidden email]" <[hidden email]>
> >
> > 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
>


Reply | Threaded
Open this post in threaded view
|

Re: SPARQL 1.0.3 and EBNF gems released

Andy Seaborne-3
(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 [hidden email] 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:[hidden email]] On Behalf Of Gregg Kellogg
>> Sent: Mittwoch, 06. März 2013 02:17
>> To: [hidden email]
>> 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 <[hidden email]>
>>> Subject: SPARQL 1.0.3 and EBNF gems released
>>> Date: March 5, 2013 5:10:04 PM PST
>>> To: "[hidden email]" <[hidden email]>
>>>
>>> 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
>>
>
>

Reply | Threaded
Open this post in threaded view
|

Re: SPARQL 1.0.3 and EBNF gems released

Gregg Kellogg-4
In reply to this post by Polleres, Axel

On Mar 5, 2013, at 11:43 PM, "Polleres, Axel" <[hidden email]> 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 [hidden email] 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:[hidden email]] On Behalf Of Gregg Kellogg
>> Sent: Mittwoch, 06. März 2013 02:17
>> To: [hidden email]
>> 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 <[hidden email]>
>>> Subject: SPARQL 1.0.3 and EBNF gems released
>>> Date: March 5, 2013 5:10:04 PM PST
>>> To: "[hidden email]" <[hidden email]>
>>>
>>> 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
>>
>