# GRS syntax

## Global structure

A GRS is composed by a set of declarations that may be provided in several files.
These files are expected to used the `.grs`

or the `.dom`

file extension.

Five kinds of declarations can be used:

**Feature domain**declarations (keyword`features`

)**Label domain**declarations (keyword`labels`

)**Rule**declaration (keyword`rule`

)**Strategy**declaration (keyword`strategy`

)**Package**declaration (keyword`package`

)

The first two kinds (Feature domain and label domain) can only be used at the top level and they cannot be nested (see below the multi-file handling).

## Feature domains

In graphs and in rules, nodes contain feature structures. To control these feature structures, a feature domain may be given first. In the feature domain declaration, feature names are identifiers and are defined as:

**closed**feature accepts only an explicit given set of possible values (like the cat feature value below);**open**feature name accepts any string value (like the lemma feature value below);**numerical**feature (like the position feature below).

In closed features definition, feature values can be any strings; double quotes are required for string that are not lexical identifier (like values for pers).

❓ Explain merging of two feature domain declarations.

```
features {
cat: n, np, v, adj;
mood: inf, ind, subj, pastp, presp;
lemma: STRING;
phon: STRING;
pers: "1","2","3";
position: NUMERIC;
}
```

**REM:** values of pers feature are numerals but the only way to restrict to the finite domain {1, 2, 3} is to declare it as a closed feature and possible values as strings.

## Label domains

An explicit set of valid labels for edges may be given after the `labels`

keyword.
It is possible to give several label domain declarations; the union of the different sets is then considered (❓ what about duplicates?, see #4).

By default, edges are drawn with a black solid line and above the figure in DEP representation.

To modify the color or the position of the edges, the user can add attributes to a label with suffixes:

`@bottom`

to put the label above`@red`

,`@blue`

, … to modify the color of the link and the label`@dot`

or`@dash`

to modify the style of the link

Several suffixes can be used simultaneously.

```
labels { OBJ, SUJ, DE_OBJ, ANT, ANT_REL@red, ANT_REP@blue@bottom@dash }
```

⚠️ the color, style and position management will change soon (see #5)

## Rules

Rule declaration is introduced by the keyword `rule`

. For the syntax, see rule page.

## Strategies

Strategies are used specify the way rules are applied during transformation. The syntax of strategies definition is:

```
strat strat_id {
<<< strategy_description >>>
}
```

Strategy descriptions are defined by the following syntax:

```
S ::= rule_id % Apply the gives rule
| package_id % Apply any rule defined in the package (not in sub-packages)
| strat_id % Called a strategy defined elsewhere
| Pick (S) % Select arbitrary one of the graph produced by the strategy S
| Alt (S_1, …, S_n) % Collect graphs produced by each sub-strategies (union)
| Seq (S_1, …, S_n) % Apply sequentially S_1, then S_2 on S_1 output …
| Iter (S) % Iterate the application of the strategy S until normal forms
| If (S, S_1, S_2) % If S is productive then it is equivalent to S_1 else it is equivalent to S_2
```

Other constructor are provided for some strategies

```
Empty ≜ Seq() % The Empty strategy always returns the input graph
Try (S) ≜ If (S, S, Empty) % Equivalent to S if S is productive else it returns the input graph
```

### Computing one normal form

To compute only one normal form with a strategy `S`

, one can used the strategy: `Pick (Iter (S))`

:
the strategy `Iter (S)`

computes the full set of normal forms and the `Pick`

operator choses one of them.
But this may be not efficient if the number of normal forms is high.

For this case, another implementation of the rewriting is available with the operator `Onf`

(the name stands for ‘One normal form’).
With this operator, only one normal form is built, and so :

```
Onf (S) = Pick (Iter (S))
```

⚠️ But `Onf`

can be safely used only if the strategy is terminating. More info about this on the rewriting page.

## Packages

Packages are used to organize the set of declarations and to define scopes of definitions. Syntax of packages definition:

```
package package_id {
declarations_list
}
```

where `declarations_list`

is a list of declarations of **rules**, **packages** and **strategies**.

The syntax for accessing to some element `e`

defined in package `P`

is `P.e`

.
In case of nested packages, an identifier may look like `P1.P2.P3.e`

.
When a reference is made to an element `P1.P2.e`

, the system tries to find inside the current package a sub-package `P1`

which contains a sub-package `P2`

which contains an element `e`

.
If no such element is found, the same thing is searched recursively, first in the mother package of the current one, up to the root package.

Note that it is not allowed to have a domain declaration inside a package.

## Multi-file management

When a GRS become large and contains an high number of rules, it is sensible to define it in through a set of files. Two mechanisms are available for this purpose: external file import and external file inclusion.

### External file import

At any place in a list of declaration in a GRS file, one can use the syntax:

```
import "filename.grs"
```

This creates a new package with the same name as the file (without the `.grs`

extension).
Hence, the meaning is the same as the following code:

```
package filename {
<<< content of the file "filename.grs" >>>
}
```

As a consequence, it is not allowed to import a file which contains domain declarations because it would be equivalent to a domain declaration inside a package and this is forbidden. To use a external domain declaration, one should use the file inclusion.

### External file inclusion

With file inclusion, the content of the external file is interpreted as if it was placed directly in the file at the same place. In other words the code:

```
include "filename.grs"
```

has the same meaning as

```
<<< content of the file "filename.grs" >>>
```

## A complete example

We consider the same GRS defined through the multi-file mechanism and with a single file.

### Multi-file declaration

Consider a folder with the five files:

`labels { L_1, L_11, L_12 }`

`rule r_1 { pattern { e:X -[L]-> Y} commands { del_edge e; add_edge X -[L_1]-> Y } } rule r_11 { pattern { e:X -[L_1]-> Y} commands { del_edge e; add_edge X -[L_11]-> Y } } rule r_12 { pattern { e:X -[L_1]-> Y} commands { del_edge e; add_edge X -[L_12]-> Y } }`

`labels { L_2, L_21, L_22 }`

`rule r_2 { pattern { e:X -[L]-> Y} commands { del_edge e; add_edge X -[L_2]-> Y } } rule r_21 { pattern { e:X -[L_2]-> Y} commands { del_edge e; add_edge X -[L_21]-> Y } } rule r_22 { pattern { e:X -[L_2]-> Y} commands { del_edge e; add_edge X -[L_22]-> Y } }`

`labels { L } include "d_1.dom" include "d_2.dom" import "p_1.grs" import "p_2.grs" strat p_1_nfs { Iter (p_1) } % all normal forms with package p_1 strat p_1_onf { Onf (p_1) } % one normal form with package p_1 strat union { Alt (p_1,p_2) } % union of the two set of rules strat all_nfs { Iter (union)} % all normal forms strat s_1 { Seq (Pick(p_1), Pick(p_2), all_nfs) }`

### Single file declaration

The five files above define a GRS, equivalent to the one below:

`single.grs`

`labels { L, L_3, L_4, L_5 } labels { L_1, L_11, L_12 } labels { L_2, L_21, L_22 } package p_1 { rule r_1 { pattern { e:X -[L]-> Y } commands { del_edge e; add_edge X -[L_1]-> Y } } rule r_11 { pattern { e:X -[L_1]-> Y } commands { del_edge e; add_edge X -[L_11]-> Y } } rule r_12 { pattern { e:X -[L_1]-> Y } commands { del_edge e; add_edge X -[L_12]-> Y } } } package p_2 { rule r_2 { pattern { e:X -[L]-> Y } commands { del_edge e; add_edge X -[L_2]-> Y } } rule r_21 { pattern { e:X -[L_2]-> Y } commands { del_edge e; add_edge X -[L_21]-> Y } } rule r_22 { pattern { e:X -[L_2]-> Y } commands { del_edge e; add_edge X -[L_22]-> Y } } } strat p_1_nfs { Iter (p_1) } % all normal forms with package p_1 strat p_1_onf { Onf (p_1) } % one normal form with package p_1 strat union { Alt (p_1,p_2) } % union of the two set of rules strat all_nfs { Iter (union)} % all normal forms strat s_1 { Seq (Pick(p_1), Pick(p_2), all_nfs) }`

Note that all the rules consist in the changement of the label of one edge.
Package `p_1`

rewrites the label `L`

into `L_1`

and `L_1`

into either `L_11`

or `L_12`

.
Similarly, package `p_2`

rewrites the label `L`

into `L_2`

and `L_2`

into either `L_21`

or `L_22`

.

### Apply the GRS to a graph

Consider small graph with 3 nodes and 2 edges labeled `L`

defined in

```
graph {
A -[L]-> B;
B -[L]-> C;
}
```

Next commands rewrite the graph `input.gr`

, following different strategies (⚠️ the `-gr`

options is needed to output graph in the native format instead of CoNLL-U)

#### strategy `p_1_nfs`

`grew transform -grs single.grs -strat p_1_nfs -i input.gr -gr`

computes all normal forms for the input graph with rules of package `p_1`

.
Each initial edges `L`

can be rewritten either `L_11`

or `L_12`

, and so 4 graphs are produced:

```
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X_11]-> N_1;
N_1 -[X_11]-> N_0;
}
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X_12]-> N_1;
N_1 -[X_11]-> N_0;
}
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X_11]-> N_1;
N_1 -[X_12]-> N_0;
}
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X_12]-> N_1;
N_1 -[X_12]-> N_0;
}
```

#### strategy `p_1_onf`

`grew transform -grs single.grs -strat p_1_onf -i input.gr -gr`

produces one of the 4 graphs of the previous strategy.

```
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X_12]-> N_1;
N_1 -[X_12]-> N_0;
}
```

#### strategy `union`

`grew transform -grs single.grs -strat union -i input.gr -gr`

compute the application of the union of one step of rewriting with `p_1`

(which produces 2 graphs, replacing one the two `L`

edge by `L_1`

and the same with `p_2`

. In the end, 4 graphs are produced (there is no iteration of rule application).

```
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X]-> N_1;
N_1 -[X_1]-> N_0;
}
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X]-> N_1;
N_1 -[X_2]-> N_0;
}
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X_1]-> N_1;
N_1 -[X]-> N_0;
}
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X_2]-> N_1;
N_1 -[X]-> N_0;
}
```

#### strategy `all_nfs`

`grew transform -grs single.grs -strat all_nfs -i input.gr -gr`

computes all normal forms that can be obtained with these all the rules and produces 16 graphs.

```
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X_11]-> N_1;
N_1 -[X_11]-> N_0;
}
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X_12]-> N_1;
N_1 -[X_11]-> N_0;
}
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X_21]-> N_1;
N_1 -[X_11]-> N_0;
}
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X_22]-> N_1;
N_1 -[X_11]-> N_0;
}
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X_11]-> N_1;
N_1 -[X_12]-> N_0;
}
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X_12]-> N_1;
N_1 -[X_12]-> N_0;
}
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X_21]-> N_1;
N_1 -[X_12]-> N_0;
}
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X_22]-> N_1;
N_1 -[X_12]-> N_0;
}
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X_11]-> N_1;
N_1 -[X_21]-> N_0;
}
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X_12]-> N_1;
N_1 -[X_21]-> N_0;
}
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X_21]-> N_1;
N_1 -[X_21]-> N_0;
}
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X_22]-> N_1;
N_1 -[X_21]-> N_0;
}
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X_11]-> N_1;
N_1 -[X_22]-> N_0;
}
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X_12]-> N_1;
N_1 -[X_22]-> N_0;
}
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X_21]-> N_1;
N_1 -[X_22]-> N_0;
}
graph {
N_2 [label="A"] ;
N_1 [label="B"] ;
N_0 [label="C"] ;
N_2 -[X_22]-> N_1;
N_1 -[X_22]-> N_0;
}
```