⬆️ 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;
    add_edge N -[span=left]-> LX;
  }
}

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 1.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 { 
    add_edge N -[span=left]-> N;
    add_edge N -[span=right]-> N;
  }
}

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)) }

⚙ Try it ⚠️ In Grew-web, dependency graphs are drawn with dep2pict and loops can not be displayed directly. Loops are replaced by 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 { 
    add_edge N -[span=left]-> N;
    add_edge N -[span=right]-> N;
  }
}

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;
      add_edge N -[span=left]-> LX;
    }
  }

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

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

  % 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;
      add_edge N -[span=left]-> X;
    }
  }

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

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

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

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

  % 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;
      add_edge N -[span=right]-> X;
    }
  }

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

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

⚙ Try it