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.
Figure 1. A graphical representation of the binary contractions
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
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.
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?
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.