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

SPARQL grammar 2004-10-12 lex/yacc conflicts feedback

From: Dave Beckett <dave.beckett@bristol.ac.uk>
Date: Mon, 25 Oct 2004 16:17:20 +0100
To: public-rdf-dawg@w3.org
Message-Id: <20041025161720.01d1614e@hoth.ilrt.bris.ac.uk>

In going through the WD grammar
  http://www.w3.org/TR/2004/WD-rdf-sparql-query-20041012/#grammar
I was implementing with lex and yacc, based on earlier things derived
from BRQL, derived from RDQL.

I found the following shift/reduce conflicts:

1) 1 shift/reduce conflict at '.' in the grammar:

   PatternElement: TriplePatternList .
   TriplePatternList: TriplePatternList . TriplePattern

i.e.:

( (
    ^here

which can be nesting
  ( ( ...
  PatternElement
OR
  ( ( s p o)
  TriplePattern

This seems to be known and you need to do at least 2-token lookahead
or possibly arbitrary length, since you can have many nested ((()))s

That means extra work in the lexer since lookahead isn't available by
default in the standard lex/flex + yacc/bison/byacc tools that I
have.  This parallels RDF/XML which needed 2 token lookahead near
property elements.  I'd like this fixed.

Possible solutions could be:
   Changing the block syntax to be {}s
   Removing nested optionals and thus the need for blocks


2) (as in RDQL), 2 shift/reduce conflicts at '.' in the grammar:

    UnaryExpression: UnaryExpressionNotPlusMinus . PLUS UnaryExpression
                   | UnaryExpressionNotPlusMinus . MINUS UnaryExpression
                   | UnaryExpressionNotPlusMinus .

This one isn't serious, it's just the usual thing with expression
grammars and unary operators.  I think!  Could still be my error.

Dave
Received on Monday, 25 October 2004 15:20:40 GMT

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