Grew main page

Pattern syntax

To be able to express more general rules, nodes and edges can be underspecified and so the definitions of nodes and edges given in the documentation of the GR graph format have to be generalized.

:NEW: You can learn to write patterns using the Grew-web tool. The tutorials give a step by step introduction to pattern syntax.

Nodes

To design general and flexible patterns, features values can be disjunction of atomic values rather than only one atom, the disjunction is written with the | symbol. Here is an example of a pattern node:

N4 [cat=V, m=inf|part]

Disjunction on the full set of possible value is written *

N4 [cat=V, m=*]

Pattern can also use inequality to filter nodes which contains some feature but with a value different from the ones given:

N4 [cat=V, m<>part]

Again, quotes are used for values that cannot be lexed as identifier:

N4 [cat=V, lemma="être", p="1"|"2"]

Edges

It is also possible to use disjunction of values as a label on a pattern edge.

 A -[obj|de_obj]-> B 

If there is no restriction on the edge label, a simpler syntax exists.

 A -> B 

It is also possible to give a negative constraints to avoid some labels.

 A -[^obj|de_obj]-> B 

Unfortunately, with the extensions above, it may be problematic to refer to a specific edge in commands. To overcome this problem, it is possible to give identifier (as a prefix separated by :, like the e in the two examples below) to an edge and hence to refer to it later unambiguously.

 e: A -[obj|de_obj]-> B 
 e: A -> B

Filters

A pattern can also contain some filters. A filter does not bind any nodes nor edges, it only makes the pattern fails if some condition is not satisfied.

Out-edges filter

The pattern filter below is satisfied iff there is some out-edge with label obj starting from node A.

A -[obj]-> *

NB: During the matching process, * stands for any node (no injectivity is required on the node matched by the * ).

In-edges filter

The pattern filter below is satisfied iff there is some in-edge with label obj ending in node A.

* -[obj]-> A

Feature value comparison

The filter below is satisfied if and only if the two features exist and have the same value:

A.lemma = B.lemma

The code below tests if two feature values are different:

A.lemma <> B.lemma

For numerical feature values, inequalities can be used for instance to compare positions:

  A.position < B.position;
  A.position ≤ B.position;
  A.position <= B.position;
  A.position > B.position;
  A.position ≥ B.position;
  A.position >= B.position;

Feature structure filter

If the identifier V already binds a node, the line below is interpreted as a filter which fails if the matched node does not satisfy the features structure fs.

V [fs]

NB: the main usage of feature structure filter is in negative pattern to avoid some feature: to match a node with a feature cat=v but without any feature named label, one can write:

  match { V [cat = v] }
  without { V [label = *] }

Pattern

Finally a pattern is defined as a set of pattern nodes, pattern edges and pattern filters with the same consistency constraints as for graph. It is introduced by the keyword match, separated by semicolon ; and surrounded by braces:

  match {
    V [cat=V, lemma="accuser"];
    O [];
    D [cat=D, lemma="de"];
    DO [cat=V, m = inf | part];
 
    V -[obj]-> O;
    V -[de_obj]-> D;
    D -[obj]-> DO
    }

Negative patterns

A pattern can be followed by any number of negative pattern extensions. The syntax of a pattern extension is the same a the syntax of a pattern (with the keyword without instead of match).

Consistency of a pattern extension is defined relatively to the corresponding positive pattern: a negative pattern can use either node defined in the positive pattern or node defined in the same pattern extension.

Matching

Suppose given a positive pattern P, a list of negative patterns N1, …, Nk.

A simple matching is an injective graph morphism from P into G

A matching φ for (P, N1, …, Nk) into a graph G is an injective function from nodes of P to nodes of G which verifies:

  • φ is a simple matching from P to G
  • for all i, there is no simple matching extending φ to a matching from PNi to G.