// ARQ/SPARQL 1.1 Grammar - native syntax for the query engine
#if 0
// (Run through cpp -P -C first)
#endif


#if !defined(ARQ) && !defined(SPARQL_11)
#error Please define one of ARQ and SPARQL_11
#endif

#if defined(ARQ) && defined(SPARQL_11)
#error Please define only one of ARQ and SPARQL_11
#endif

// UPDATE : SPARQL 1.1. Update
// ARQ_UPDATE : extensions to SPARQL 1.1 Update to cover SPARQL/Update (W3C Submission)

#ifdef SPARQL_11
#define PACKAGE     lang.sparql_11
#define CLASS       SPARQLParser11
#define PARSERBASE  SPARQLParser11Base
#define UPDATE
#endif

#ifdef ARQ
#define PACKAGE     lang.arq
#define CLASS       ARQParser
#define PARSERBASE  ARQParserBase
#define UPDATE
#define ARQ_UPDATE
#endif

// Author:  Andy Seaborne <andy.seaborne@epimorphics.com>
// (c) Copyright 2004, 2005, 2006, 2007, 2008, 2009 Hewlett-Packard Development Company, LP
// (c) Copyright 2010 Talis Systems Ltd.
// (c) Copyright 2010, 2011 Epimorphics Ltd.
// All rights reserved.
// See end of file for details.
//
// Constraint expression is derived from Java : 
// example java1.2-a.jj grammer in JavaCC distribution
// Much modifed over time.

options
{
   JAVA_UNICODE_ESCAPE   = true ;
   UNICODE_INPUT         = false ;

  STATIC                = false ;
//  DEBUG_PARSER          = true ;
//  DEBUG_TOKEN_MANAGER   = true ;
}

PARSER_BEGIN(CLASS)
/*
 * (c) Copyright 2004, 2005, 2006, 2007, 2008, 2009 Hewlett-Packard Development Company, LP
 * (c) Copyright 2010 Talis Systems Ltd
 * All rights reserved.
 */

package com.hp.hpl.jena.sparql.PACKAGE ;

import com.hp.hpl.jena.graph.* ;
import com.hp.hpl.jena.query.* ;
import com.hp.hpl.jena.sparql.core.Var ;
import com.hp.hpl.jena.sparql.syntax.* ;
import com.hp.hpl.jena.sparql.expr.* ;
import com.hp.hpl.jena.sparql.path.* ;
import com.hp.hpl.jena.sparql.expr.aggregate.* ;
#ifdef  UPDATE
import com.hp.hpl.jena.update.* ;
import com.hp.hpl.jena.sparql.modify.request.* ;
#endif

public class CLASS extends PARSERBASE
{
    boolean allowAggregatesInExpressions = false ;
}
PARSER_END(CLASS)

// // Common top for single entry point.
// void Top(): {}
// {
//     ( Query() | Update() )
//     <EOF>
// }

// Query only entry point
void QueryUnit(): { }
{
  { startQuery() ; }
  Query() <EOF>
  { finishQuery() ; }
}

void Query() : { }
{    
  Prologue()
  ( SelectQuery() | ConstructQuery() | DescribeQuery() | AskQuery() )
  BindingsClause()
}

#ifdef UPDATE
void UpdateUnit() : {}
{
  { startUpdateRequest() ; }
  Update()
  <EOF>
  { finishUpdateRequest() ; }
}
#endif


void Prologue() : {}
{
  ( BaseDecl() | PrefixDecl() )*
}

void BaseDecl() : { String iri ; }
{
  <BASE> iri = IRI_REF()
  { getPrologue().setBaseURI(iri) ; }
}

void PrefixDecl() : { Token t ; String iri ; }
{
    <PREFIX> t = <PNAME_NS> iri = IRI_REF()
      { String s = fixupPrefix(t.image, t.beginLine, t.beginColumn) ;
        getPrologue().setPrefix(s, iri) ; }
}

// ---- Query type clauses

void SelectQuery() : { }
{  
  SelectClause()
  ( DatasetClause() )*
  WhereClause()
  SolutionModifier()
}

void SubSelect() :{ }
{  
  SelectClause()
  WhereClause()
  SolutionModifier()
} 

void SelectClause() : {  Var v ; Expr expr ; Node n ; }
{
  <SELECT>
    { getQuery().setQuerySelectType() ; }
  ( <DISTINCT> { getQuery().setDistinct(true);} 
  | <REDUCED>  { getQuery().setReduced(true); }
  )? 

  { allowAggregatesInExpressions = true ; }
  (
    (
      v = Var()                     { getQuery().addResultVar(v) ; }
    | 
#if ARQ
      // Expressions without ()
      ( LOOKAHEAD(2)
        expr = Aggregate()          { getQuery().addResultVar((Var)null, expr) ; }
      | expr = BuiltInCall()        { getQuery().addResultVar((Var)null, expr) ; }
      | expr = FunctionCall()       { getQuery().addResultVar((Var)null, expr) ; }
      | n = RDFLiteral()            { getQuery().addResultVar((Var)null, NodeValue.makeNode(n)) ; }
      | n = NumericLiteral()        { getQuery().addResultVar((Var)null, NodeValue.makeNode(n)) ; }
      | n = BooleanLiteral()        { getQuery().addResultVar((Var)null, NodeValue.makeNode(n)) ; }
      )
      // @@ PROBLEMS: expr = FunctionCall()
      // <uri>(?x)
      // looks like a function call and also a "<uri> ( ?v )"
      //| expr = FunctionCall()  { getQuery().addResultVar((Var)null, expr) ; }
    |
#endif      
        // Expressions with ()
      (
        { v = null ; }
        <LPAREN>
        expr = Expression() 
#ifdef SPARQL_11
        <AS> v = Var()
#endif
#ifdef ARQ
        ( <AS> v = Var() ) ?
#endif
        <RPAREN>
        { getQuery().addResultVar(v, expr) ; }
      )
      { getQuery().setQueryResultStar(false) ; }
    )+
  |
    <STAR> { getQuery().setQueryResultStar(true) ; }
  )
  { allowAggregatesInExpressions = false ; }
}

void ConstructQuery() : { Template t ; 
                          TripleCollectorBGP acc = new TripleCollectorBGP() ; }
{
// #ifndef ARQ
//   <CONSTRUCT>
//      { getQuery().setQueryConstructType() ; }
//   t = ConstructTemplate() 
//     { getQuery().setConstructTemplate(t) ; }
//   ( DatasetClause() )*
//   WhereClause()
//   SolutionModifier()
// #else

 <CONSTRUCT>
   { getQuery().setQueryConstructType() ; }
 (
    // Full form.
    t = ConstructTemplate() 
      { getQuery().setConstructTemplate(t) ; }
    ( DatasetClause() )*
    WhereClause()
    SolutionModifier()
 |
    ( DatasetClause() )*
    <WHERE>
    <LBRACE>
    (TriplesTemplate(acc))?
    <RBRACE>
    SolutionModifier()
    { 
      t = new Template(acc.getBGP()) ;
      getQuery().setConstructTemplate(t) ;
      // Create a query in the same shape as the query created by writing out in full.
      ElementPathBlock epb = new ElementPathBlock(acc.getBGP()) ;
      ElementGroup elg = new ElementGroup() ;
      elg.addElement(epb) ;
      getQuery().setQueryPattern(elg) ;
    }
 )
//#endif
}

void DescribeQuery() : { Node n ; }
{
  <DESCRIBE>
    { getQuery().setQueryDescribeType() ; }
  (
    ( n = VarOrIRIref() { getQuery().addDescribeNode(n) ; } )+
    { getQuery().setQueryResultStar(false) ; }
  |
    <STAR>
    { getQuery().setQueryResultStar(true) ; }
  )
  ( DatasetClause() )*
  ( WhereClause() )?
  SolutionModifier()
}

void AskQuery() : {}
{
  <ASK> { getQuery().setQueryAskType() ; }
  ( DatasetClause() )*
  WhereClause()
}

// ----

void DatasetClause() : {}
{
  <FROM>
  ( DefaultGraphClause() | NamedGraphClause() )
}

void DefaultGraphClause() : { String iri ; }
{
  iri = SourceSelector() 
  {
    // This checks for duplicates
    getQuery().addGraphURI(iri) ;
  }
}

void NamedGraphClause() : { String iri ; }
{
  <NAMED>
  iri = SourceSelector()
  { 
    // This checks for duplicates
    getQuery().addNamedGraphURI(iri) ;
  }
}

String SourceSelector() : { String iri ; }
{
  iri = IRIref() { return iri ; }
}


void WhereClause() : { Element el ; }
{
   (<WHERE>)? el = GroupGraphPattern() { getQuery().setQueryPattern(el) ; }
}

void SolutionModifier() : { }
{
  ( GroupClause() )?
  ( HavingClause() )?
  ( OrderClause() )?
  ( LimitOffsetClauses() )? 
}

void GroupClause() : { }
{
  <GROUP> <BY> ( GroupCondition() )+
}

