Requests
Requests are used in Grew to describe the left part of rewriting rules and in Grewmatch to describe queries to be executed on corpora.
The syntax of requests in Grew can be learnt using the tutorial part of the Grewmatch tool.
Requests syntax
A request is defined through 4 different kinds of request items.
 Global items (introduced by the keyword
global
) filter structures based on information about the whole graph or its metadata.  Matching items (introduced by keyword
pattern
) describe nodes and relations that must be found in the graph.  Positive filtering items (introduced by the keyword
with
) filter out matchings previously selected by other items (keeping only the ones which follows the additional graph constraints).  Negative filtering items (introduced by the keyword
without
) filter out matchings previously selected by other items (keeping only the ones which do not follow the additional graph constraints).
The full matching on one graph process is:
 Take a graph and a request as input.
 Output a set of matchings; a matching being a function from nodes and edges defined in the matching items to nodes and edges of the host graph.
 If the graph metadata does not satisfy one of the global items, the output is empty.
 Else the set M is initialised as the set of matchings which satisfy the union of matching items.
 For each positive filtering item, remove from M the matchings which do not satisfy it.
 For each negative filtering item, remove from M the matchings which satisfy it.
On a corpus, the graph matching process is repeated on each graph.
Remarks
 If there is more than one matching
pattern
items, the union is considered.  If there is more than one filtering (
without
orwith
) items, there are all interpreted independently  The order of items in a request are irrelevant.
 It there is no positive item, there is a trivial matching which is the empty function.
Matching and filtering items
Matching and filtering items both follow the same syntax. They are described by a list of clauses: node clauses, edge clauses and additional constraints
Node clauses
In a node clause, a node is described by an identifier (X
in the example below) and some constraints on its feature structure.
X [upos = VERB, Mood = IndImp, Tense <> Fut, Number, !Person, form = "être", lemma = re"s.*" ]
The clause above illustrates the syntax of constraint that can be expressed, in turn:
upos = VERB
requires that the featureupos
is defined with the valueVERB
Mood = IndImp
requires that the featureMood
is defined with one of the two valuesInd
orImp
Tense <> Fut
requires that the featureTense
is defined with a value different fromFut
Number
requires that the featureNumber
is defined whatever is its value (note that the same constraint can also be writtenNumber = *
)!Person
requires that the featurePerson
is not definedform = "être"
quotes are required when nonASCII characters are usedlemma = re"s.*"
the prefixre
before a string declares a regular expression
Anchor nodes
⚠️ For dependency trees, an anchor node (position 0) is added to the structure (see here). In ArboratorGrew, this node is not displayed but is still taken into account when searching requests or when applying rules.
Disjunction in node clause
⚠️ Since version 1.14
Following the feature request #47, a node can be matched with a disjunction of feature structures
(separated by the pipe symbol 
).
Examples
The following clause selects either a past participle verb or an adjective :
X [upos=VERB, VerbForm=Part, Tense=Past][upos=ADJ]
A node with either a upos
ADV
(and no ExtPos
) or an ExtPos
ADV
can be searched with
:
X [upos=ADV, !ExtPos][ExtPos=ADV]
Edge clauses
All edge clauses below require the existence of an edge between the node selected by X
and the node selected by Y
, eventually with additional constraints:
X > Y
: no additional constrainsX [nsubj]> Y
: the edge label isnsubj
X [nsubjobj]> Y
: the edge label is eithernsubj
orobj
X [^nsubjobj]> Y
: the edge label is different fromnsubj
andobj
X [re".*subj"]> Y
: the edge follows the regular expression (see here for regular expressions accepted)
Edges may also be named for usage in commands (in Grew) or in clustering (in Grewmatch) with an identifier:
e: X > Y
e: X [nsubj]> Y
 …
Note that edges may refer to undeclared nodes, these nodes are then implicitly declared without constraint. For instance, the two requests below are equivalent:
pattern { X [nsubj]> Y }
pattern { X[]; Y[]; X [nsubj]> Y }
Additional constraints
These constraints do not bind new elements in the graph, but must be fulfilled (i.e. binding solutions which do not fulfill the constraints are filtered out).
Constraints on feature values:
X.lemma = Y.lemma
two feature values must be equalX.lemma <> Y.lemma
two feature values must be differentX.lemma = "constant"
the featurelemma
of nodeX
must be the valueconstant
X.lemma = re".*ing"
the value of a feature must follow a regular expression (see here for regular expressions accepted)X.lemma = lexicon.field
imposes that the featurelemma
of nodeX
must be the be present in thefield
of thelexicon
. NB: this also reduces the current lexicon to the items for whichfield
is equals toX.lemma
.
Constraints on node ordering:
X < Y
the nodeX
immediately precedes the nodeY
X << Y
the nodeX
precedes the nodeY
Constraints on in or out edges on bound nodes:
* [nsubj]> Y
there is an incoming edge with labelnsubj
with targetY
(NB: the source node of the incoming edge is not bound; it can be equals to any other node (bound or not))Y [nsubj]> *
there is an outgoing edge with labelnsubj
with sourceY
(NB: the target node of the outcoming edge is not bound; it can be equals to any other node (bound or not))
Constraints on edge labels:
e1.label = e2.label
the labels of the two edgese1
ande2
are equale1.label <> e2.label
the labels of the two edgese1
ande2
are different
Constraints on edges relative positions
These constraints impose that the source and the target of both edges are ordered)
e1 >< e2
the two edges intersect (this implies that the 4 nodes are all ordered)e1 << e2
the edgee1
is covered bye2
e1 <> e2
the two edges are disjoint
Position of a node with respect to an edge
X << e
the nodeX
is strictly included between the source and the target of edgee
.
Constraints on distance between two nodes
🆕 in Version 1.16. These constraints impose both X
and Y
are ordered nodes
length(X,Y) = 4
the length of the dependency relation is 4 (i.e. there are exactly 3 other nodes betweenX
andY
), whatever is the relative position ofX
andY
delta(X,Y) = 4
the length of the dependency relation is 4 andY
is afterX
in the linear orderdelta(X,Y) = 4
the length of the dependency relation is 4 andY
is beforeX
in the linear order
In the previous constraints, =
can be replaced by <
, <=
, >
or >=
with an obvious meaning!
The keywords length
and delta
are also available as clustering keys.
Injectivity in nodes matching
By default the matching of nodes is injective, this means that two different nodes in the request are mapped to two different nodes in the graph.
For instance, the request below searches for two different tokens, both having the same lemma make
pattern { X1 [ lemma="make" ]; X2 [ lemma="make" ] }
If the node identifier is suffixed by the symbol $
, the injectify constraint is relaxed.
A node X$
can be mapped to any node in the graph (either already mapped by another node of the request or not).
Example
For a more complex example with noninjective matching, you can see this example.
In AMR graphs, if we look for a predicate (with concept=judge01
in the example) with two arguments ARG0
and ARG1
, there are two dictinct cases:
pattern { X [concept="judge01"]; X [ARG0]> A0; X [ARG1]> A1; }
pattern { X [concept="judge01"]; X [ARG0]> A; X [ARG1]> A; }
If we do not require the injectivity on one of the two arguments, then both cases above are returned → 5 occurences
pattern { X [concept="judge01"]; X [ARG0]> A; X [ARG1]> B$; }
Complex edges
As label edges are internally represented by feature structures (see here), it is possible to match them with a standard unification mechanism, similar to the one used for feature structures in nodes.
X [1=subj]> Y
the edge must match the edge feature constraints (more examples below). [Since version
1.9.1
]X [2="зад"]> Y
the edge must match the edge feature constraints with nonASCII characters (see #36).
Some examples (with sud
configuration) are given below.
Syntax  Description  comp 
comp:obl 
comp:obl@agent 
comp:aux 
comp:obj@lvc 

X [1=comp]> Y 
any edge such that the feature 1 is defined with value comp 
YES  YES  YES  YES  YES 
X [1=comp, 2=oblaux]> Y 
the feature 1 is defined with value comp and the feature 2 is defined with one of the two values obl or aux 
NO  YES  YES  YES  NO 
X [1=comp, 2<>oblaux]> Y 
the feature 1 is defined with value comp and the feature 2 is defined with a value different from obl or aux 
NO  NO  NO  NO  YES 
X [1=comp, !deep]> Y 
the feature 1 is defined with value comp and the feature deep is not defined 
YES  YES  NO  YES  NO 
X [1=comp, 2=*]> Y 
the feature 1 is defined with value comp and the feature 2 is defined with any value 
NO  YES  YES  YES  YES 
X [comp]> Y 
the exact label comp and nothing else 
YES  NO  NO  NO  NO 
⚠️ Matching with atomic labels ⚠️
It is important to note that from the request point of view, the two clauses X [1=comp]> Y
(first line in the table) and X [comp]> Y
(last line in the table) are not equivalent!
Difference with node features matching
Note that we would expect that the syntax X [1=comp, 2]> Y
should be equivalent to X [1=comp, 2=*]> Y
but it will bring an ambiguity for X [lab]> Y
that can be interpreted as the atomic label X [lab]> Y
or as X [lab=*]> Y
.
To avoid this ambiguity, the syntax X [1=comp, 2]> Y
in not allowed.
Global request
Global requests let the user express constrains about the structure of the whole graph. It is also possible to express constraints about metadata of the graph.
Structure constraints
Structure constraints are expressed with a fixed list of keywords.
We describe below 4 of the constraints available.
For each one, its negation is available by changing the is_
prefix by the is_not_
prefix.

is_cyclic
: the graph satisfied this constraint if and only if it contains a cycle. A cycle is a list of nodesX1
,X2
…X(k1)
,Xk
such that there are edgesX1 > X2
,X2 > X3
,X(k1) > Xk
,Xk > X1
. In graph theory, a non cyclic graph is also called a Directed Acyclic Graph (DAG). 
is_forest
: the graph satisfied this constraint if and only it is acyclic and if there are no couples of edges with the same target. In other words, a graph is a forest if and only if it is acyclic and each node has at most one incoming edge. 
is_tree
: a graph is a tree if it is a forest and if it have exactly one root. 
is_projective
: the usual notion of projectivity defined on tree is generalised by saying the a structure is projective if there are no 4tuples (A
,B
,C
,D
) of ordered nodes (i.e.A << B
,B << C
andC << D
) such thatA
andC
are linked andB
andD
are linked (two nodes are linked when there is at least one edge between the two, whatever is the orientation).
Metadata constraints
In Grew, each graph is associated with a list of metadata: a list of (key, value) pairs.
In global
items, constraints of these metadata can be expressed with:
sent_id = "frudtrain_01234"  "frudtrain_12345"
: the metadatasent_id
has one of the two given values;sent_id <> "frudtrain_01234"  "frudtrain_12345"
: the metadatasent_id
is different from two given values;text = re".*\baux\b.*
: thetext
metadata field follows the given regexp (see here for regular expressions accepted; in the example, the field must contain the word aux).
For corpora described by the CoNLLU format, available metadata are described before each sentence (see CoNNLU doc).
In the UD or SUD corpora, each sentence contains at least the two metadata sent_id
and text
.
Some other tricks
Equivalent nodes
When two or more nodes are equivalent in a request (i.e. they can be interchanged without altering the meaning of the request), each occurrence of the request in a graph is reported multiple times (up to permutation in the sets of equivalent nodes).
For example, in the request below, the 3 nodes X1
, X2
and X3
are equivalent.
pattern { X1 [ARG1]> X; X2 [ARG1]> X; X3 [ARG1]> X; }
This request is found 270 times in the Little Prince corpus
but there are only 45 different occurrences; each one being reported 6 times with all permutations on X1
, X2
and X3
.
To avoid this, the constraint X1.__id__ < X2.__id__
can be used, which imposes an ordering on some internal representation of the nodes and so avoids these permutations.
NB: If a constraint X1.__id__ < X2.__id__
is used with two nonequivalent nodes, the result is unspecified.
The request below returns the 45 expected occurrences
pattern {
X1 [ARG1]> X; X2 [ARG1]> X; X3 [ARG1]> X;
X1.__id__ < X2.__id__; X2.__id__ < X3.__id__;
}