Grew

Graph Rewriting for NLP

Command syntax

Each rule contains a sequence of commands introduced by the keyword commands, separated by semicolon symbol ; and surrounded by braces.

Edge deletion

To delete an edge, the del_edge command can refer either to the full description of the edge or to an identifier e given in the request:

del_edge X -[obj]-> Y;
del_edge e;

For the first syntax, if the corresponding edge does not exists, an exception is raised and the full rewriting process is stopped.

Add a new edge

The basic syntax to add a new edge is:

add_edge X -[suj]-> Y

It is also possible to give a name to the newly created edge, in order to manipulate it in the next commands. For instance the two commands below create a new edge f and copy the edge label of some other edge e.

add_edge f: X -> Y;    % this supposes that `f` is a fresh name in the rule
f.label = e.label;     % this supposes that `e` is a known edge in the rule

NB: the syntax above (add_edge f:…) has changed in version 1.4, please see here for info about migration.

Node deletion

The following command removes the node X and all its incident edges.

del_node X

Node creation

To create a new node, the command is add_node. The command below creates a new node and give it the identifier X until the end the rule application.

add_node X

Moreover, if the node must be placed at a specific position in the linear order of the nodes, two syntax are available: the new node Y (resp. Z) is placed on the immediate left (resp. right) of the node X.

add_node Y :< X
add_node Z :> X

Shifting (edge redirection)

Commands are available to move globally incident edges of some node of the pattern. Keywords are shift_in, shift_out and shift, respectively for moving in-edges, out-edges and all incident edges.

Brackets can be used to select the set of edges to move according to their labelling.

⚠️ edges between two nodes matched by the pattern are not changed by shift rules. The only edges that are moved are edges linking one node of the pattern and one node which is not in the pattern.

  shift X ==> Y
  shift_out X =[suj|obj]=> Y
  shift_in X =[^suj|obj]=> Y

The action of the 3 commands above are respectively:

Add or update a node feature

The following commands update the feature f of the node X. If the node X does not have such a feature, it is added.

X.f = "new_value"    % give a new value
X.f = Y.f            % copy a feature value from another node

It is possible to use the + symbol for string concatenation:

X.f = Y.f + "/" + Y.lemma

🆕 in version 1.8: A Python like slicing can be added in the right-hand side of the updating command.

X.f = Y.f[1:]          % copy `Y.f` on node `X`, skipping the first character
X.f = Y.f[:-1] + X.f   % prepend `Y.f` (without the last character) to `X.f`

NB: the indexes used in slicing refers the UFT-8 characters. If X.form is "помощник" then X.form[2:4] is "мо"

Remove a node feature

del_feat X.f

Modification of an existing edge

In commands, it is possible to manipulate subpart of edges. If the request binds the identifier e to some edge (with the syntax e: X -[…]-> Y), the following commands can be used:

Changing nodes order

Change an ordered node into an unordered node

unorder X

Change an unordered node into an ordered node

insert X :> Y  % put the unordered node X right after the node Y 
insert X :< Y  % put the unordered node X right before the node Y

The two commands unorder and insert can be used together to move a node. For instance the next rule exchanges the positions of X1 and X2

rule ex {
  pattern { X1 [upos=VERB]; X2 [upos=ADV]; X1 < X2 }
  commands { unorder X1; insert X1 :> X2 }
}

Copy several features from one node to another

The commands append_feats X ==> Y / prepend_feats X ==> Y appends / prepends all features (different from form, lemma, upos, xpos) of node X to features of node Y.

To be more precise, the commands append_feats X ==> Y / prepend_feats X ==> Y modify the feature structure of node Y:

It is also possible to add a string separator for feature values concatenation. The command append_feats "/" X ==> Y will have the same effect as Y.f = Y.f + "/" + X.f when f is defined in both nodes.

This can be used to clone a node. The command below clones the node Y into a new node, called X in the rule, such that X follows Y. A new edge copy is added from Y to its clone.

rule clone {
  pattern { X [form, lemma, upos=VERB]; }
  without { X -[copy]-> * } % to avoid loop: do not clone twice the same node
  without { * -[copy]-> X } % to avoid loop: do not clone a clone
  commands {
    add_node Y :> X;
    append_feats X ==> Y;
    Y.form = X.form;
    Y.textform = X.textform;
    Y.lemma = X.lemma;
    Y.upos = X.upos;
    add_edge X -[copy]-> Y;
  }
}

With the syntax below, the set of features taken into account can be filtered with a regexp:

append_feats X1 =[re"Number\|Gender"]=> X2;
prepend_feats X3 =[re"Gloss"]=> X4;

Examples

Example 1: copy an edge feature value

Rule: copy.grs:

rule main {
  pattern { e1: N -[1=X]-> M; e2: M -[!2]-> T }
  commands { e2.2 = e1.2 }
}
Input graph: copy.json Rewritten graph
input output

Example 2: modify and edge and copy it

This example and the next one show that modifying an edge before copying it is different from the reverse order

Rule: modify_and_copy.grs: 

rule main {
  pattern { e1: N -[1=X]-> M; M -> T }
  commands {
    e1.2 = U;
    add_edge new_e: M -> T;
    new_e.label = e1.label;
  }
}

Input graph: copy.json Rewritten graph
input output

Example 2bis: copy and edge and modify it

Rule: copy_and_modify.grs: 

rule main {
  pattern { e1: N -[1=X]-> M; M -> T }
  commands {
    add_edge new_e: M -> T;
    new_e.label = e1.label;
    e1.2 = U;
  }
}

Input graph: copy.json Rewritten graph
input output

Example 3: reverse an edge

GRS: reverse.grs: 

rule r {
  pattern { N -[X]-> M; e: N -[Y|Z]-> M }
  commands {
    add_edge new_e: M -> N;
    new_e.label = e.label;
    del_edge e;
  }
}
strat main { Onf (r) }

Input graph: reverse.json Rewritten graph
input output

By contrast, with the GRS: fail_reverse.grs: 

rule r {
  pattern { N -[X]-> M; e: N -[Y|Z]-> M }
  commands {
    del_edge e;
    add_edge new_e: M -> N;
    new_e.label = e.label;  % <== this command cannot be executed because `e` doesn't exist anymore
  }
}
strat main { Onf (r) }

the command grew transform -grs fail_reverse.grs applied to the same graph produces the error:

MESSAGE : [file: fail_reverse.grs, line: 6] Unknown identifier "e"

Example 4: shifting

GRS: shift.grs: 

rule main {
  pattern { a[label="♧"]; b[label="♡"]; c[label="♢"]; a -[A]-> b; }
  commands {
    shift a =[D]=> b;
    del_node a;
    shift b =[D]=> c;
  }
}

Input graph: shift.json after one command after two commands Rewritten graph
input step1 step2 output

Effective commands

There are situations where the actions commands may be difficult to define. Consider the rule r below and and a graph with two nodes A and B linked by two edges X and Y both going from A to B. The rule r can be applied to the graph but the command add_edge can not be applied (the edge labelled Y already exists).

rule r {
  pattern { N -[X]-> M }
  commands { add_edge N -[Y]-> M }
}

The fact that a rule is effective or not depends on the graph on which the rule is applied.

In fact, to deal with this case, Grew has two running modes with different behaviors.

  1. In the default mode, ineffective commands are simply ignored and the rewriting goes on with the next commands or rules.
  2. In the safe mode (set by the -safe_commands argument), an ineffective command stop the rewriting with and produces an execution error.

List of ineffective Commands

Commands which may be ineffective are:

Note that it is always possible to define a Graph Rewriting System with only effective commands following the procedure: