⬆️ Top

# Compute span of nodes in a dependency tree

This example illustrates the usage of non-injective matching introduced in version 1.11 (January 2023).

The objective is to add to each node, two new outgoing edges (labeled span=left and span=right) from the given node to its leftmost projection and rightmost projection respectively.

The main idea of the GRS is:

1. add to each node two looping links span=left and span=right (rule init above)
2. iteratively enlarge the span of one node either on the left or on the right (package enlarge above): “if one of my daughter node has a left [resp. right] span which is more on the left [resp. right] than mine, it become my new left [resp. right] span”. When this last rule cannot be applied further, the spans are correcly computed.

The second item (for the left case) can be formulated in the Grew rule below, with nodes:

• N: the current node where the span will be enlarge
• LN: the left span of N before the application of the rule
• X: the daughter of N having a left span LX which is more on the left than LN
• LX: the left span of X
rule left {
pattern { e: N -[span=left]-> LN; N -> X; X -[span=left]-> LX; LX << LN }
commands {
del_edge e;
}
}


The main difficulty is that we have to take into account some superposition subcases (NB: the other superposition cases cannot arise, the proof is left as an exercise!) Possible cases are:

1. all nodes are different
2. N and LN refers to the same node
3. X and LX refers to the same node
4. (N and LN refers to the same node) and (X and LX refers to the same node)
5. LN and X refers to the same node

When using only injective matching, we then have to design 10 rules (5 on the left and 5 on the right) for the enlarge package (see below).

With non-injective matching (introduced in version 2.11), the same package can be written with only two rules.

## Solution with non-injective matching

With the grs file non_injective.grs:

rule init {
pattern { N [upos] }
without { N -[span=left]-> * }
without { N -[span=right]-> * }
commands {
}
}

package enlarge {
rule left {
pattern { e: N -[span=left]-> LN$; N -> X; X -[span=left]-> LX$; LX$<< LN$ }
commands {
del_edge e;
add_edge N -[span=left]-> LX$; } } rule right { pattern { e: N -[span=right]-> RN$; N -> X; X -[span=right]-> RX$; RN$ << RX$} commands { del_edge e; add_edge N -[span=right]-> RX$;
}
}
}

strat main { Seq (Onf (init), Onf (enlarge)) }


⚠️ In Grew-web, dependency graphs are drawn with dep2pict and loops can not be displayed directly. Loops are replaced by a special features with a green background and with double brackets. See for instance, the final graph computed with the example above: ## Solution with only injective matching

With the grs file injective.grs:

rule init {
pattern { N [upos] }
without { N -[span=left]-> * }
without { N -[span=right]-> * }
commands {
}
}

package enlarge {

% 4 different nodes
rule left_1 {
pattern { e: N -[span=left]-> LN; N -> X; X -[span=left]-> LX; LX << LN }
commands {
del_edge e;
}
}

% LN = N
rule left_2 {
pattern { e: N -[span=left]-> N; N -> X; X -[span=left]-> LX; LX << N }
commands {
del_edge e;
}
}

% LX = X
rule left_3 {
pattern { e: N -[span=left]-> LN; N -> X; X -[span=left]-> X; X << LN }
commands {
del_edge e;
}
}

% LN = N & LX = X
rule left_4 {
pattern { e: N -[span=left]-> N; N -> X; X -[span=left]-> X; X << N }
commands {
del_edge e;
}
}

% LN = X
rule left_5 {
pattern { e: N -[span=left]-> X; N -> X; X -[span=left]-> LX; LX << X }
commands {
del_edge e;
}
}

% 4 different nodes
rule right_1 {
pattern { e: N -[span=right]-> RN; N -> X; X -[span=right]-> RX; RX >> RN }
commands {
del_edge e;
}
}

% RN = N
rule right_2 {
pattern { e: N -[span=right]-> N; N -> X; X -[span=right]-> RX; RX >> N }
commands {
del_edge e;
}
}

% RX = X
rule right_3 {
pattern { e: N -[span=right]-> RN; N -> X; X -[span=right]-> X; X >> RN }
commands {
del_edge e;
}
}

% RN = N & RX = X
rule right_4 {
pattern { e: N -[span=right]-> N; N -> X; X -[span=right]-> X; X >> N }
commands {
del_edge e;
}
}

% RN = X
rule right_5 {
pattern { e: N -[span=right]-> X; N -> X; X -[span=right]-> RX; RX >> X }
commands {
del_edge e;