void GroupCondition() : { Var v = null ; Expr expr = null ; }
{
  ( expr = BuiltInCall()   { getQuery().addGroupBy((Var)null, expr) ; }
  | expr = FunctionCall()  { getQuery().addGroupBy((Var)null, expr) ; }
  |
    <LPAREN>
      expr = Expression() 
    ( <AS>  v = Var() )?
    <RPAREN>
    { getQuery().addGroupBy(v ,expr) ; }
  | v = Var()
    { getQuery().addGroupBy(v) ; }
  )
}

void HavingClause() : { }
{
    { allowAggregatesInExpressions = true ; }
    <HAVING> (HavingCondition())+
    { allowAggregatesInExpressions = false ; }
}

void HavingCondition() : { Expr c ; }
{
   c = Constraint()
   { getQuery().addHavingCondition(c) ; }
}

void OrderClause() : { }
{
  <ORDER> <BY> ( OrderCondition() )+
}

void OrderCondition() :
{ int direction = 0 ; Expr expr = null ; Node v = null ; }
{
  { direction = Query.ORDER_DEFAULT ; }
  (
    ( // These are for clarity in the HTML
      ( <ASC>  { direction = Query.ORDER_ASCENDING ; }
      | <DESC> { direction = Query.ORDER_DESCENDING ; } ) 
      expr = BrackettedExpression() 
    )
  |
    ( expr = Constraint()
    | v = Var() //{ expr = asExpr(v) ; } 
    ) 
  )
  { if ( v == null )
          getQuery().addOrderBy(expr, direction) ;
      else
          getQuery().addOrderBy(v, direction) ; }
}

void LimitOffsetClauses() : { }
{
  // SPARQL does not care about the order here.
  // SQL (where implemented) does (it's LIMIT then OFFSET generally)
  // But that is counter intuitive as it's applied the other way round
  (
    LimitClause() (OffsetClause())? 
  |
    OffsetClause() (LimitClause())? 
  )
}

void LimitClause() : { Token t ; }
{
  <LIMIT> t = <INTEGER>
    { getQuery().setLimit(integerValue(t.image)) ; }
}

void OffsetClause() : { Token t ; }
{
  <OFFSET> t = <INTEGER>
    { getQuery().setOffset(integerValue(t.image)) ; }
}

void BindingsClause() : { Var v ; Node n ; Token t ; }
{
  (
    // @@ Zero allowed?
    t = <BINDINGS> 
    { startBinding(t.beginLine, t.beginColumn) ; }
    ( v = Var() { emitBindingVariable(v, t.beginLine, t.beginColumn) ; }) *

    t = <LBRACE>
    (
      t = <LPAREN> 
        { startBindingValueRow(t.beginLine, t.beginColumn) ; }
      (n = BindingValue() { emitBindingValue(n, t.beginLine, t.beginColumn) ; }) *
      t = <RPAREN> 
        { finishBindingValueRow(t.beginLine, t.beginColumn) ; }
    |
      t = <NIL>
      { startBindingValueRow(t.beginLine, t.beginColumn) ; }
      { finishBindingValueRow(t.beginLine, t.beginColumn) ; }
    )*

    t = <RBRACE>
    { finishBinding(t.beginLine, t.beginColumn) ; }
  )?
}

Node BindingValue() : { Node n ; String iri ; }
{
  iri = IRIref()        { return createNode(iri) ; }
| n = RDFLiteral()      { return n ; }
| n = NumericLiteral()  { return n ; }
| n = BooleanLiteral()  { return n ; }
| <UNDEF>               { return null ; }
}

#ifdef UPDATE
// SPARQL Update + transitional extensions for SPARQL/Update (the W3C submission)
// Update only entry point

#ifdef ARQ_UPDATE
// Optional SEMICOLON
void Update() : { }
{
   Prologue()
   ( Update1() (<SEMICOLON>)*  Update() )?
}
#else
// Strict SPARQL 1.1 : mandatory separator, optional terminator.
void Update() : { }
{  
   Prologue()
   (Update1() ( <SEMICOLON> Update() )? )?
}
#endif

void Update1() : { Update up ; }
{
  { startUpdateOperation() ; }
  ( up = Load()
  | up = Clear()
  | up = Drop()
  | up = Add()
  | up = Move()
  | up = Copy()
  | up = Create()
  | up = InsertData()
  | up = DeleteData()
  | up = DeleteWhere()
  | up = Modify()
#ifdef ARQ_UPDATE
  | up = ModifyOld()
#endif
  )
  {
    emitUpdate(up) ;
    finishUpdateOperation() ;
  }

}

Update Load() : { String url ; Node dest = null ; boolean silent = false ; }
{
    // Should be +?
    //    <LOAD> ( IRIref() )+
    <LOAD>  (<SILENT> { silent = true ; })? url = IRIref()
#ifndef ARQ_UPDATE
    (<INTO> dest = GraphRef() )?
#else
    { String iri ; }
    (<INTO> (<GRAPH>)? iri = IRIref() { dest = createNode(iri) ; })?
#endif
    { return new UpdateLoad(url, dest, silent) ; }
}

Update Clear() : { boolean silent = false ; Target target ; }
{
   <CLEAR> (<SILENT> { silent = true ; })? target = GraphRefAll()
   { return new UpdateClear(target, silent) ; }
}

Update Drop() : { boolean silent = false ; Target target ; }
{
   <DROP> (<SILENT> { silent = true ; })? target = GraphRefAll()
   { return new UpdateDrop(target, silent) ; }
}

Update Create() : { Node iri ; boolean silent = false ; }
{
   <CREATE> (<SILENT> { silent=true ; } )? iri = GraphRef()
   { return new UpdateCreate(iri, silent) ; } 
}

Update Add() : { Target src ; Target dest ; boolean silent = false ; }
{
  <ADD>  (<SILENT> { silent=true ; } )? src = GraphOrDefault() <TO> dest = GraphOrDefault()
  { return new UpdateAdd(src, dest, silent) ; }
}

Update Move() : { Target src ; Target dest ; boolean silent = false ; } 
{
  <MOVE>  (<SILENT> { silent=true ; } )? src = GraphOrDefault() <TO> dest = GraphOrDefault()
  { return new UpdateMove(src, dest, silent) ; }
}

Update Copy() : { Target src ; Target dest ; boolean silent = false ; }
{
  <COPY>  (<SILENT> { silent=true ; } )? src = GraphOrDefault() <TO> dest = GraphOrDefault()
  { return new UpdateCopy(src, dest, silent) ; }
}

// #ifdef ARQ
// void Meta() : { QuadDataAcc qd = new QuadDataAcc() ; }
// {
//    <META> 
//    QuadData(qd)
// }
// #endif

Update InsertData() : { QuadDataAcc qd = new QuadDataAcc() ; Token t ; }
{
  t =  <INSERT_DATA>
  { startDataInsert(qd, t.beginLine, t.beginColumn) ; }
#ifndef ARQ_UPDATE
   QuadData(qd)
#else
   OptionalIntoTarget(qd)
   QuadPattern(qd)
#endif
  {
    finishDataInsert(qd, t.beginLine, t.beginColumn) ;
    return new UpdateDataInsert(qd) ; 
  }
}

Update DeleteData() : { QuadDataAcc qd = new QuadDataAcc() ; Token t ; }
{
  t = <DELETE_DATA>
  { startDataDelete(qd, t.beginLine, t.beginColumn) ; }
#ifndef ARQ_UPDATE
  QuadData(qd)
#else
  OptionalFromTarget(qd)
  QuadData(qd)
#endif
  { 
    finishDataDelete(qd, t.beginLine, t.beginColumn) ;
    return new UpdateDataDelete(qd) ;
  }
}

Update DeleteWhere() : { QuadAcc qp = new QuadAcc() ;  Token t ; }
{
  t = <DELETE_WHERE> 
  { startDeleteTemplate(qp, t.beginLine, t.beginColumn) ; }
  QuadPattern(qp)
  { finishDeleteTemplate(qp, t.beginLine, t.beginColumn) ; }
  { return new UpdateDeleteWhere(qp) ; }
}

Update Modify() : { Element el ; String iri = null ;
                    UpdateModify up = new UpdateModify() ; }
{
  ( <WITH> iri = IRIref() { Node n = createNode(iri) ; up.setWithIRI(n) ; } )?
  ( DeleteClause(up) ( InsertClause(up) )?
  | InsertClause(up)
  )
  (UsingClause(up))*
  <WHERE>
  el = GroupGraphPattern() { up.setElement(el) ; }    
  { return up ; }
}

#ifdef ARQ_UPDATE
Update ModifyOld() :
       { UpdateModify up = new UpdateModify() ; String iri ; Template template ; Element el ; }
{
    <MODIFY>
    ( iri = IRIref() { Node n = createNode(iri) ; up.setWithIRI(n) ; } )?
    (DeleteClause(up))?
    (InsertClause(up))?
    <WHERE>
    el = GroupGraphPattern() { up.setElement(el) ; }    
    { return up ; }
}
#endif

void DeleteClause(UpdateModify up) : { QuadAcc qp = up.getDeleteAcc() ;  Token t ;}
{
   t = <DELETE>
   { startDeleteTemplate(qp, t.beginLine, t.beginColumn) ; }
#ifndef ARQ_UPDATE
   QuadPattern(qp)
#else
   OptionalFromTarget(qp)
   QuadPattern(qp)
#endif
   { finishDeleteTemplate(qp, t.beginLine, t.beginColumn) ; }
   { up.setHasDeleteClause(true) ; }
}

void InsertClause(UpdateModify up) : { QuadAcc qp = up.getInsertAcc() ; Token t ; }
{
   t = <INSERT>
   { startInsertTemplate(qp, t.beginLine, t.beginColumn) ; }
#ifndef ARQ_UPDATE
   QuadPattern(qp)
#else
   OptionalIntoTarget(qp)
   QuadPattern(qp)
#endif
   { finishInsertTemplate(qp, t.beginLine, t.beginColumn) ; }
   { up.setHasInsertClause(true) ; }
}

#ifdef ARQ_UPDATE
void OptionalIntoTarget(QuadAcc qp) : { String iri ; }
{
  ( (<INTO>)? 
     iri = IRIref()
     { Node gn = createNode(iri) ; setAccGraph(qp, gn) ; }
   )?
}

void OptionalFromTarget(QuadAcc qp) : { String iri ; }
{
  ( (<FROM>)? 
     iri = IRIref()
     { Node gn = createNode(iri) ; setAccGraph(qp, gn) ; }
   )?
}
#endif

void UsingClause(UpdateWithUsing update) : { String iri ; Node n ; }
{
  <USING> 
  ( iri = IRIref() 
    { n = createNode(iri) ; update.addUsing(n) ; }
  | <NAMED> iri = IRIref()
    { n = createNode(iri) ; update.addUsingNamed(n) ; }
  )
}

Target GraphOrDefault() : { String iri ; }
{
  ( <DFT> { return Target.DEFAULT ; }
  |  (<GRAPH>)? 
     iri = IRIref()
     {  return Target.create(createNode(iri)) ; }
  )
}

Node GraphRef() : { String iri ; }
{
    <GRAPH> iri = IRIref()
    { return createNode(iri) ; }
}

Target GraphRefAll() : { Node iri ; }
{
   ( iri = GraphRef() 
     { return Target.create(iri) ; }
   | <DFT>    { return Target.DEFAULT ; }
   | <NAMED>  { return Target.NAMED ; } 
   | <ALL>    { return Target.ALL ; } 
   )
#ifdef ARQ_UPDATE
   ?
   { return Target.DEFAULT ; }
#endif
}

void QuadPattern(QuadAcc acc) : { }
{
    <LBRACE>
    Quads(acc)
    <RBRACE>
}

//Ground data : As QuadPattern but don't allow variables.
void QuadData(QuadDataAcc acc) : { }
{
    <LBRACE>
    Quads(acc)
    <RBRACE>
}

void Quads(QuadAcc acc) : { }
{
   (TriplesTemplate(acc))?
   (
     QuadsNotTriples(acc)
     (<DOT>)?
     (TriplesTemplate(acc))?
   )*
}

void QuadsNotTriples(QuadAcc acc) : {Node gn ; Node prev = acc.getGraph() ; }
{
    <GRAPH> gn = VarOrIRIref()
    { setAccGraph(acc, gn) ; }
    <LBRACE> 
    (TriplesTemplate(acc))?
    <RBRACE>
    { setAccGraph(acc, prev) ; }
    
}

void TriplesTemplate(TripleCollector acc) : { }
{    
    TriplesSameSubject(acc)
    (<DOT> (TriplesTemplate(acc))?)?
}

#endif // UPDATE

// ---- General Graph Pattern 

Element GroupGraphPattern() : { Element el = null ; Token t ; }
{
  t = <LBRACE>
  ( 
    { startSubSelect(t.beginLine, t.beginColumn) ; }
    SubSelect()
    { 
      Query q = endSubSelect(t.beginLine, t.beginColumn) ;
      el = new ElementSubQuery(q) ;
    }
  | el = GroupGraphPatternSub()
  )
  <RBRACE>
    { return el ; }
}

Element GroupGraphPatternSub() : { Element el = null ; }
{
      { ElementGroup elg = new ElementGroup() ; }
      { startGroup(elg) ; }
  // Ensure two BGP's can't be next to each other
  // Done by seeing if there is a non-BGP and recursing
  // if there is an intermediate
  (
    { startTriplesBlock() ; }
    el = TriplesBlock(null)
    { endTriplesBlock() ;
      elg.addElement(el) ; } 
  )?
  (
    el = GraphPatternNotTriples() 
    { elg.addElement(el) ; }

    (<DOT>)?

    (
      { startTriplesBlock() ; }
      el = TriplesBlock(null)
      { endTriplesBlock() ;
        elg.addElement(el) ; } 
    )?
  )*
      { endGroup(elg) ; }
      { return elg ; }
}

// -- TriplesBlock
// Two versions - for SPARQL 1.0 and SPARQL 1.1 (with paths)

// #ifdef SPARQL_10
// Element TriplesBlock(ElementTriplesBlock acc) : { }
// {
//   { if ( acc == null )
//         acc = new ElementTriplesBlock() ;
//   }
//   TriplesSameSubject(acc)
//   ( <DOT> (TriplesBlock(acc))? )?
//     { return acc ; }
// }
// #endif

Element TriplesBlock(ElementPathBlock acc) : { }
{
  { if ( acc == null )
        acc = new ElementPathBlock() ;
  }
  TriplesSameSubjectPath(acc)
  ( <DOT> (TriplesBlock(acc))? )?
    { return acc ; }
}

// -----

Element GraphPatternNotTriples() : { Element el = null ; }
{
 (
//    el = GroupGraphPattern()
//  |
//    el = UnionGraphPattern()
//  |
   el = GroupOrUnionGraphPattern()
 |
   el = OptionalGraphPattern()
 |
   el = MinusGraphPattern()
 |
   el = GraphGraphPattern()
 |
   el = ServiceGraphPattern()
 |
   el = Filter()
 |
   el = Bind()
#ifdef ARQ
 |
   el = Assignment()
 | 
   el = FetchGraph()
 |
   el = ExistsElt()
 |
   el = NotExistsElt()
#endif
 )
 { return el ; }
}

// ---- Definitions of each pattern element

Element OptionalGraphPattern() : { Element el ; }
{ <OPTIONAL> el = GroupGraphPattern()
    { return new ElementOptional(el) ; }
}

Element GraphGraphPattern() : { Element el ; Node n ;}
{
  <GRAPH> n = VarOrIRIref() el = GroupGraphPattern()
    { return new ElementNamedGraph(n, el) ; }
}


Element ServiceGraphPattern() : { Element el ; Node n ; boolean silent = false ; }
{
  <SERVICE> 
  (<SILENT>
   { silent=true; }
  )?
  n = VarOrIRIref()
  el = GroupGraphPattern()
    { return new ElementService(n, el, silent) ; }
}

Element Bind() : {  Var v ; Expr expr ; }
{
  <BIND>
  <LPAREN>
  expr = Expression()
  <AS>
  v = Var()
  <RPAREN>
  { return new ElementBind(v, expr) ; }
}

#ifdef ARQ

Element Assignment() : { Var v ; Expr expr ; }
{
  <LET>  
  <LPAREN>
  v = Var()
  <ASSIGN> 
  expr = Expression()
  <RPAREN>
    { return new ElementAssign(v, expr) ; }
}

Element FetchGraph() : { Node n ; }
{
  <FETCH>
  n = VarOrIRIref() 
  { return new ElementFetch(n) ; }
}


Element ExistsElt() : { Element el ; }
{
    <EXISTS>
    el = GroupGraphPattern()
    { return new ElementExists(el) ; }
}

Element NotExistsElt() : { Element el ; }
{
    <NOT> <EXISTS>
    el = GroupGraphPattern()
    { return new ElementNotExists(el) ; }
}
#endif

Element MinusGraphPattern() : { Element el ; }
{
    <MINUS_P>
    el = GroupGraphPattern()
    { return new ElementMinus(el) ; }
}

// Element UnionGraphPattern() : { Element el ; }
// {
//     <UNION>
//     el = GroupGraphPattern()
//     { return new ElementUnion(el) ; }
// }


// SPARQL 1.0: {pattern} UNION {pattern} UNION {pattern} ... :: 
// SPARQL 1.1 may introduce: { pattern UNION pattern UNION ... }


// G (union G)* can be a single group pattern
// or a group pattern as part of an union.
Element GroupOrUnionGraphPattern() :
    { Element el = null ; ElementUnion el2 = null ; }
{
  el = GroupGraphPattern()
  ( <UNION>
    { if ( el2 == null )
      {
        el2 = new ElementUnion() ;
        el2.addElement(el) ;
      }
    }
  el = GroupGraphPattern()
    { el2.addElement(el) ; } 
  )*
    { return (el2==null)? el : el2 ; }
}


Element Filter() : { Expr c ; }
{
  <FILTER> c = Constraint()
  { return new ElementFilter(c) ; }
}

Expr Constraint() : { Expr c ; }
{
  ( c = BrackettedExpression() 
  | c = BuiltInCall()
  | c = FunctionCall()
  )
  { return c ; }
}

Expr FunctionCall() : { String fname ; ExprList a ; }
{
  fname = IRIref()
  a = ArgList()
  { return new E_Function(fname, a) ; }
}

