Link Search Menu Expand Document
Specifications PyCSP3 Tools Instances Competitions About

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"