# SPARQL ABNF Grammar

# The SPARQL language is defined by the Query production
Query: Prolog ( SelectQuery | ConstructQuery | DescribeQuery | AskQuery ) ;

# Reporting schemes
SelectQuery: 'SELECT' 'DISTINCT' ? ( Var + | '*' ) DatasetClause WherePattern ResultsFilter;
ConstructQuery: 'CONSTRUCT' ConstructTemplate DatasetClause WherePattern ResultsFilter;
DescribeQuery: 'DESCRIBE' ( VarOrIRIref + | '*' ) DatasetClause WherePattern ? ResultsFilter ;
AskQuery: 'ASK' DatasetClause WherePattern ? ;

# Prolog
Prolog: BaseDecl ? PrefixDecl * ;
BaseDecl: 'BASE' QuotedIRIref ;
PrefixDecl: 'PREFIX' QNAME_NS QuotedIRIref ;

# Dataset
DatasetClause: DefaultGraphClause ? NamedGraphClause * ;
DefaultGraphClause: 'FROM' SourceSelector ;
NamedGraphClause: FROM_NAMED SourceSelector ;
SourceSelector: IRIref ;

WherePattern: 'WHERE' ? GraphPattern ;
# Graph patterns
GraphPattern: EmptyPattern | OpenCurly Union CloseCurly ;
ConstructTemplate: OpenCurly SubjectStatements ( Dot SubjectStatements )* CloseCurly ;

# Results filter
ResultsFilter: OrderClause ? LimitClause ? OffsetClause ? ;
OrderClause: 'ORDER' 'BY' OrderCondition + ;
OrderCondition: ( 'ASC' | 'DESC' ) '(' Expression ')' | FunctionCall | Var | '(' Expression ')' ;
LimitClause: 'LIMIT' INTEGER ;
OffsetClause: 'OFFSET' INTEGER ;

# Binary graph operator is at highest precedence
Union: Pattern 'UNION' Union
       | Pattern ;

# Unary graph operators
Optional: 'OPTIONAL' PatternElts ;
#Optional: 'OPTIONAL' GraphPattern ;
GraphConstraint: 'GRAPH' VarOrBlankNodeOrIRIref PatternElts ;
#GraphConstraint: 'GRAPH' VarOrBlankNodeOrIRIref GraphPattern ;
PatternElts: NonSubjectPatternStarters | Filter ;

# Graph pattern restrictions:
#   need a '.' between SubjectStatements
#   can't start with Filter
Pattern: SubjectStatements AfterSubjectStatements
       | NonSubjectPatternElts AfterNotSubject ;
AfterSubjectStatements: Dot SubjectStatements AfterSubjectStatements
     | OptDot ? NonSubjectPatternElts AfterNotSubject
     | ;
AfterNotSubject: Dot ? SubjectStatements AfterSubjectStatements
     | OptDot ? NonSubjectPatternElts AfterNotSubject
     | ;
NonSubjectPatternStarters: Optional | GraphConstraint | GraphPattern ;
NonSubjectPatternElts: NonSubjectPatternStarters | Filter ;

Filter: 'FILTER' ( Expression ) ;

# Turtle/N3 ',' ';' syntax
SubjectStatements: Subject PredicateObjectList ? ;
PredicateObjectList: Predicate ObjectList ( ';' Predicate ObjectList )* ;
ObjectList: Object ('~' Object)* ;

# Turtle/N3 parts of speach
Subject: GraphNode ;
Predicate: VarOrBlankNodeOrIRIref | 'a' ;
Object: VarOrTerm | TriplesNode ;
TriplesNode: Collection | BlankNodePropertyList ;
BlankNodePropertyList: OpenSquare PredicateObjectList CloseSquare ;
Collection: '(' GraphNode+ ')' ;

# Turtle/N3 atoms plus SPARQL variables
GraphNode: VarOrTerm | TriplesNode ;
VarOrTerm: Var | GraphTerm ;
VarOrIRIref: Var | IRIref ;
VarOrBlankNodeOrIRIref: Var | BlankNode | IRIref ;
Var: VAR1 | VAR2 ;
GraphTerm: RDFTerm | '(' ')' ;

# Common expression idiom
Expression: ConditionalOrExpression ;
ConditionalOrExpression: ConditionalAndExpression ( '||' ConditionalAndExpression )* ;
ConditionalAndExpression: ValueLogical ( '&&' ValueLogical )* ;
ValueLogical: RelationalExpression ;
RelationalExpression: NumericExpression ( '=' NumericExpression | '!=' NumericExpression | '<' NumericExpression | '>' NumericExpression | '<=' NumericExpression | '>=' NumericExpression )? ;
NumericExpression: AdditiveExpression ;
AdditiveExpression: MultiplicativeExpression ( '+' MultiplicativeExpression | '-' MultiplicativeExpression )* ;
MultiplicativeExpression: UnaryExpression ( '*' UnaryExpression | '/' UnaryExpression )* ;
UnaryExpression: '!' CallExpression
| '+' CallExpression
| '-' CallExpression
| CallExpression ;