ExprList ArgList() : { Expr expr ; boolean distinct = false ;
                      ExprList args = new ExprList() ; Token t ; }
{ 
  (
    <NIL>
  |
    <LPAREN>
      (t = <DISTINCT> { distinct = true ; }
        {
          if ( ! allowAggregatesInExpressions )
              throwParseException("Aggregate expression not legal at this point",
                                 t.beginLine, t.beginColumn) ;
        }
      )?
      expr = Expression() { args.add(expr) ; } 
      (<COMMA> expr = Expression() { args.add(expr) ; } )*
    <RPAREN>
   )
    { return args ; }
}

ExprList ExpressionList() : { Expr expr = null ; ExprList args = new ExprList() ;}
{
  (
    <NIL>
  |
    <LPAREN>
    expr = Expression() { args.add(expr) ; } 
      (<COMMA> expr = Expression() { args.add(expr) ; } )* 
    <RPAREN>
  )
  { return args ; }
}

// -------- Construct patterns

Template ConstructTemplate() : { TripleCollectorBGP acc = new TripleCollectorBGP(); 
                                 Template t = new Template(acc.getBGP()) ; }
{
    { setInConstructTemplate(true) ; }
  <LBRACE> 
    (ConstructTriples(acc))?
  <RBRACE>
    { setInConstructTemplate(false) ;
      return t ; }
}

void ConstructTriples(TripleCollector acc) : { }
{
#ifdef SPARQL_11
// SPARQL - recursion - does not scale for SPARQL/Update
    TriplesSameSubject(acc)
    (<DOT> (ConstructTriples(acc))? )?
#endif
#ifdef ARQ
    // Rewrite for no recursion - grammar is not LL(1)
    TriplesSameSubject(acc)
    (LOOKAHEAD(2) (<DOT>) TriplesSameSubject(acc))*
    (<DOT>)?
#endif
}

// -------- Triple lists with property and object lists
// -------- Without paths: entry: TriplesSameSubject

void TriplesSameSubject(TripleCollector acc) : { Node s ; } 
{
  s = VarOrTerm()
  PropertyListNotEmpty(s, acc) 
|
  // Any of the triple generating syntax elements
  s = TriplesNode(acc)
  PropertyList(s, acc)
}

void PropertyListNotEmpty(Node s, TripleCollector acc) : 
    { Node p = null ; }
{
    p = Verb()
    ObjectList(s, p, null, acc)
  ( <SEMICOLON> 
    (
       p = Verb()
      ObjectList(s, p, null, acc)
    )? 
  )*
}

void PropertyList(Node s, TripleCollector acc) : { }
{
  ( PropertyListNotEmpty(s, acc) ) ?
}

void ObjectList(Node s,  Node p, Path path, TripleCollector acc): { Node o ; } 
{
  Object(s, p, path, acc)
  ( <COMMA> Object(s, p, path, acc) )*
}

void Object(Node s, Node p, Path path, TripleCollector acc): { Node o ; }
{
    { int mark = acc.mark() ; }
  o = GraphNode(acc) 
  { insert(acc, mark, s, p, path, o) ; }
}

Node Verb() : { Node p ;}
{
// Blank nodes as predicates
//   ( p = VarOrBlankNodeOrIRIref() | <KW_A> { p = nRDFtype ; } )
  ( p = VarOrIRIref() | <KW_A> { p = nRDFtype ; } )
  { return p ; }
}

// -------- BGPs with paths.
// -------- Entry point: TriplesSameSubjectPath

void TriplesSameSubjectPath(TripleCollector acc) : { Node s ; } 
{
  s = VarOrTerm()
  PropertyListNotEmptyPath(s, acc) 
|
  // Any of the triple generating syntax elements
  s = TriplesNode(acc)
  PropertyListPath(s, acc)
}

void PropertyListNotEmptyPath(Node s, TripleCollector acc) : 
    { Path path = null ; Node p = null ; }
{
  ( path = VerbPath()
  | p = VerbSimple()
  )

  ObjectList(s, p, path, acc)
  ( <SEMICOLON> 
    { path = null ; p = null ; }
    (
      ( path = VerbPath()
      | p = VerbSimple()
      )
      ObjectList(s, p, path, acc)
    )? 
  )*
#if 0
  |
  Reification(s, acc)
#endif
}

void PropertyListPath(Node s, TripleCollector acc) : { }
{
  ( PropertyListNotEmpty(s, acc) ) ?
}


Path VerbPath() : {Node p ; Path path ; }
{
  path = Path() { return path ; }
}

Node VerbSimple() : { Node p ; }
{
  // "a" now allowed in paths.
  //( p = Var() | <KW_A> { p = nRDFtype ; } )
  p = Var()
  { return p ; }
}
// End paths stuff.

// -------- Paths

#ifdef ARQ
Path PathUnit() : { Path p ; }
{
    p = Path()
    <EOF>
    { return p ; }
}
#endif

// Weakest outermost
Path Path() : { Path p ; }
{ 
  p = PathAlternative() { return p ; }
}

Path PathAlternative() : { Path p1 , p2 ; }
{
   p1 = PathSequence()
   (
      <VBAR> p2 = PathSequence()
      { p1 = PathFactory.pathAlt(p1, p2) ; }
   )*
   { return p1 ; }
}

Path PathSequence() : { Path p1 , p2 ; }
{
    p1 = PathEltOrInverse()
    ( <SLASH> p2 = PathEltOrInverse()
      { p1 = PathFactory.pathSeq(p1, p2) ; }
#ifdef ARQ
    // :p^:q -- Not in SPARQL 1.1
    | <CARAT> p2 = PathElt()
      { p1 = PathFactory.pathSeq(p1, new P_Inverse(p2)) ; }
#endif
    )*
   { return p1; }
}

// Path unit element, no inverse
Path PathElt() : { String str ; Node n ; Path p ; }
{ 
   p = PathPrimary() 
   ( p = PathMod(p) )?
   { return p ; }
}

// Path unit element, including inverse.
Path PathEltOrInverse() : { String str ; Node n ; Path p ; }
{ 
   ( p = PathElt() 
   | <CARAT>
     p = PathElt()
     { p = PathFactory.pathInverse(p) ; }
   )
   { return p ; }
}

Path PathMod(Path p) : { long i1 ; long i2 ; }
{
   ( <STAR>   { return PathFactory.pathZeroOrMore(p) ; }
   | <QMARK>  { return PathFactory.pathZeroOrOne(p) ; }
   | <PLUS>   { return PathFactory.pathOneOrMore(p) ; }
   | <LBRACE>
       (  // {N} {N,M} {N,}
          i1 = Integer()
          ( <COMMA>
            ( // case {N,}
              <RBRACE> 
              { return PathFactory.pathMod(p, i1, PathFactory.UNSET) ; } 
            | // case {N,M}
              i2 = Integer() <RBRACE> // case {N,M}
              { return PathFactory.pathMod(p, i1, i2) ; } 
            )
          |
            <RBRACE>   // {N}
                     { return PathFactory.pathFixedLength(p, i1) ; }
          )
       |   // {,N}
         <COMMA>
         i2 = Integer()
         <RBRACE>
           { return PathFactory.pathMod(p, PathFactory.UNSET, i2) ; } 
       )
   )
}

Path PathPrimary() : { String str ; Path p ; Node n ; }
{
  ( 
    str = IRIref()
     { n = createNode(str) ; p = PathFactory.pathLink(n) ; }
  | <KW_A> 
     { p = PathFactory.pathLink(nRDFtype) ; }
  | <BANG> p = PathNegatedPropertySet()
  | <LPAREN> p = Path() <RPAREN>
  )
    { return p ; }
}

Path PathNegatedPropertySet() : { P_Path0 p ; P_NegPropSet pNegSet ; }
{
  { pNegSet = new P_NegPropSet() ; }

  ( p = PathOneInPropertySet()
    { pNegSet.add(p) ; }
  | <LPAREN> 
    ( p = PathOneInPropertySet() { pNegSet.add(p) ; }
      (<VBAR> p = PathOneInPropertySet() { pNegSet.add(p) ; }) *
    )? 
     <RPAREN>
  ) 
  { return pNegSet ; }
}

P_Path0 PathOneInPropertySet() : { String str ; Node n ; }
{
  ( str = IRIref() { n = createNode(str) ; return new P_Link(n) ; } 
  | <KW_A>         { return new P_Link(nRDFtype) ; }
  // This is the !(^:property) form.
  | <CARAT>  
    ( str = IRIref() { n = createNode(str) ; return new P_ReverseLink(n) ; } 
    | <KW_A> { return new P_ReverseLink(nRDFtype) ; } 
    )
  )
}


long Integer() : {Token t ;}
{
    t = <INTEGER> 
    { return integerValue(t.image) ; }
}

// -------- Triple expansions

// Anything that can stand in a node slot and which is
// a number of triples

Node TriplesNode(TripleCollector acc) : { Node n ; }
{
  n = Collection(acc) { return n ; }
 |
  n = BlankNodePropertyList(acc) { return n ; }
#if 0
 |
  n = Reification(null, acc) { return n ; }
#endif
}

