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.
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
.
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
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).
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"
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 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).
Substitution
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.
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.