Syntax
The syntax given in this document combines two languages:
- XML for describing the main elements and attributes of XCSP3 (high level description)
- BNF for describing the textual contents of XCSP3 elements and attributes (low level description)
In many situations, the content of an XML text-only element corresponds to a list of basic data (values, variables, …) with whitespace as separator. In such situations, the whitespace that follows the last object of the list must always be considered as optional. More generally, the following rule applies for XCSP3: In XCSP3, leading and trailing whitespace are tolerated, but not required, in any XML text-only element.
We use a variant of Backus-Naur Form (BNF) defined as follows:
- a non-terminal definition is preceded by ::=
- terminals are between quotation marks as e.g., "CSP"
- non-terminals are composed of alphanumeric characters (and the character "_"), and so, do not contain any white space character, as e.g., frameworkType. When such non-terminals are mixed with XML notation (in the pdf document), they are written in dark blue italic form
- concatenation is given by any non-empty sequence of white space characters
- alternatives are separated by a vertical bar as, e.g., "+" | "-"
- square brackets are used for surrounding optional elements, as, e.g., ["+" | "-"]
- an element followed by * can occur 0 or any number of times
- an element followed by + must occur at least 1 time
- an element followed by n+ must occur at least n times
- parentheses are used for grouping (often used with *, + and n+)
The syntax is given for fully expanded XCSP3 code, meaning that compact lists of array variables (such as x[]) are not handled.
The basic BNF non-terminals are:
Syntax
wspace ::= (" " | "\t" | "\n" | "\r")+
digit ::= "0".."9"
unsignedInteger ::= digit+
integer ::= ["+" | "-"] unsignedInteger
decimal ::= integer "." unsignedInteger
rational ::= integer "/" unsignedInteger
number ::= integer | decimal | rational
boolean ::= "false" | "true"
intSet ::= "set(" [integer ("," integer)*] ")"
letter ::= "a".."z" | "A".."Z"
identifier ::= letter (letter | digit | "_" )*
The basic data type are (note that we include many aliases so as to facilitate readability):
Syntax
indexing ::= ("[" unsignedInteger "]")+
variable ::= identifier [indexing]
01Var ::= variable
intVar ::= variable
symVar ::= variable
realVar ::= variable
setVar ::= variable
graphVar ::= variable
qualVar ::= variable
intVal ::= integer
realVal ::= number
intIntvl ::= (integer | "-infinity") ".." (integer | "+infinity")
realIntvl ::= ("]" | "[") (number | "-infinity") ","
(number | "+infinity") ("]" | "[")
setVal ::= "{" [integer ("," integer)*] "}"
proba ::=
unsignedInteger "." unsignedInteger
| unsignedInteger "/" unsignedInteger
| 0 | 1
operator ::= "lt" | "le" | "ge" | "gt" | "ne" | "eq" | "in" | "notin"
operand ::= intVal | intVar | intIntvl | intSet
tuplePiece ::= intVal | "*" | setVal
state ::= identifier
symbol ::= identifier
intCtr ::= identifier
dimensions ::= indexing
Some types are defined as:
Syntax
frameworkType ::=
"CSP" | "COP" | "WCSP" | "FCSP" | "QCSP" | "QCSP+" | "QCOP" | "QCOP+"
| "SCSP" | "SCOP" | "QSTR" | "TCSP"
| "NCSP" | "NCOP" | "DisCSP" | "DisWCSP"
varType ::=
"integer" | "symbolic" | "real" | "set" | "symbolic set"
| "undirected graph" | "directed graph" | "stochastic"
| "symbolic stochastic" | "point" | "interval" | "region"
orderedType ::= "increasing" | "strictlyIncreasing" | "decreasing" | "strictlyDecreasing"
rankType ::= "any" | "first" | "last"
iaBaseRelation ::= "eq" | "p" | "pi" | "m" | "mi" | "o" | "oi" | "s" | "si" | "d" | "di" | "f" | "fi"
paBaseRelation ::= "b" | "eq" | "a"
rcc8BaseRelation ::= "dc" | "ec" | "eq" | "po" | "tpp" | "tppi" | "nttp" | "nttpi"
measureType ::= "var" | "dec" | "val" | "edit"
combinationType ::= "lexico" | "pareto"
blockType ::= "clues" | "symmetryBreaking" | "redundantConstraints" | "nogoods"
varhType ::=
"lexico" | "dom" | "deg" | "ddeg" | "wdeg" | "immpact" | "activity"
| varhType "/" varhType
| varhType "+" varhType
valhType ::= "conflicts" | "value"
filteringType ::= "boundsZ" | "boundsD" | "boundsR" | "AC" | "FC"
consistencyType ::= "FC" | "BC" | "AC" | "SAC" | "FPWC" | "PC" | "CDC" | "FDAC" | "EDAC" | "VAC"
branchingType ::= "2-way" | "d-way"
restartsType ::= "luby" | "geometric"
The grammar used to build predicate expressions with integer variables is:
Syntax
intExpr ::=
01Var | intVar | integer
| "neg(" intExpr ")"
| "abs(" intExpr ")
| "add(" intExpr ("," intExpr)+ ")"
| "sub(" intExpr "," intExpr ")"
| "mul(" intExpr ("," intExpr)+ ")"
| "div(" intExpr "," intExpr ")"
| "mod(" intExpr "," intExpr ")"
| "sqr(" intExpr ")"
| "pow(" intExpr "," intExpr ")"
| "min(" intExpr ("," intExpr)+ ")"
| "max(" intExpr ("," intExpr)+ ")"
| "dist(" intExpr "," intExpr ")"
| "if(" boolExpr "," intExpr "," intExpr ")"
boolExpr ::=
01Var
| "lt(" intExpr "," intExpr ")"
| "le(" intExpr "," intExpr ")"
| "ge(" intExpr "," intExpr ")"
| "gt(" intExpr "," intExpr ")"
| "ne(" intExpr "," intExpr ")"
| "eq(" intExpr ("," intExpr)+ ")"
| "in(" intExpr "," intSet ")"
| "not(" boolExpr ")"
| "and(" boolExpr ("," boolExpr)+ ")"
| "or(" boolExpr ("," boolExpr)+ ")"
| "xor(" boolExpr ("," boolExpr)+ ")"
| "iff(" boolExpr ("," boolExpr)+ ")"
| "imp(" boolExpr "," boolExpr ")"
The grammar used to build predicate expressions with integer variables and set variables is:
Syntax
intExprSet ::=
01Var | intVar | integer
| "neg(" intExprSet ")"
| "abs(" intExprSet ")
| "add(" intExprSet ("," intExprSet)+ ")"
| "sub(" intExprSet "," intExprSet ")"
| "mul(" intExprSet ("," intExprSet)+ ")"
| "div(" intExprSet "," intExprSet ")"
| "mod(" intExprSet "," intExprSet ")"
| "sqr(" intExprSet ")"
| "pow(" intExprSet "," intExprSet ")"
| "min(" intExprSet ("," intExprSet)+ ")"
| "max(" intExprSet ("," intExprSet)+ ")"
| "dist(" intExprSet "," intExprSet ")"
| "if(" boolExprSet "," intExprSet "," intExprSet ")"
| "card(" setExpr ")"
| "min(" setExpr ")"
| "max(" setExpr ")"
setExpr ::=
setVar | "set(" [intExprSet ("," intExprSet)*] ")"
| "union(" setExpr ("," setExpr)+ ")"
| "inter(" setExpr ("," setExpr)+ ")"
| "diff(" setExpr "," setExpr ")"
| "sdiff(" setExpr ("," setExpr)+ ")"
| "hull(" setExpr ")"
boolExprSet ::=
01Var
| "lt(" intExprSet "," intExprSet ")"
| "le(" intExprSet "," intExprSet ")"
| "ge(" intExprSet "," intExprSet ")"
| "gt(" intExprSet "," intExprSet ")"
| "ne(" intExprSet "," intExprSet ")"
| "eq(" intExprSet ("," intExprSet)+ ")"
| "in(" intExprSet "," setExpr ")"
| "ne(" setExpr "," setExpr ")"
| "eq(" setExpr ("," setExpr)+ ")"
| "not(" boolExprSet ")"
| "and(" boolExprSet ("," boolExprSet)+ ")"
| "or(" boolExprSet ("," boolExprSet)+ ")"
| "xor(" boolExprSet ("," boolExprSet)+ ")"
| "iff(" boolExprSet ("," boolExprSet)+ ")"
| "imp(" boolExprSet "," boolExprSet ")"
| "djoint(" setExpr "," setExpr ")"
| "subset(" setExpr "," setExpr ")"
| "subseq(" setExpr "," setExpr ")"
| "supseq(" setExpr "," setExpr ")"
| "supset(" setExpr "," setExpr ")"
| "convex(" setExpr ")"
The grammar used to build predicate expressions with integer variables and real variables is:
Syntax
realExpr ::=
01Var | intVar | realVar | number | PI | E
| "neg(" realExpr ")"
| "abs(" realExpr ")
| "add(" realExpr ("," realExpr)+ ")"
| "sub(" realExpr "," realExpr ")"
| "mul(" realExpr ("," realExpr)+ ")"
| "fdiv(" realExpr "," realExpr ")"
| "fmod(" realExpr "," realExpr ")"
| "min(" realExpr ("," realExpr)+ ")"
| "max(" realExpr ("," realExpr)+ ")"
| "sqr(" realExpr ")"
| "pow(" realExpr "," realExpr ")"
| "sqrt(" realExpr ")"
| "nroot(" realExpr "," integer ")"
| "exp(" realExpr ")"
| "ln(" realExpr ")"
| "log(" realExpr "," integer ")"
| "sin(" realExpr ")"
| "cos(" realExpr ")"
| "tan(" realExpr ")"
| "asin(" realExpr ")"
| "acos(" realExpr ")"
| "atan(" realExpr ")"
| "sinh(" realExpr ")"
| "cosh(" realExpr ")"
| "tanh(" realExpr ")"
| "if(" boolExprReal "," realExpr "," realExpr ")"
boolExprReal ::=
01Var
| "lt(" realExpr "," realExpr ")"
| "le(" realExpr "," realExpr ")"
| "ge(" realExpr "," realExpr ")"
| "gt(" realExpr "," realExpr ")"
| "ne(" realExpr "," realExpr ")"
| "eq(" realExpr ("," realExpr)+ ")"
| "not(" boolExprReal ")"
| "and(" boolExprReal ("," boolExprReal)+ ")"
| "or(" boolExprReal ("," boolExprReal)+ ")"
| "xor(" boolExprReal ("," boolExprReal)+ ")"
| "iff(" boolExprReal ("," boolExprReal)+ ")"
| "imp(" boolExprReal "," boolExprReal ")"
Finally, we need some non-terminal tokens to be used for XML elements.
Syntax
constraint ::=
"extension" | "intension"
| "regular" | "grammar" | "mdd"
| "allDifferent" | "allEqual" | "allDistant" | "ordered" | "allIncomparable"
| "sum" | "count" | "nValues" | "cardinality" | "balance" | "spread" | "deviation" |
"sumCosts" | "sequence"
| "maximum" | "minimum" | "element" | "channel" | "permutation" | "precedence"
| "stretch" | "noOverlap" | "cumulative" | "binPacking" | "knapsack" | "networkFlow"
| "circuit" | "nCircuits" | "path" | "nPaths" | "tree" | "nTrees"
| "clause" | "instantiation"
| "allIntersecting" | "range" | "roots" | "partition"
| "arbo" | "nArbos" | "nCliques"
metaConstraint ::=
"slide" | "seqbin" | "and" | "or" | "not"