Report on SPARQL Grammar implementation experience using ANTLR.


I wanted to report on our implementation experience for the SPARQL
grammar using the ANTLR parser generator based on the Working Draft
of the SPARQL query language[1][2].  This implementation does not
handle SPARQL semantics.  As such, the feedback is mainly relevant
to the utility of the current working draft of the SPARQL grammar
to implementors.

Overall, the SPARQL grammar was relatively easy to realize using
ANTLR.  The main points of confusion were the productions for QNAME
and QNAME_NS, especially as used in the PrefixDecl production - the
productions as given could not be made to work without significant
refactoring.  Also, the Perl5 regex production was not given in the

The implementation contains a test harness for the parser and another
for the lexer.  The parser accepts several of the DAWG Test Cases[3],
but it has not be vetted against all of the current test cases. (The
lexer test harness is currently non-functional owing to a problem
which has not yet been isolated either with the ANTLR lexer or with
how it is being invoked from the test harness.)

It would be useful from an implementation perspective if a bundle was
developed containing the test cases and sufficient metadata such that
a harness could easily be written or adapted to run the test cases
against a given implementation.

We plan to track subsequent working drafts and update this realization
of a SPARQL parser and lexer.  As of this writing, the parser produces
an AST using the default AST generation rules, and hence is not yet
suitable for query evaluation.  We are considering an RDF algebra as
a translation target that would make it possible to explore query
optimization and query evaluation.




Received on Wednesday, 9 March 2005 17:20:42 UTC