Grail Tutorial - NL Grammars, Lexical Graphs and Graph Contractions

This tutorial assumes you are familiar with AB grammars and Grails way of parsing AB grammars by identifying positive and negative atomic categories in the graph. The non-associative Lambek calculus NL, introduced by Lambek (1961), adds symmetric operations to AB. Whereas in AB, we would only build complex trees out of simpler ones, NL gives us a limited way of destroying part of a tree which has already been built.

Lexical Graphs

The lexical lookup for the sentence
[Someone slept] Select the sentence "Someone slept" from the NL section of the grammar grail0.pl and verify that Graphviz produces the same structure as shown in the figure.

The figure shows the lexical tree for the intransitive verb "slept" : it is looking for a noun phrase to its left in order to form a sentence. We have seen this type of lexical trees before: it is explained in the section about the connections of AB.

It is the lexical tree for "someone" which interests us here. Let's begin by just looking at the nodes and the atomic categories. Remember that categories displayed above the node number are thing the lexical graph looking for (positive categories or hypotheses), whereas categories below the node number are things the lexical graph provides (negative categories or conclusions. So the graph is looking for a sentence (the s of node 4) while providing a noun phrase (the np of node 5) and a sentence (the s of node 2). One difference with AB trees, where we are looking for a number of categories, this number can be zero of course, to provide a single one is clear even from this superficial observation: we are looking for a single category but provide two in return.