Node BlankNodePropertyList(TripleCollector acc) : { Token t ; }
{
  t = <LBRACKET> 
    { Node n = createBNode( t.beginLine, t.beginColumn) ; }
  PropertyListNotEmpty(n, acc)
  <RBRACKET>
    { return n ; }
}
#if 0
Node Reification(Node id, TripleCollector acc) : 
    { Node s , p , o ; int mark ; Token t ; }
{
  // For generality, should be AndNode for s/p/o
  // Insert reification triple before the resulting subtriples (if any)
  t = "<<" 
    { if ( id == null )
        id = createBNode(t.beginLine, t.beginColumn() ;
      mark = acc.mark() ; }
  s = GraphNode(acc)
    { insert(acc, mark, id, nRDFsubject, s) ;
      mark = acc.mark() ; 
    }
  p = GraphNode(acc)
    { insert(acc, mark, id, nRDFpredicate, p) ;
      mark = acc.mark() ;
    }
  o = GraphNode(acc)
    { insert(acc, mark, id, nRDFobject, o) ; }
  ">>"
    { return id ; }
}
#endif

// ------- RDF collections

Node Collection(TripleCollector acc) : 
    { Node listHead = nRDFnil ; Node lastCell = null ; int mark ; Node n ; Token t ; }
{
  t = <LPAREN> 
  (
    { Node cell = createListNode( t.beginLine, t.beginColumn) ;
      if ( listHead == nRDFnil )
         listHead = cell ;
      if ( lastCell != null )
        insert(acc, lastCell, nRDFrest,  cell) ;
      mark = acc.mark() ;
    }
    n = GraphNode(acc)
    {
      insert(acc, mark, cell, nRDFfirst, n) ;
      lastCell = cell ;
    }
  ) +
  // Not * here - "()" is handled separately.
  <RPAREN>
   { if ( lastCell != null )
       insert(acc, lastCell, nRDFrest,  nRDFnil) ;
     return listHead ; }
}

// -------- Nodes in a graph pattern or template

Node GraphNode(TripleCollector acc) : { Node n ; }
{
  n = VarOrTerm() { return n ; }
 |
  n = TriplesNode(acc) { return n ; }
}

Node VarOrTerm() : {Node n = null ; }
{
  ( n = Var() | n = GraphTerm() )
  { return n ; }
}

// Property (if no bNodes) + DESCRIBE
Node VarOrIRIref() : {Node n = null ; String iri ; }
{
  ( n = Var() | iri = IRIref() { n = createNode(iri) ; } )
  { return n ; }
}

Var Var() : { Token t ;}
{
    ( t = <VAR1> | t = <VAR2> )
    { return createVariable(t.image, t.beginLine, t.beginColumn) ; }
}

Node GraphTerm() : { Node n ; String iri ; }
{
  iri = IRIref()        { return createNode(iri) ; }
| n = RDFLiteral()      { return n ; }
| n = NumericLiteral()  { return n ; }
| n = BooleanLiteral()  { return n ; }
| n = BlankNode()       { return n ; }   
  //  <LPAREN> <RPAREN>     { return nRDFnil ; }
| <NIL>  { return nRDFnil ; }
}

// -------- Constraint syntax

Expr Expression() : { Expr expr ; }
{
  expr = ConditionalOrExpression()
  { return expr ; }
}

Expr ConditionalOrExpression() : { Expr expr1, expr2 ; }
{
  expr1 = ConditionalAndExpression() 
  ( <SC_OR> expr2 = ConditionalAndExpression()
    { expr1 = new E_LogicalOr(expr1, expr2) ; } 
  )*
    { return expr1 ; }
    
}

Expr ConditionalAndExpression() : { Expr expr1, expr2 ;}
{
  expr1 = ValueLogical()
  ( <SC_AND> expr2 = ValueLogical()
    { expr1 = new E_LogicalAnd(expr1, expr2) ; }
  )*
    { return expr1 ; }
}

Expr ValueLogical() : { Expr expr ; }
{
  expr = RelationalExpression()
    { return expr ; }
}

Expr RelationalExpression() : { Expr expr1, expr2 ; ExprList a ; }
{
  expr1 = NumericExpression()
  (
    <EQ> expr2 = NumericExpression()
      { expr1 = new E_Equals(expr1, expr2) ; }
  | <NE> expr2 = NumericExpression()
      { expr1 = new E_NotEquals(expr1, expr2) ; }
  | <LT> expr2 = NumericExpression()
      { expr1 = new E_LessThan(expr1, expr2) ; }
  | <GT> expr2 = NumericExpression()
      { expr1 = new E_GreaterThan(expr1, expr2) ; }
  | <LE> expr2 = NumericExpression()
      { expr1 = new E_LessThanOrEqual(expr1, expr2) ; }
  | <GE> expr2 = NumericExpression()
      { expr1 = new E_GreaterThanOrEqual(expr1, expr2) ; }
  | <IN> a = ExpressionList()
      { expr1 = new E_OneOf(expr1, a) ; }
  | <NOT> <IN> a = ExpressionList()
      { expr1 = new E_NotOneOf(expr1, a) ; }
  )?
    { return expr1 ; }
}

Expr NumericExpression ()  : { Expr expr ; }
{
  expr = AdditiveExpression()
    { return expr ; }
}

Expr AdditiveExpression() : { Expr expr1, expr2, expr3 ; boolean addition ; Node n ; }
{
  expr1 = MultiplicativeExpression()
  ( <PLUS> expr2 = MultiplicativeExpression()
    { expr1 = new E_Add(expr1, expr2) ; }
  | <MINUS> expr2 = MultiplicativeExpression()
    { expr1 = new E_Subtract(expr1, expr2) ; }

// SPARQL Bug.
//   | n = NumericLiteralPositive()
//     { 
//       n = stripSign(n) ;
//       expr2 = asExpr(n) ;
//       expr1 = new E_Add(expr1, expr2) ; 
//     }
//   |
//     n = NumericLiteralNegative()
//     { 
//       n = stripSign(n) ;
//       expr2 = asExpr(n) ;
//       expr1 = new E_Subtract(expr1, expr2) ; 
//     }
//   )*

  // Expression - no + or -
  |
    (
      n = NumericLiteralPositive()
      {
         n = stripSign(n) ;
         expr2 = asExpr(n) ;
         addition = true ;
      }
    |
      n = NumericLiteralNegative()
     { 
         n = stripSign(n) ;
         expr2 = asExpr(n) ;
         addition = false ;
     }
     )

    (
      ( <STAR>  expr3 = UnaryExpression() { expr2 = new E_Multiply(expr2, expr3) ; } )
    |
      ( <SLASH>  expr3 = UnaryExpression() { expr2 = new E_Divide(expr2, expr3) ; } )
    )?

    { if ( addition )
         expr1 = new E_Add(expr1, expr2) ;
      else
         expr1 = new E_Subtract(expr1, expr2) ;
    }
  )*
  { return expr1 ; }
}

Expr MultiplicativeExpression() : { Expr expr1, expr2 ; }
{
  expr1 = UnaryExpression()
  ( <STAR>  expr2 = UnaryExpression()
    { expr1 = new E_Multiply(expr1, expr2) ; }
  | <SLASH> expr2 = UnaryExpression()
    { expr1 = new E_Divide(expr1, expr2) ; }
//   | <REM>   expr2 = UnaryExpression()
//     { expr1 = new E_Modulus(expr1, expr2) ; }
  )*
    { return expr1 ; }
}

Expr UnaryExpression() : { Expr expr ; }
{
  <BANG> expr = PrimaryExpression()
    { return new E_LogicalNot(expr) ; }
  | <PLUS>  expr = PrimaryExpression() { return new E_UnaryPlus(expr) ; }
  | <MINUS> expr = PrimaryExpression() { return new E_UnaryMinus(expr) ; }
  | expr = PrimaryExpression() { return expr ; }
}

Expr PrimaryExpression() : { Expr expr ; Node gn ; }
{
  ( expr = BrackettedExpression() { return expr ; }
  | expr = BuiltInCall() { return expr ; }  
  | expr = IRIrefOrFunction()  { return expr ; }

// NOT  | gn = VarOrTerm()           { return asExpr(gn) ; }
// Because of IRIrefOrFunction 
  | gn = RDFLiteral()      { return asExpr(gn) ; }
  | gn = NumericLiteral()  { return asExpr(gn) ; }
  | gn = BooleanLiteral()  { return asExpr(gn) ; }
  | gn = Var()             { return asExpr(gn) ; }
  | expr = Aggregate() { return expr ; }
  )
}

Expr BrackettedExpression() : { Expr expr ; }
{
    <LPAREN> expr = Expression() <RPAREN>  { return expr ; }
}

Expr BuiltInCall() : { Expr expr ; Expr expr1 = null ; Expr expr2 = null ; 
                       Node gn ; Token t ; ExprList a ; }
{
    <STR> <LPAREN> expr = Expression() <RPAREN>
    { return new E_Str(expr) ; }
  | <LANG> <LPAREN> expr = Expression() <RPAREN>
    { return new E_Lang(expr) ; }

  | <LANGMATCHES> 
       <LPAREN> expr1 = Expression() <COMMA> expr2 = Expression() <RPAREN>
    { return new E_LangMatches(expr1, expr2) ; }

  | <DTYPE> <LPAREN> expr = Expression() <RPAREN>
    { return new E_Datatype(expr) ; }

  | <BOUND> <LPAREN> gn = Var() <RPAREN>
    { return new E_Bound(new ExprVar(gn)) ; }

  | <IRI> <LPAREN> expr = Expression() <RPAREN>
    { return new E_IRI(expr) ; }

  | <URI> <LPAREN> expr = Expression() <RPAREN>
    { return new E_URI(expr) ; }

  | <BNODE> 
    ( <LPAREN> expr1 = Expression() <RPAREN>
      { return new E_BNode(expr1) ; }
    |
      <NIL> { return new E_BNode() ; }
    )

  | <RAND> <NIL> { return new E_Random() ; }

  | <ABS>  <LPAREN> expr1 = Expression() <RPAREN> { return new E_NumAbs(expr1) ; }
    
  | <CEIL> <LPAREN> expr1 = Expression() <RPAREN> { return new E_NumCeiling(expr1) ; }
    
  | <FLOOR> <LPAREN> expr1 = Expression() <RPAREN> { return new E_NumFloor(expr1) ; }
    
  | <ROUND> <LPAREN> expr1 = Expression() <RPAREN> { return new E_NumRound(expr1) ; }
    
  | <CONCAT> a = ExpressionList() { return new E_StrConcat(a) ; }
    
  | expr = SubstringExpression() { return expr ; }
    
  | <STRLEN> <LPAREN> expr1 = Expression() <RPAREN> { return new E_StrLength(expr1) ; }
    
  | <UCASE> <LPAREN> expr1 = Expression() <RPAREN> { return new E_StrUpperCase(expr1) ; }
    
  | <LCASE> <LPAREN> expr1 = Expression() <RPAREN> { return new E_StrLowerCase(expr1) ; }
    
  | <ENCODE_FOR_URI> <LPAREN> expr1 = Expression() <RPAREN> { return new E_StrEncodeForURI(expr1) ; }
    
  | <CONTAINS> <LPAREN> expr1 = Expression() <COMMA> expr2 = Expression() <RPAREN>
    { return new E_StrContains(expr1, expr2) ; }
    
  | <STRSTARTS> <LPAREN> expr1 = Expression() <COMMA> expr2 = Expression() <RPAREN>
    { return new E_StrStartsWith(expr1, expr2) ; }
    
  | <STRENDS> <LPAREN> expr1 = Expression() <COMMA> expr2 = Expression() <RPAREN>
    { return new E_StrEndsWith(expr1, expr2) ; }
    
  | <YEAR> <LPAREN> expr1 = Expression() <RPAREN> { return new E_DateTimeYear(expr1) ; }
    
  | <MONTH> <LPAREN> expr1 = Expression() <RPAREN> { return new E_DateTimeMonth(expr1) ; }
    
  | <DAY> <LPAREN> expr1 = Expression() <RPAREN> { return new E_DateTimeDay(expr1) ; }
    
  | <HOURS> <LPAREN> expr1 = Expression() <RPAREN> { return new E_DateTimeHours(expr1) ; }
    
  | <MINUTES> <LPAREN> expr1 = Expression() <RPAREN> { return new E_DateTimeMinutes(expr1) ; }
    
  | <SECONDS> <LPAREN> expr1 = Expression() <RPAREN> { return new E_DateTimeSeconds(expr1) ; }
    
  | <TIMEZONE> <LPAREN> expr1 = Expression() <RPAREN> { return new E_DateTimeTimezone(expr1) ; }
  | <TZ> <LPAREN> expr1 = Expression() <RPAREN> { return new E_DateTimeTZ(expr1) ; }

  | <NOW> <NIL>   { return new E_Now() ; }

  | <MD5>         <LPAREN> expr1 = Expression() <RPAREN> { return new E_MD5(expr1) ; }

  | <SHA1>        <LPAREN> expr1 = Expression() <RPAREN> { return new E_SHA1(expr1) ; }

  | <SHA224>      <LPAREN> expr1 = Expression() <RPAREN> { return new E_SHA224(expr1) ; }

  | <SHA256>      <LPAREN> expr1 = Expression() <RPAREN> { return new E_SHA256(expr1) ; }

  | <SHA384>      <LPAREN> expr1 = Expression() <RPAREN> { return new E_SHA384(expr1) ; }

  | <SHA512>      <LPAREN> expr1 = Expression() <RPAREN> { return new E_SHA512(expr1) ; }

#if 0
  | <VERSION> <NIL>     { return new E_Version(); }
#endif    

  | <COALESCE> a = ExpressionList()
    { return new E_Coalesce(a) ; }

  | <IF> <LPAREN> expr = Expression() <COMMA> 
                  expr1 = Expression() <COMMA> 
                  expr2 = Expression() <RPAREN>
    { return new E_Conditional(expr, expr1, expr2) ; }

  | <STRLANG> <LPAREN> expr1 = Expression() <COMMA> expr2 = Expression() <RPAREN>
    { return new E_StrLang(expr1, expr2) ; }

  | <STRDT> <LPAREN> expr1 = Expression() <COMMA> expr2 = Expression() <RPAREN>
    { return new E_StrDatatype(expr1, expr2) ; }

#ifdef ARQ
  // Also allowed ?func(?a1,?a2,...)
  | <CALL> a = ExpressionList()
    { return new E_Call(a) ; }
#endif

  | <SAME_TERM> <LPAREN> expr1 = Expression() <COMMA> expr2 = Expression() <RPAREN>
    { return new E_SameTerm(expr1, expr2) ; }

  | t = <IS_IRI> <LPAREN> expr = Expression() <RPAREN>
    { return new E_IsIRI(expr) ; }

  | t = <IS_URI> <LPAREN> expr = Expression() <RPAREN>
    { return new E_IsURI(expr) ; }

  | <IS_BLANK> <LPAREN> expr = Expression() <RPAREN>
    { return new E_IsBlank(expr) ; }

  | <IS_LITERAL> <LPAREN> expr = Expression() <RPAREN>
    { return new E_IsLiteral(expr) ; }

  | <IS_NUMERIC> <LPAREN> expr = Expression() <RPAREN>
    { return new E_IsNumeric(expr) ; }

  | // Regular expression matcher
    expr = RegexExpression() { return expr ; }

  | expr = ExistsFunc()      { return expr ; }

  | expr = NotExistsFunc()   { return expr ; }
}

Expr RegexExpression() :
{ Expr expr ; Expr patExpr = null ; Expr flagsExpr = null ; }
{
    <REGEX> 
    <LPAREN> 
      expr = Expression() 
      <COMMA>
      patExpr = Expression()
      ( <COMMA> flagsExpr = Expression() ) ?
    <RPAREN>
      { return new E_Regex(expr, patExpr, flagsExpr) ; }
}

Expr SubstringExpression() :
{ Expr expr1 ; Expr expr2 = null ; Expr expr3 = null ; }
{
    <SUBSTR>
    <LPAREN> 
      expr1 = Expression() 
      <COMMA>
      expr2 = Expression()
      ( <COMMA> expr3 = Expression() ) ?
    <RPAREN>
      { return new E_StrSubstring(expr1, expr2, expr3) ; }
}

Expr ExistsFunc() : { Element el ; }
{
   <EXISTS>
   el = GroupGraphPattern()
   { return createExprExists(el) ; }
}

Expr NotExistsFunc() : { Element el ; }
{
   <NOT> <EXISTS>
   el = GroupGraphPattern()
   { return createExprNotExists(el) ; }
}


Expr Aggregate() : { Aggregator agg = null ; String sep = null ;
                     boolean distinct = false ;
                     Expr expr = null ; ExprList a = new ExprList() ;
                     Token t ; }
{
  // Count is special because of COUNT(*)
  // GROUP_CONCAT is special because of separator=

  ( t = <COUNT> <LPAREN> 
    ( <DISTINCT> { distinct = true ; } )?
    ( <STAR> | expr = Expression() )
    <RPAREN>
    { if ( expr == null ) { agg = AggregatorFactory.createCount(distinct) ; }
      if ( expr != null ) { agg = AggregatorFactory.createCountExpr(distinct, expr) ; }
    }

  | t = <SUM> <LPAREN> ( <DISTINCT> { distinct = true ; } )? expr = Expression() <RPAREN> 
    { agg = AggregatorFactory.createSum(distinct, expr) ; }

  | t = <MIN> <LPAREN> ( <DISTINCT> { distinct = true ; } )? expr = Expression() <RPAREN>
    { agg = AggregatorFactory.createMin(distinct, expr) ; }

  | t = <MAX> <LPAREN> ( <DISTINCT> { distinct = true ; } )? expr = Expression() <RPAREN>
    { agg = AggregatorFactory.createMax(distinct, expr) ; }

  | t = <AVG> <LPAREN> ( <DISTINCT> { distinct = true ; } )? expr = Expression() <RPAREN>
    { agg = AggregatorFactory.createAvg(distinct, expr) ; }

  | t = <SAMPLE> <LPAREN> ( <DISTINCT> { distinct = true ; } )? expr = Expression() <RPAREN>
    { agg = AggregatorFactory.createSample(distinct, expr) ; }

  | t = <GROUP_CONCAT>
    <LPAREN>
    (t = <DISTINCT> { distinct = true ; })?
    expr = Expression() { a.add(expr) ; } 
    // Single arg version
    (<SEMICOLON> <SEPARATOR> <EQ> sep=String())?
#ifdef false
    { Expr expr2 ; }
    // Limited GROUP BY
    (<SEMICOLON> <GROUP><BY> expr2 = Expression()
#endif
    <RPAREN>
    { agg = AggregatorFactory.createGroupConcat(distinct, expr, sep) ; }
//     (<COMMA> expr = Expression() { a.add(expr) ; } )*
//     (<SEMICOLON> <SEPARATOR> <EQ> sep=String())?
//     <RPAREN>
//     { agg = AggregatorFactory.createGroupConcat(distinct, a, sep) ; }
   )

   {
     if ( ! allowAggregatesInExpressions )
            throwParseException("Aggregate expression not legal at this point",
                                 t.beginLine, t.beginColumn) ;
   }
   { Expr exprAgg = getQuery().allocAggregate(agg) ;
     return exprAgg ; }
}

// See also FunctionCall.
// The case of "q:name()" or "q:agg()" or just "q:name"
// by expanding out FunctionCall()

Expr IRIrefOrFunction() : { String iri ; ExprList a = null ; 
                            ExprList params = null ; 
                            boolean distinct = false ; }
{
  iri = IRIref()
  (a = ArgList())?
  { if ( a == null ) 
       return asExpr(createNode(iri)) ;
    return new E_Function(iri, a) ;
  }
}

#ifdef ARQ
// The case of "?var()" or just "?var"
Expr VarOrFunction() : { Var v ; ExprList a = null ; }
{
  v = Var()
  { Expr ev = new ExprVar(v) ; }
  ( a = ExpressionList() )?
  { if ( a == null ) return ev ;
    return new E_FunctionDynamic(ev, a) ;
  }
}
#endif


Node RDFLiteral() : { Token t ; String lex = null ; }
{
  lex = String()
  // Optional lang tag and datatype.
  { String lang = null ; String uri = null ; }
  (
    ( t = <LANGTAG>  { lang = stripChars(t.image, 1) ; } )
  |
    ( <DATATYPE> uri = IRIref() )
  )?
    { return createLiteral(lex, lang, uri) ; }
} 


Node NumericLiteral() : { Node n ; }
{
  (
    n = NumericLiteralUnsigned()
  | n = NumericLiteralPositive()
  | n = NumericLiteralNegative()
  )
  { return n ; }

}

Node NumericLiteralUnsigned() : { Token t ; }
{
  t = <INTEGER> { return createLiteralInteger(t.image) ; }
| t = <DECIMAL> { return createLiteralDecimal(t.image) ; }
| t = <DOUBLE>  { return createLiteralDouble(t.image) ; }
}

Node NumericLiteralPositive() : { Token t ; }
{
  t = <INTEGER_POSITIVE> { return createLiteralInteger(t.image) ; }
| t = <DECIMAL_POSITIVE> { return createLiteralDecimal(t.image) ; }
| t = <DOUBLE_POSITIVE>  { return createLiteralDouble(t.image) ; }
}

Node NumericLiteralNegative() : { Token t ; }
{
  t = <INTEGER_NEGATIVE> { return createLiteralInteger(t.image) ; }
| t = <DECIMAL_NEGATIVE> { return createLiteralDecimal(t.image) ; }
| t = <DOUBLE_NEGATIVE>  { return createLiteralDouble(t.image) ; }
}


Node BooleanLiteral() : {}
{
  <TRUE> { return XSD_TRUE ; }
 |
  <FALSE> { return XSD_FALSE ; }
}

String String() : { Token t ; String lex ; }
{
  ( t = <STRING_LITERAL1> { lex = stripQuotes(t.image) ; }
  | t = <STRING_LITERAL2> { lex = stripQuotes(t.image) ; }
  | t = <STRING_LITERAL_LONG1> { lex = stripQuotes3(t.image) ; }
  | t = <STRING_LITERAL_LONG2> { lex = stripQuotes3(t.image) ; }
  )
    {
      lex = unescapeStr(lex,  t.beginLine, t.beginColumn) ;
      return lex ;
    }
}

String IRIref() : { String iri ; }
{
  iri = IRI_REF() { return iri ; }
|
  iri = PrefixedName() { return iri ; }
}

String PrefixedName() : { Token t ; }
{
  ( t = <PNAME_LN>
    { return resolvePName(t.image, t.beginLine, t.beginColumn) ; }
  |
    t = <PNAME_NS>
    { return resolvePName(t.image, t.beginLine, t.beginColumn) ; }
  )
}

Node BlankNode() :  { Token t = null ; }
{
  t = <BLANK_NODE_LABEL>
    { return createBNode(t.image, t.beginLine, t.beginColumn) ; }  
|
//  <LBRACKET> <RBRACKET> { return createBNode(t.beginLine, t.beginColumn) ; }
  t = <ANON> { return createBNode(t.beginLine, t.beginColumn) ; }

}

String IRI_REF() : { Token t ; }
{
  t = <IRIref>
  { return resolveQuotedIRI(t.image, t.beginLine, t.beginColumn) ; }
}

// ------------------------------------------
// Tokens

// Comments and whitespace

SKIP : { " " | "\t" | "\n" | "\r" | "\f" }

SPECIAL_TOKEN :
{ <SINGLE_LINE_COMMENT: "#" (~["\n","\r"])* ("\n"|"\r"|"\r\n")? > }

TOKEN: { 
  <#WS: " " | "\t" | "\n" | "\r" | "\f">
|
  // Whitespace or comment.
  <#WSC: <WS> | <SINGLE_LINE_COMMENT> >
}

// Main tokens */

TOKEN:
{
   // Includes # for relative URIs
   <IRIref: "<" (~[ ">","<", "\"", "{", "}", "^", "\\", "|", "`", 
                      "\u0000"-"\u0020"])* ">" >
|  <PNAME_NS: (<PN_PREFIX>)? ":" >
|  <PNAME_LN: <PNAME_NS> <PN_LOCAL> >
|  <BLANK_NODE_LABEL: "_:" <PN_LOCAL> >
|  <VAR1: "?" <VARNAME> >
|  <VAR2: "$" <VARNAME> >
|  <LANGTAG: <AT> (<A2Z>)+("-" (<A2ZN>)+)* >
|  <#A2Z: ["a"-"z","A"-"Z"]>
|  <#A2ZN: ["a"-"z","A"-"Z","0"-"9"]>
}

// -------------------------------------------------
// Keyworks : includes operators that are words and should be
// before general things like IDENTIFIER which swallow almost
// anything

TOKEN : { <KW_A:  "a" > }

TOKEN [IGNORE_CASE] :
{
// Prologue
   < BASE:        "base" >
|  < PREFIX:      "prefix" >

// Result forms
|  < SELECT:      "select" >
|  < DISTINCT:    "distinct" >
|  < REDUCED:     "reduced" >
|  < DESCRIBE:    "describe" >
|  < CONSTRUCT:   "construct" >
|  < ASK:         "ask" >

|  < LIMIT:       "limit" >
|  < OFFSET:      "offset" >
|  < ORDER:       "order" >
|  < BY:          "by" >
|  < BINDINGS:    "bindings" >
|  < UNDEF:       "undef" >

|  < ASC:         "asc" >
|  < DESC:        "desc" >

// Dataset
|  < NAMED:       "named" >
|  < FROM:        "from" >

// Graph pattern operators 
|  < WHERE:       "where" >
|  < AND:         "and" >
|  < GRAPH:       "graph" >
|  < OPTIONAL:    "optional" >
|  < UNION:       "union" >
|  < MINUS_P:     "minus" >
|  < BIND:        "bind" >
|  < SERVICE:     "service" >

#ifdef ARQ
|  < LET:         "let" >
|  < FETCH:       "fetch" >
#endif
|  < EXISTS:      "exists" >
|  < NOT:         "not" >
//|  < UNSAID:      "unsaid" >
|  < AS:          "as" >
|  < GROUP:       "group" >
|  < HAVING:      "having" >
|  < SEPARATOR:   "separator" >
|  < AGG:         "agg" >
|  < COUNT:       "count" >
|  < MIN:         "min" >
|  < MAX:         "max" >
|  < SUM:         "sum" >
|  < AVG:         "avg" >
|  < STDDEV:      "stdev" >
|  < SAMPLE:      "sample" >
|  < GROUP_CONCAT: "group_concat" >

|  < FILTER:      "filter" >

// Expression operators
|  < BOUND:       "bound" >
|  < COALESCE:    "coalesce" >
|  < IN:          "in" >
|  < IF:          "if" >
|  < BNODE:       "bnode" >
|  < IRI:         "iri" >
|  < URI:         "uri" >

#ifdef ARQ
|  < CAST:        "cast" >
|  < CALL:        "call" >
#endif

|  < STR:         "str" >
|  < STRLANG:     "strlang" >
|  < STRDT:       "strdt" >
|  < DTYPE:       "datatype" >
|  < LANG:        "lang" >
|  < LANGMATCHES: "langmatches" >
|  < IS_URI:      "isURI" >
|  < IS_IRI:      "isIRI" >
|  < IS_BLANK:    "isBlank" >
|  < IS_LITERAL:  "isLiteral" >
|  < IS_NUMERIC:  "isNumeric" >
|  < REGEX:       "regex" >
|  < SAME_TERM:   "sameTerm" >

|  < RAND:        "RAND" >
|  < ABS:         "ABS" >
|  < CEIL:        "CEIL" >
|  < FLOOR:       "FLOOR" >
|  < ROUND:       "ROUND" >
|  < CONCAT:      "CONCAT" >
|  < SUBSTR:      "SUBSTR" >
|  < STRLEN:      "STRLEN" >
|  < UCASE:       "UCASE" >
|  < LCASE:       "LCASE" >
|  < ENCODE_FOR_URI:      "ENCODE_FOR_URI" >
|  < CONTAINS:    "CONTAINS" >
|  < STRSTARTS:    "strSTARTS" >
|  < STRENDS:        "strENDS" >
|  < YEAR:        "YEAR" >
|  < MONTH:       "MONTH" >
|  < DAY:         "DAY" >
|  < HOURS:       "HOURS" >
|  < MINUTES:     "MINUTES" >
|  < SECONDS:     "SECONDS" >
|  < TIMEZONE:    "TIMEZONE" >
|  < TZ:          "TZ" >
|  < NOW:         "NOW" >

#ifdef ARQ
|  < VERSION:     "VERSION" >
#endif

| < MD5:          "MD5" >
| < SHA1:         "SHA1" >
| < SHA224:       "SHA224" >
| < SHA256:       "SHA256" >
| < SHA384:       "SHA384" >
| < SHA512:       "SHA512" >

|  < TRUE:        "true" >
|  < FALSE:       "false" >
}

#if defined(UPDATE)
// SPARQL/Update parts.

TOKEN [IGNORE_CASE] :
{
  < #DATA:	      "data" >
| < INSERT:       "insert">
| < DELETE:       "delete" >

| < INSERT_DATA:  <INSERT> (<WSC>)* <DATA> >
| < DELETE_DATA:  <DELETE> (<WSC>)* <DATA> >
| < DELETE_WHERE: <DELETE> (<WSC>)* <WHERE> >

#ifdef ARQ_UPDATE
| < MODIFY:      "modify">
#endif
| < LOAD:         "load" >
| < CLEAR:        "clear" >
| < CREATE:       "create" >
| < ADD:          "add" >
| < MOVE:         "move" >
| < COPY:         "copy" >
| < META:         "meta" >
| < SILENT:       "silent" >
| < DROP:         "drop" >
| < INTO:         "into" >
| < TO:           "to" >
| < DFT:          "default" >
//| < NAMED:        "named" >
| < ALL:          "all" >
| < WITH:         "with" >
| < USING:        "using" >

//| < BEGIN:       "begin" >
//| < COMMIT:      "commit" >
//| < ABORT:       "abort" >
}
#endif

// -------------------------------------------------

TOKEN :
{
  < #DIGITS: (["0"-"9"])+>
| < INTEGER: <DIGITS> >
//| < DECIMAL: ( <DIGITS> "." (<DIGITS>)* | "." <DIGITS> ) >
| < DECIMAL: (<DIGITS>)? "." <DIGITS> >
| < DOUBLE:   // Required exponent.
      (
        (["0"-"9"])+ "." (["0"-"9"])* <EXPONENT>
        | "." (["0"-"9"])+ (<EXPONENT>)
        | (["0"-"9"])+ <EXPONENT>
      )
      >

| < INTEGER_POSITIVE: <PLUS> <INTEGER> >
| < DECIMAL_POSITIVE: <PLUS> <DECIMAL> >
| < DOUBLE_POSITIVE:  <PLUS> <DOUBLE> >

| < INTEGER_NEGATIVE: <MINUS> <INTEGER> >
| < DECIMAL_NEGATIVE: <MINUS> <DECIMAL> >
| < DOUBLE_NEGATIVE:  <MINUS> <DOUBLE> >

| < #EXPONENT: ["e","E"] (["+","-"])? (["0"-"9"])+ >
| < #QUOTE_3D: "\"\"\"">
| < #QUOTE_3S: "'''">
| <ECHAR: "\\" ( "t"|"b"|"n"|"r"|"f"|"\\"|"\""|"'") >
| < STRING_LITERAL1: 
      // Single quoted string
      "'" ( (~["'","\\","\n","\r"]) | <ECHAR> )* "'" > 
| < STRING_LITERAL2:
    // Double quoted string
      "\"" ( (~["\"","\\","\n","\r"]) | <ECHAR> )* "\"" >
| < STRING_LITERAL_LONG1:
     <QUOTE_3S> 
      ( ("'" | "''")? (~["'","\\"] | <ECHAR> ))*
     <QUOTE_3S> >

| < STRING_LITERAL_LONG2: 
     <QUOTE_3D> 
      ( ("\"" | "\"\"")? (~["\"","\\"] | <ECHAR> ))*
     <QUOTE_3D> >
}

TOKEN :
{
  < LPAREN:    "(" >
| < RPAREN:    ")" >

// All the stuff for NUL is needed just to make a 
// single list "() ." as a triple pattern illegal.
// It leads to a lot of extra work.
// Similarly [].

| <NIL: <LPAREN> (<WSC>)* <RPAREN> >

| < LBRACE:    "{" >
| < RBRACE:    "}" >

| < LBRACKET:  "[" >
| < RBRACKET:  "]" >
| < ANON:      <LBRACKET> (<WSC>)* <RBRACKET> >

| < SEMICOLON: ";" >
| < COMMA:     "," >
| < DOT:       "." >
| < EQ:      "=" >
| < NE:      "!=" >
| < GT:      ">" >
| < LT:      "<" >
| < LE:      "<=" >    // Maybe: | "=>" >
| < GE:      ">=" >    // Maybe: | "=<" >

| < BANG:    "!" >
| < TILDE:   "~" >
| < COLON:   ":" >

| < SC_OR:   "||" >
| < SC_AND:  "&&" >

| < PLUS:    "+" >
| < MINUS:   "-" >
| < STAR:    "*" >
| < SLASH:   "/" >

//| < AMP: "&" >
//| < REM: "%" >

| < DATATYPE: "^^">
| < AT: "@">
#ifdef ARQ
| < ASSIGN:     ":=">
#endif

// Path related
| < VBAR:     "|" >
| < CARAT:    "^" >
| < FPATH:    "->" >
| < RPATH:    "<-" >
| < QMARK:    "?" >
}

// See XML chars.txt for notes

TOKEN:
{
  // XML 1.1 NCNameStartChar without "_"
  <#PN_CHARS_BASE:
          ["A"-"Z"] | ["a"-"z"] |
          ["\u00C0"-"\u00D6"] | ["\u00D8"-"\u00F6"] | ["\u00F8"-"\u02FF"] |
          ["\u0370"-"\u037D"] | ["\u037F"-"\u1FFF"] |
          ["\u200C"-"\u200D"] | ["\u2070"-"\u218F"] | ["\u2C00"-"\u2FEF"] |
          ["\u3001"-"\uD7FF"] | ["\uF900"-"\uFFFD"] 
          >
          // [#x10000-#xEFFFF]
|
  <#PN_CHARS_U: <PN_CHARS_BASE> | "_" >
|
// No DOT
  <#PN_CHARS: (<PN_CHARS_U> | "-" | ["0"-"9"] | "\u00B7" |
              ["\u0300"-"\u036F"] | ["\u203F"-"\u2040"] ) >
|
  // No leading "_", no trailing ".", can have dot inside prefix name.
  <#PN_PREFIX: <PN_CHARS_BASE> ((<PN_CHARS>|".")* <PN_CHARS>)?  >
|
  // With a leading "_", no dot at end of local name.
  <#PN_LOCAL: (<PN_CHARS_U> | ["0"-"9"]) ((<PN_CHARS>|".")* <PN_CHARS>)?  >
|
  // NCNAME without "-" and ".", allowing leading digits.
  <#VARNAME: ( <PN_CHARS_U> | ["0"-"9"] )
             ( <PN_CHARS_U> | ["0"-"9"] | "\u00B7" |
               ["\u0300"-"\u036F"] | ["\u203F"-"\u2040"] )* >
}

// Catch-all tokens.  Must be last.  
// Any non-whitespace.  Causes a parser exception, rather than a
// token manager error (with hidden line numbers).
// Only bad IRIs (e.g. spaces) now give unhelpful parse errors.
TOKEN:
{
  <#UNKNOWN: (~[" ","\t","\n","\r","\f" ])+ >
}

/*
 * (c) Copyright 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
 * (c) Copyright 2010 Talis Systems Ltd.
 * (c) Copyright 2010, 2011 Epimorphics Ltd.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name of the author may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
/*
# Local Variables:
# tab-width: 4
# indent-tabs-mode: nil
# comment-default-style: "//"
# End:
*/