Grail Tutorial - AB grammars, Lexical Trees and Substitution

The tutorial on AB grammars assumes you have loaded the grammar grail0.pl. We will start with the simplest possible grammars: AB grammars, named after the pioneering work of Ajdukiewicz (1935) and Bar-Hillel (1964), and gradually introduce more and more of Grail's features.

Lexical Trees

As we have seen in the previous section, we can open the lexicon window either by pressing the [Lexicon] button or by selecting [Window/Lexicon Window] from the menu bar. The lexicon window displays an alphabetic list of the words in the lexicon of the current grammar. The atomic lexical graph for [Arthur]

Select the word "Arthur" from the lexicon. The graph assigned to it should look as shown in the figure. The number 1 is just a unique reference to a node in the graph and will be used to select nodes during interactive parsing. "Arthur" is assigned the basic category np, for noun phrase. Generally, Grail will display hypotheses (sometimes called negative or input nodes) above the node number and conclusions, (sometimes called positive or output nodes) below it. With this in mind, the meaning of the lexical graph for "Arthur" becomes: if we use the word "Arthur" we can conclude an np. That is to say, the word "Arthur", just by itself, can occur anywhere in our grammar where we are looking for an np.

The complex lexical graph for the
transitive verb [dismembers] Select the transitive verb "dismembers" from the lexicon. Again, the graph should look as shown in the figure. This time, we have a complex lexical entry which is a binary branching tree.

In categorial grammars, there is no explicit category for verbs. A verb tells us explicitly which types of arguments it is looking for. The intuition for the transitive verb shown is that it takes a noun phrase to its left and a noun phrase to its right to produce a sentence.

The open circles are connections (sometimes called links or constructors) between the nodes in the tree: each link connects three nodes, with three different paths leaving the central circle. These paths are labeled 1, 2 and 3. In this case, the tree structure is clear from the figure without these additional path labels: 1 is the left daughter, 2 is the right daughter and 3 is the mother node. For example, the bottom link connects node 2,3 and 4, with node 4 being the parent node (path 3 from the central circle), node 3 being the left daughter (path 1) and node 2 being the right daughter (path 2). As the graphs grow more complicated, Graphviz may decide that the graph can be better displayed by switching the positions of the nodes.

For the moment, we simply have a binary tree with three leaves (3, 1 and 5, in that order) and root node 4. Remember that hypotheses are portrayed above the node number and conclusions below it. So the lexical entry for "dismembers" has three hypotheses (the leaves 3, 1 and 5) and one conclusion node 4. This should be interpreted as: if we have a lexical hypothesis "dismembers" and two noun phrases, then we can conclude that the word dismembers combined with these two np's is a sentence s. Or, in other words: the word "dismembers" is looking for two noun phrases (its inputs) to produce a sentence (its output).

What's more, the transitive verb specifies the position of these two noun phrases in its lexical tree. One noun phrase will be the sister of the lexical leaf "dismembers" and will occur to its right: this will be the object of the phrase. The other noun phrase will be the left sister of the final sentence, and therefore occur directly to the left of subtree 2 which corresponds to the verb phrase "dismembers object" (for some object). So the final sentence will be of the generic form "subject dismembers object" (for given subject and object noun phrases).

Substitution

The lexical trees for [Arthur] and [dismembers] together in the same Figure The operation of substitution cancels out a hypothesis against a conclusion. So, for example, if we have a tree with conclusion a and another tree with hypothesis a we can cancel out the hypothesis and conclusion against eachother by identifying the two nodes.

In other words if we have a noun phrase (as output) and we are looking for a noun phrase (as input) then the noun phrase we have can fulfill the role of the noun phrase we are looking for.

Returning to our two previous lexical entries, when the occur in the same sentence, it will look as shown in the figure. The two lexical entries are the same as in the figures above up to a relabeling of the node number for the entry for "dismembers". Given that node 1 is already used for "Arthur", the nodes of the second tree are labeled starting from 2. In general, node numbers provide unique references to the nodes of the graph.

Now, given that "Arthur" provides a noun phrase whereas "dismembers" is looking for two noun phrases, we can combine these two trees by substituting node 1 (for "Arthur") either for the node 4 (the subject), in which case we will derive "Arthur dismembers object" or for node 6 (the object), in which case we will derive "subject dismembers Arthur" Substitution of the np node 1 [Arthur] for np node 4

The image on the left shows the result of substituting "Arthur" for the subject. The only difference with the previous figure is that node 4 has been replace by node 1. The two np's, which where the conclusion of the "Arthur" lexical tree and the leftmost hypothesis of the "dismembers" lexical tree respectively, have both been eliminated: we have found one of the np's we were looking for. The result of the substitution operation is a tree still looking for an object noun phrase to obtain a sentence.

What's Next

Lexical trees and the substitution operation provide us with the objects and the operation we need to parse AB grammars, which will be the subject of the
next section.

We will extend the lexical trees to lexical graphs in order to parse grammars for the non-associative Lambek calculus afterwards. But it is important to first get a feel for parsing AB grammars interactively with Grail.


Richard.Moot@labri.fr
Last modified: Sat Feb 21 00:40:12 CET 2009