A new element is the connection with the filled circle linking node 3, 4 and 5. It is an inverse connection, sometimes called an auxiliary constructor, which can be seen as a sort of constraint we have to verify: a correct use to this inverse connection will have node 4 and 5 (that is, the two node to which the arrow isn't pointing) attached to two nodes of another connection, but with an open circle. In addition, we require that node 4, which is connected to the filled circle with label 3, is connected to the open circle with label 3 as well and that node 5, which is connected to the filled circle with label 1, is connected to this same open circle with label 1 as well.

Node 8 from the tree for "slept" is a negative s node linked to an open circle with label 3. Therefore, the positive s node 4 which is connected to the filled circle with label 3 can be connected to it: both from the point of view of the substitutions (positive canceling out negative) and from the point of the constraint.

Connect the two s node 8 and 4 by selecting them in the atom selection window. Now, in order to satisfy the constraint imposed by the filled connection, we have to connect the two np nodes 5 and 7 as well. This way, we identify a positive and negative node, as required, but in addition we ensure that the filled and open connections are connected by a second node: the np node now links both the filled and open connection by a 1-labeled path.

Perform the 5-7 connection and the final 2-9 connection to complete the substitution phase on the parse of this sentence.

Graph Contractions

The binary contractions

Figure 1. A graphical representation of the binary contractions

The graph for 
[Someone slept] after all substitutions The resulting tree for
[Someone slept] after the contraction

We have talked about how the inverse (filled) constructor should be interpreted as a constraint and how the graph we have produced satisfied it. Grail employs a mechanism of graph contractions to verify the constraints imposed by the inverse constructors. As said in the introduction, an inverse constructors deletes an open constructor. Figure 1 above gives a graphical representation of the graph contractions for NL.

All contractions are an instance of the same scheme: when a constructor and a destructor are connected at the two nodes of the destructor which are not connected to the arrow, respecting up and down and having the path labels then both constructor and destructor as well as the two nodes connecting them are eliminated from the graph. The nodes labeled H and C in Figure 1 above, that is the node to which the arrow was pointing and the remaining node of the open connection (with the same path label as the node with the arrow), are identified.

We can compare this contraction to a collision of a particle, such as an electron, with an anti-particle, such as a positron, in physics: the two are annihilated leaving only a photon. In our case the intransitive verb of nodes 6, 7 and 8 in the figure above collides with the intransitive anti-verb of nodes 3, 4 and 5 and both are annihilated.

After the substitution phase, Grail allows you to select which contractions to perform. Often, there is only a single possibility but in more complicated examples there can be a choice between multiple possibilities. Grail will mark auxiliary constructors which are active, that is, ready to be contracted, with the color blue. Just turning blue, however, does not guarantee the subgraph is in the proper configuration to be contracted: it is just an indication that we have enough information at this stage in the parse to decide whether it can be contracted or not.

Grail should show a figure similar to the one displayed here: one filled constructor, which is active and connected to an open constructor. You select which constructor to contract by indicating the node to which the arrow is pointing, node 3 in our case. Select this node to see the effect of the contractions.

The resulting tree is shown in the figure on the right. If, for any reason, it is impossible to contract all inverse connections, then the parse fails.

You may have wondered: why all this effort, when we can just assign the category np to the word "someone" and produce the same final tree with less effort, ie. no contractions and only two substitutions? The answer is that from the point of view of semantics the lexical graph assigned here is better, since it takes into account that the quantifier "someone" takes scope at the sentence level. This will be explained further in the tutorial on semantics

More Examples of NL Graphs and Parses

In the previous example, we have seen the contraction for the auxiliary constructor the arrow left the connection by path 2. The other contractions follow exactly the same schema: when the arrow leaves the filled constructor by path 1, the nodes reached by the paths labeled 2 and 3 need to be attached to the same open connection.

This case is left-right symmetric to the previous case. Whereas the 2 contraction eliminated the immediate left daughter (reached by the path labeled 1) of the root of the tree (reached by the path labeled 3), the 1 contraction eliminates the right daughter node (reached by path label 2) of the tree the root of which is reached by the path label 3.

The figure below shown an example of where this contraction would be used.

Lexical lookup for the sentence [Lancelot is brave]

The lexical graph assigned to the word "is" has a filled constructor with the arrow leaving along path 1. In order to contract it needs to connect its negative n node 7 and its positive n node 8 to the same open connection by paths 2 and 3 respectively.

Another way to see this is that where the lexical graph for "someone" contained an auxiliary constructor which was a sort of anti-particle for for a verb phrase (or an intransitive verb) - cancelling out a vp - the lexical graph for is "is" contains an auxiliary constructor which is an anti-particle for a noun modifier.

The lexical entry for "brave" fills this role perfectly: it is looking for a noun to its right (node 11) to form another noun (node 10). By identifying nodes 8 and 10 as well as nodes 7 and 11 we obtain the subgraph we need to perform the contraction.

Try this yourself by performing these two substitutions and verify that the two constructors are properly connected to perform a contraction. The auxiliary constructor turns blue to indicate the possibility of performing a contraction. However, before we can perform the contraction we must first perform the final two substitutions.

Connecting the np nodes 1 and 4 and the s nodes 5 and 12 will give us the graph shown below on the left.

The previous sentence after all
substitutions have been performed The final tree after the
contraction

The contraction selection window will open and it will offer you the possibility to perform the contraction, deleting the two entangled connectors and identifying nodes 6 and 9. The final tree is shown in the figure above on the right.

Try parsing the additional examples in the NL section of the grail0.pl grammar. They illustrate the use of adverbs (nearly, quickly) and reflexives (himself, which has two auxiliary constructors).

Exercise 1.3 According to linguistic conventions starred examples are ungrammatical, so verify that Grail does not find a parse for the sentence

1. *The swallow is unladen african.

Why does the contraction fail in this case?

A second example to remark is the sentence.

2. Robin nearly wet himself.

Here, when looking at the possible substitutions there seem to be two parses possible, even though it is possible for perform all contractions for only one of these possible parse attempts. What causes the final contraction to fail in the other parse attempt?

What's Next

Now that all the basics are in place, it is time to start editing the grammar, to extend the lexicon and experiment with some of your own example phrases.

Alternatively, you can learn more about how Grail's lexical graphs correspond to the formulas of the non-associative Lambek calculus. This has the added benefit of allowing you to edit your grammar files directly.

Finally, you can decide to explore some of the extensions to NL and see how they are implemented in Grail.


Richard.Moot@labri.fr
Last modified: Wed Jun 10 17:13:02 CEST 2009