IL syntax - Manual of the XDG Development Kit

Next: SL syntax, Previous: XML syntax, Up: Compiler

4.12 IL syntax

In this section, we describe the syntax of Intermediate Language (IL) grammar files. The IL is a record language in Mozart-Oz syntax. It is designed specifically to be dealt with easily in Mozart-Oz.

We describe the syntax of the IL in a notation similar to the Extended Backus Naur Form (EBNF). We use the record syntax of Mozart-Oz, where records look like this:

     <constant>(<constant_1>:<value_1>
                ...
                <constant_n>:<value_n>)

where <constant> is the record name, and <constant_i>:<value_i> is a feature with field <constant_i> and value <value_i> (1<=i<=n).

4.12.1 Descriptions

We write down the syntax of the IL as a mapping from description identifiers to descriptions. This mapping is written as a Mozart-Oz record as follows:

     o(<description id_1>:<description_1>
       ...
       <description id_n>:<description_n>)

A description can be one of the following:

tuple of n descriptions: <description_1>#...#<description_n>
list of descriptions: '*'(<description>) (if such a description is not given, the empty list is assumed)
optional description: '?'(<description>) (if such a description is not given, a default depending on the description is assumed)
a reference to a description identifier: <description_id>

a disjunction of n descriptions:

          disj(<description_1>
               ...
               <description_n>)

a complex description (an element):

          elem(tag: <constant>
               <constant_1>: <description_1>
               ...
               <constant_n>: <description_n>)

a simple description, i.e. either:
- an atom defining a unique identifier: 'ID'
- an atom referring to a unique identifier: 'IDREF'
- character data: 'CDATA'
- an atom: 'ATOM'
- an integer: 'INT'

We use single quotes to escape Mozart-Oz keywords (e.g. functor), tokens starting with an upper case letter (Mozart-Oz variables), and tokens containing dots (e.g. 'principle.tree').

4.12.2 Syntax checker

The XDK includes the Mozart-Oz functor Compiler/SyntaxChecker.ozf whose exported procedure Check can be used to check whether an file fulfills its syntax specifications. The IL syntax specification is in the functor Compiler/ILSyntax.ozf. The file Compiler/SyntaxCheckerTest.oz, which can be fed in the Oz Programming Interface (OPI), demonstrates how to use the syntax checker to check whether the output of the UL and XML language frontends are syntactically correct.

The syntax checker will be useful if you decide to design a new grammar file input language in addition to the UL and the XML language.

4.12.3 Start symbol ('S')

We continue with giving an overview of the syntax of the IL. The start symbol of the IL syntax is 'S':

     'S': 'GRAMMAR'

4.12.4 Grammar definition ('GRAMMAR')

A grammar definition has tag grammar:

     'GRAMMAR': elem(tag: grammar
                     principles: '*'('PRINCIPLEDEF')
                     outputs: '*'('OUTPUTDEF')
                     usedimensions: '*'('CONSTANT')
                     dimensions: '*'('DIMENSION')
                     classes: '*'('CLASSDEF')
                     entries: '*'('ENTRY'))

The principles feature corresponds to a list of principle definitions ('*'('PRINCIPLEDEF')).

The outputs feature corresponds to a list of output definitions ('*'('OUTPUTDEF')).

The usedimensions feature corresponds to a list of constants which represent the identifiers of the used dimensions ('*'('CONSTANT')).

The dimensions feature corresponds to a list of dimension definitions ('*'('DIMENSION')).

The classes feature corresponds to a list of class definitions ('*'('CLASSDEF')).

The entries feature corresponds to a list of lexical entries ('*'('ENTRY')).

4.12.5 Principle definitions ('PRINCIPLEDEF')