# SPARQL function calls
CallExpression: BuiltIns
| PrimaryExpression ;
BuiltIns: 'STR' '(' Expression ')'
| 'LANG' '(' Expression ')'
| 'DATATYPE' '(' Expression ')'
| 'REGEX' '(' Expression ',' String ( ',' String )? ')'
| 'BOUND' '(' Var ')'
| 'isURI' '(' Expression ')'
| 'isBLANK' '(' Expression ')'
| 'isLITERAL' '(' Expression ')'
| FunctionCall ;


# SPARQL expression atoms
PrimaryExpression: ( Var | RDFTerm | '(' Expression ')' ) ;
FunctionCall: '&' IRIref ArgList ;
ArgList: '(' ( Expression ( ',' Expression )* )? ')' ;
RDFTerm: IRIref | RDFLiteral | NumericLiteral | BooleanLiteral | BlankNode ;
NumericLiteral: INTEGER | FLOATING_POINT ;
RDFLiteral: String ( ( LANGTAG ) | ( '^^' IRIref ) )? ;
BooleanLiteral: 'true' | 'false' ;
String: STRING_LITERAL1 | STRING_LITERAL2 | STRING_LITERAL_LONG1 | STRING_LITERAL_LONG2 ;
IRIref: QuotedIRIref | QName ;
QName: QNAME | QNAME_NS ;
BlankNode: BNODE_LABEL | OpenSquare CloseSquare ;

@terminals

@pass: SPACE+
     | '#' [^\n]* "\n"
     | '/*' ( '/' [^*] | [^/*] )* '*/' ;

# SPARQL look-ahead lexing requirements
EmptyPattern: '{' SPACE* '}' ;
Dot: '.' ;
OptDot: '.' / ( SPACE* ( ( 'UNION'|'OPTIONAL'|'GRAPH'|'FILTER' ) [^a-z] |'{') ) ;
OpenCurly: '{' ;
CloseCurly: SPACE* ';'? SPACE* '.'? SPACE* '}' ;
OpenSquare: '[' ;
CloseSquare: SPACE* ';'? SPACE* ']' ;
FROM_NAMED: "FROM" SPACE+ "NAMED" ;

# URIs
QuotedIRIref: '<' ([^> ])* '>' ;
QNAME_NS: NCNAME_PREFIX? ':' ;
QNAME: NCNAME_PREFIX? ':' NCNAME? ;
BNODE_LABEL: '_:' NCNAME ;

# SPARQL variables
VAR1: '?' VARNAME ;
VAR2: '$' VARNAME ;

# Numbers
INTEGER: [0-9]+ ;
DECIMAL: [0-9]+ '.' [0-9]* | '.' [0-9]+ ;
FLOATING_POINT: [0-9]+ '.' [0-9]* EXPONENT? | '.' ([0-9])+ EXPONENT? | ([0-9])+ EXPONENT ;
EXPONENT: [eE] [+-]? [0-9]+ ;

# Strings
STRING_LITERAL1: "'" ( ([^'\\\n\r]) | ('\\' [^\n\r]) )* "'" ;
STRING_LITERAL2: '"' ( ([^"\\\n\r]) | ('\\' [^\n\r]) )* '"' ;
STRING_LITERAL_LONG1: '"""' ( [^"\\] | ("\\" [^\n\r]) | ('"' [^"]) | ('""' [^"]) )* '"""' ;
STRING_LITERAL_LONG2: "'''" ( [^'\\] | ("\\" [^\n\r]) | ("'" [^']) | ("''" [^']) )* "'''" ;
LANGTAG: '@' [a-zA-Z]+ ('-' [a-zA-Z0-9]+)* ;

# XML NameChars
NCCHAR1: [A-Z]
| [a-z]
| [#x00C0-#x00D6]
| [#x00D8-#x00F6]
| [#x00F8-#x02FF]
| [#x0370-#x037D]
| [#x037F-#x1FFF]
| [#x200C-#x200D]
| [#x2070-#x218F]
| [#x2C00-#x2FEF]
| [#x3001-#xD7FF]
| [#xF900-#xFFFE] ;
NCCHAR: NCCHAR1 | '_' | '-' | "." | [0-9] | #x00B7 ;
NCNAME_PREFIX: NCCHAR1 NCCHAR* ;
NCNAME: ( "_" | NCCHAR1 ) NCCHAR* ;
VARNAME: ( NCCHAR1 | "_" | [0-9] | #x00B7 )* ;

SPACE: #x0009
| #x000A
| #x000D
| #x0020
| #x00A0
| [#x2000-#x200B]
| #x202F
| #x205F
| #x3000 ;