A principle definition has tag principledef. Notice that principle definitions can only be written in the IL since they are closed for the user. They cannot be written in the UL or the XML language:

     'PRINCIPLEDEF': elem(tag: principledef
                          id: 'CONSTANT'
                          dimensions: '*'('VARIABLE')
                          args: '*'('VARIABLE'#'TYPE')
                          defaults: '*'('VARIABLE'#'TERM')
                          node: '?'('TYPE')
                          constraints: '*'('CONSTANT'#'INTEGER'))

The id feature corresponds to the principle identifier ('CONSTANT').

The dimensions feature corresponds to a list of dimension variables ('*'('VARIABLE')), the dimension variables which are introduced by the principle.

The args feature corresponds to a list of pairs of argument variables and their types ('*'('VARIABLE'#'TYPE')).

The defaults feature corresponds to a list of pairs of argument variables and their default values ('*'('VARIABLE'#'TERM')).

The node feature corresponds to an optional model record type '?'('TYPE'). If this feature is not given, the empty record is assumed.

The constraints feature corresponds to a list of pairs of constraint names and their priorities ('*'('CONSTANT'#'INTEGER')).

4.12.6 Output definitions

An output definition has tag outputdef. Notice that output definitions can only be written in the IL since they are closed for the user. They cannot be written in the UL or the XML language.

     'OUTPUTDEF': elem(tag: outputdef
                       id: 'CONSTANT'
                       'functor': 'CONSTANT')

The id feature corresponds to the output identifier ('CONSTANT').

The 'functor' feature corresponds to the functor name of the output ('CONSTANT').

4.12.7 Dimension definitions ('DIMENSION')

A dimension definition has tag dimension:

     'DIMENSION': elem(tag: dimension
                       id: 'CONSTANT'
                       attrs: '?'('TYPE')
                       entry: '?'('TYPE')
                       label: '?'('TYPE')
                       types: '*'('TYPEDEF')
                       principles: '*'('USEPRINCIPLE')
                       outputs: '*'('OUTPUT')
                       useoutputs: '*'('USEOUTPUT'))

The id feature corresponds to the dimension identifier ('CONSTANT').

The attrs feature corresponds to an optional attributes type ('?'('TYPE')). The default for this description is the empty record.

The entry feature corresponds to an optional entry type ('?'('TYPE')). The default for this description is the empty record.

The label feature corresponds to an optional label type ('?'('TYPE')). The default for this description is the empty domain.

The types feature corresponds to a list of type definitions ('*'('TYPEDEF')).

The principles feature corresponds to a list of principle uses ('*'('USEPRINCIPLE')).

The outputs feature corresponds to a list of chosen outputs ('*'('OUTPUT')).

The useoutputs feature corresponds to a list of used outputs ('*'('USEOUTPUT')).

4.12.8 Output chooses ('OUTPUT')

An output chooses has tag output:

     'OUTPUT': elem(tag: output
                    idref: 'CONSTANT')

The idref feature corresponds to the chosen output identifier ('CONSTANT').

4.12.9 Output uses ('USEOUTPUT')

An output choosing has tag useoutput:

     'USEOUTPUT': elem(tag: useoutput
                       idref: 'CONSTANT')

The idref feature corresponds to the used output identifier ('CONSTANT').

4.12.10 Type definitions ('TYPEDEF')

A type definition has tag typedef:

     'TYPEDEF': elem(tag: typedef
                     id: 'CONSTANT'
                     type: 'TYPE')

The id feature corresponds to the type identifier ('CONSTANT').

The type feature corresponds to the type ('TYPE').

4.12.11 Types ('TYPE')

The description identifier 'TYPE' corresponds to the following:

     'TYPE': disj(elem(tag: 'type.domain'
                       args: '*'('CONSTANT'))
                  elem(tag: 'type.set'
                       arg: 'TYPE')
                  elem(tag: 'type.iset'
                       arg: 'TYPE')
                  elem(tag: 'type.tuple'
                       args: '*'('TYPE'))
                  elem(tag: 'type.list'
                       arg: 'TYPE')
                  elem(tag: 'type.record'
                       args: '*'('CONSTANT'#'TYPE'))
                  elem(tag: 'type.valency'
                       arg: 'TYPE')
                  elem(tag: 'type.card')
                  elem(tag: 'type.vec'
                       arg1: 'TYPE'
                       arg2: 'TYPE')
                  elem(tag: 'type.int')
                  elem(tag: 'type.ints')
                  elem(tag: 'type.string')
                  elem(tag: 'type.bool')
                  elem(tag: 'type.ref'
                       idref: 'CONSTANT')
                  elem(tag: 'type.labelref'
                       arg: 'VARIABLE')
                  elem(tag: 'type.variable'
                       data: 'ATOM'))

4.12.11.1 Domain types ('type.domain')

A domain type has tag 'type.domain'. The args feature corresponds to the set of constants in the domain ('*'('CONSTANT')).

4.12.11.2 Accumulative set types ('type.set')

An accumulative set type has tag 'type.set'. The arg feature corresponds to the type of the domain of the set ('TYPE').

4.12.11.3 Intersective set types ('type.iset')

An intersective set type has tag 'type.iset'. The arg feature corresponds to the type of the domain of the set ('TYPE').

4.12.11.4 Tuple types ('type.tuple')

A tuple type has tag 'type.tuple'. The args feature corresponds to the types of the projections of the tuple ('*'('TYPE')).

4.12.11.5 List types ('type.list')

A list type has tag 'type.record'. The arg feature corresponds to the type of the domain of the list ('TYPE').

4.12.11.6 Record types ('type.record')

A record type has tag 'type.list'. The args feature corresponds to a list of pairs of the record fields and their types ('*'('CONSTANT'#'TYPE')).

4.12.11.7 Valency types ('type.valency')

A valency type has tag 'type.valency'. The arg feature corresponds to the type of the domain of the valency ('TYPE').

4.12.11.8 Vector types ('type.vec')

A vector type has tag 'type.vec'. The arg1 feature corresponds to the domain of the fields of the vector ('TYPE'), and the arg2 feature to the type of the values ('TYPE').

4.12.11.9 Integer types ('type.int')

An integer type has tag 'type.int'.

4.12.11.10 Set of integers types ('type.ints')

A set of integers type has tag 'type.ints'.

4.12.11.11 String types ('type.string')

A string type has tag 'type.string'.

4.12.11.12 Bool types ('type.bool')

A boolean type has tag 'type.bool'.

4.12.11.13 Type reference types ('type.ref')

A type reference has tag 'type.ref'. The idref feature corresponds to the identifier of the referenced type ('CONSTANT').

4.12.11.14 Label reference types ('type.labelref')

A label reference has tag 'type.labelref'. The arg feature corresponds to the dimension variable whose set of edge labels is referenced ('VARIABLE').

4.12.11.15 Type variable ('type.variable')

A type variable has tag 'type.variable'.

4.12.12 Principle uses ('USEPRINCIPLE')

A principle use has tag useprinciple:

     'USEPRINCIPLE': elem(tag: useprinciple
                          idref: 'CONSTANT'
                          dimensions: '*'('VARIABLE'#'CONSTANT')
                          args: '*'('VARIABLE'#'TERM'))

The idref feature corresponds to the principle identifier of the used principle ('CONSTANT').

The dimensions feature corresponds to the dimension mapping, a list of pairs of dimension variables and dimension identifiers ('*'('VARIABLE'#'CONSTANT')).

The args feature corresponds to the argument mapping, a list of pairs of argument variables and their values ('*'('VARIABLE'#'TERM')).

4.12.13 Class definitions ('CLASSDEF')

A class definition has tag classdef:

     'CLASSDEF': elem(tag: classdef
                      id: 'CONSTANT'
                      vars: '*'('VARIABLE')
                      body: 'CLASS')

The id feature corresponds to the class identifier ('CONSTANT').

The vars feature corresponds to the list of variables which are bound by the class ('*'('VARIABLE')).

The body feature corresponds to the class body ('CLASS').

4.12.14 Class bodies ('CLASS')

The description identifier 'CLASS' corresponds to the following:

     'CLASS': disj(elem(tag: 'class.dimension'
                        idref: 'CONSTANT'
                        arg: 'TERM')
                    elem(tag: 'class.ref'
                         idref: 'CONSTANT'
                         args: '*'('VARIABLE'#'TERM'))
                    elem(tag: conj
                         args: '*'('CLASS'))
                    elem(tag: disj
                         args: '*'('CLASS')))

4.12.14.1 Entry dimension ('class.dimension')

An entry dimension has tag 'class.dimension'. The idref feature corresponds to the dimension identifier ('CONSTANT'), and the arg feature corresponds to the entry dimension itself ('TERM').

4.12.14.2 Class reference ('class.ref')

A class reference has tag 'class.ref'. The idref feature corresponds to the class identifier of the referenced class. The args feature corresponds to the list of pairs of variables and values that specify the variable binding of the class reference ('*'('VARIABLE'#'TERM')).

4.12.14.3 Conjunction (conj)

A conjunction of class bodies has tag conj. The args feature corresponds to the list of class bodies which are combined by conjunction ('*'('CLASS')).

4.12.14.4 Disjunction (disj)

A disjunction of class bodies has tag disj. The args feature corresponds to the list of class bodies which are combined by disjunction ('*'('CLASS')).

4.12.15 Lexical entries ('ENTRY')

A lexical entry has tag entry.

     'ENTRY': elem(tag: entry
                   body: 'CLASS')

The body feature corresponds to the class body which specifies the lexical entry ('CLASS').

4.12.16 Terms ('TERM')

The description identifier 'TERM' corresponds to the following:

     'TERM': disj('CONSTANT'
                  'VARIABLE'
                  'INTEGER'
                  'CARD'
                  'CONSTANT'#'CARD'
                  'VARIABLE'#'CARD'
                  elem(tag: top)
                  elem(tag: bot)
                  elem(tag: set
                       args: '*'('TERM'))
                  elem(tag: list
                       args: '*'('TERM'))
                  elem(tag: record
                       args: '*'('RECSPEC'))
                  elem(tag: setgen
                       arg: 'SETGEN')
                  elem(tag: featurepath
                       root: 'ROOT'
                       dimension: 'VARIABLE'
                       aspect: 'ASPECT'
                       fields: '*'('CONSTANT'))
                  elem(tag: annotation
                       arg1: 'TERM'
                       arg2: 'TYPE')
                  elem(tag: conj
                       args: '*'('TERM'))
                  elem(tag: disj
                       args: '*'('TERM'))
                  elem(tag: concat
                       args: '*'('TERM'))
                  elem(tag: order
                       args: '*'('TERM')))
     
     'ROOT': disj('_' '^')
     'ASPECT': disj('entry' 'attrs')

4.12.16.1 Constants ('CONSTANT')

A constant has tag constant:

     'CONSTANT': elem(tag: constant
                      data: 'ATOM')

The data feature corresponds to the constant itself.

4.12.16.2 Variables ('VARIABLE')

A variable has tag variable.

     'VARIABLE': elem(tag: variable
                      data: 'ATOM')

The data feature corresponds to the variable itself.

4.12.16.3 Integers ('INTEGER')

An integer has tag integer.

     'INTEGER': disj(elem(tag: integer
                          data: 'INT')
                     elem(tag: integer
                          data: 'infty'))

An integer is either an integer or infinity.

The data feature of an integer corresponds to the integer itself or to the special constant infty (for “infinity”).

4.12.16.4 Cardinality sets ('CARD')

The description identifier CARD corresponds to the following:

     'CARD': disj(elem(tag: 'card.wild'
                       arg: 'WILD')
                  elem(tag: 'card.set'
                       args: '*'('INTEGER'))
                  elem(tag: 'card.interval'
                       arg1: 'INTEGER'
                       arg2: 'INTEGER'))
     
     'WILD': disj('!' '?' '*' '+')

A wild card cardinality set has tag 'card.wild'. The arg feature corresponds to one of the wild cards '!', '?', '*', or '+'.

A cardinality set has tag 'card.set'. The args feature corresponds to a list of integers which specify the set ('*'('INTEGER')).

A cardinality interval has tag 'card.interval'. The arg1 feature corresponds to the left endpoint of the closed interval ('INTEGER'), and the arg2 feature to the right endpoint ('INTEGER').

4.12.16.5 Cardinality specifications (`'CONSTANT'#'CARD'` or `'VARIABLE'#'CARD'`)

Cardinality specifications have the syntax 'CONSTANT'#'CARD', or 'VARIABLE'#'CARD'.

4.12.16.6 Top values (`top`)

Top values have tag top.

4.12.16.7 Bottom values (`bot`)

Bottom values have tag bot.

4.12.16.8 Sets (`set`)

Sets have tag set. The args feature corresponds to the set elements ('*'('TERM')).

4.12.16.9 Lists (`list`)

Lists have tag list. The args feature corresponds to the list elements ('*'('TERM')).

4.12.16.10 Records (`record`)

Records have tag record. The args feature corresponds to the list of record specifications for this record '*'('RECSPEC').

A record specification (description identifier 'RECSPEC') has the following syntax:

     'RECSPEC': disj('CONSTANT'#'TERM'
                     'VARIABLE'#'TERM'
                     elem(tag: conj
                          args: '*'('RECSPEC'))
                     elem(tag: disj
                          args: '*'('RECSPEC')))

I.e. a record specification is either a pair of a field and a value ('CONSTANT'#'TERM'), of a variable and a value ('VARIABLE'#'TERM'), or a conjunction of record specifications (tag: conj), or a disjunction of record specifications (tag: disj).

4.12.16.11 Set generator expressions (`setgen`)

A set generator expression has tag setgen. The arg feature is the set generator expression body (description identifier 'SETGEN'):

     'SETGEN': disj('CONSTANT'
                    elem(tag: conj
                         args: '*'('SETGEN'))
                    elem(tag: disj
                         args: '*'('SETGEN')))

I.e. a set generator expression body is either a constant, or a conjunction of set generator expression bodies (tag: conj), or a disjunction of set generator expression bodies (tag: disj).

4.12.16.12 Feature paths (`featurepath`)

A feature path has tag featurepath.

The root feature corresponds to the root variable of the feature path, either '_' or '^'.

The dimension feature corresponds to the dimension variable of the feature path ('VARIABLE').

The aspect feature corresponds to the aspect of the feature path, either 'entry' or 'attrs'.

The fields feature corresponds to the fields of the feature path ('*'('CONSTANT')).

4.12.16.13 Type annotations (`annotation`)

A type annotation has tag annotation.

The arg1 feature corresponds to the term ('TERM'), and the arg2 feature to the annotated type ('TYPE').

4.12.16.14 Conjunction (`conj`)

A conjunction has tag conj.

The args feature corresponds to the list of terms which are combined by conjunction.

4.12.16.15 Disjunction (`disj`)

A disjunction has tag disj.

The args feature corresponds to the list of terms which are combined by disjunction.

4.12.16.16 Concatenation (`concat`)

A concatenation has tag concat.

The args feature corresponds to the list of terms which are to be concatenated. Concatenation is restricted to strings.

4.12.16.17 Order (`order`)

An order generator has tag order.

The args feature corresponds to the list of terms from which a set of pairs representing an order relation is generated.

4.12.17 Undetermined values

The XDK solver can also yield partial solutions in which not all values in the node record are determined; instead some of the values are still variables. In the following, we show how these variables are represented in the IL.

4.12.17.1 Undetermined cardinality sets

This is the IL syntax for undetermined cardinality sets (i.e. cardinality set variables) in valencies:

     elem(tag: '_'
          args: [IL1 IL2])

IL1 is the cardinality set representing the set of integers which are already known to be in the cardinality set variable.

IL2 is the cardinality set representing the set of integers which can still be bound to the cardinality set variable.

4.12.17.2 Undetermined constants

This is the IL syntax for undetermined constants (i.e. constant variables):

     elem(tag: '_'
          args: [DSpec])

DSpec is a domain specification¹, representing the set of constants which can still be bound to the constant variable.

4.12.17.3 Undetermined integers

This is the IL syntax for undetermined integers (i.e. integer variables):

     elem(tag: '_'
          args: [DSpec])

DSpec is a domain specification representing the set of integers which can still be bound to the integer variable.

4.12.17.4 Undetermined lists

This is the IL syntax for undetermined lists (i.e. list variables):

     elem(tag: '_'
          args: nil)

4.12.17.5 Undetermined sets

The IL syntax for undetermined sets (i.e. set variables) differs depending on the domain of the set:

a finite domain of constants or a tuple of which all projections are finite domains of constants
any other type

The IL syntax for undetermined sets whose domain is either a finite domain of constants or a tuple of which all projections are finite domains of constants is given below:
```
          elem(tag: '_'
               args: [MSpec1 MSpec2 DSpec])
     
```
MSpec1 is a set specification representing the set of constants which are already known to be in the set variable.
MSpec2 is a set specification representing the set of constants which could still end up in the set variable.
DSpec is a domain specification representing the set of integers which can still be bound to the integer variable representing the cardinality of the set variable.
The IL syntax for undetermined sets over any other domain is given below:
```
          elem(tag: '_'
               args: nil)
     
```

4.12.17.6 Undetermined strings

This is the IL syntax for undetermined strings (i.e. string variables):

     elem(tag: '_'
          args: nil)

4.12.17.7 Undetermined tuples

The IL syntax for undetermined tuples (i.e. tuple variables) differs depending on the types of the projections of the tuple:

all projections are finite domains of constants
any of the projections has a type other than finite domain of constants

This is the IL syntax for undetermined tuples of which all projections are finite domains of constants:
```
          elem(tag: '_'
               args: [DSpec])
     
```
DSpec is a domain specification representing the set of tuples which can still be bound to the tuple variable.
This is the IL syntax for undetermined tuples of which any of the projections has a type other than finite domain of constants:
```
          elem(tag: '_'
               args: nil)
     
```

Footnotes

[1] A domain specification can be a list of values (or pairs of values), or just a value (or a pair of values) describing the domain. Pairs of values denote closed intervals within the set.