We turn now to a simple example to provide a flavor for the order of
processing pursued by this generation algorithm. The grammar fragment in
Figure 1 uses an infix operator `/` to separate syntactic and
semantic category information. Subcategorization for complements is performed
lexically.

Consider the generation from the category
`sentence/decl(call_up(john,friends))`

. The analysis tree that we
will be implicitly traversing in the course of generation is given in
Figure 2. The rule numbers are keyed to the grammar.
The pivots chosen during generation and the branches
corresponding to the semantic head relation are shown in bold face.

We begin by attempting to find a non-chain rule that will define the
pivot. This is a rule whose left-hand-side semantics matches the root
semantics `decl(call_up(john,friends))`

(although its syntax may
differ). In fact, the only such non-chain rule is

We conjecture that the pivot is labeled
`sentence/decl(call_up(john,friends))`

. In terms of the tree
traversal,
we are implicitly choosing the root node [a] as the pivot. We
recursively generate from the child's node [b], whose category is
`s(finite)/call_up(john,friends)`

. For this category, the pivot
(which
will turn out to be node [f]) will be defined by the non-chain rule

(If there were other forms of the verb, these would be
potential candidates, but would be eliminated by the
`chained_nodes`

check, as the semantic head relation requires identity of the verb form
of a sentence and its VP head.) Again, we recursively generate for all
the nonterminal elements of the right-hand side of this rule, of which
there are none.

We must therefore connect the pivot [f] to the root [b]. A chain rule whose semantic head matches the pivot must be chosen. The only choice is the rule

Unifying in the pivot, we find that we must recursively
generate the remaining RHS element `np(_)/friends`

, and then
connect the left-hand side node [e] with category

to the same root [b]. The recursive generation yields a node covering the string ``friends'' following the previously generated string ``calls''. The recursive connection will use the same chain rule, generating the particle ``up'', and the new node to be connected [d]. This node requires the chain rule

for connection. Again, the recursive generation for the
subject yields the string ``John'', and the new node to be connected
`s(finite)/call _up(john,friends)`.
This last node connects to the root [b] by virtue of identity.

This completes the process of generating top-down from the original
pivot `sentence/decl(call _up(john,friends))`.
All that remains is to connect this pivot to the original root.
Again, the process is trivial, by virtue of the base case for
connection. The generation process is thus completed, yielding the
string ``John calls friends up''. The drawing summarizes the
generation process by showing which steps were performed top-down or
bottom-up by arrows on the analysis tree branches.

The grammar presented here was perforce trivial, for expository reasons. We have developed more extensive experimental grammars that can generate relative clauses with gaps and sentences with quantified NPs from quantified logical forms by using a version of Cooper storage [3]. We give an outline of our treatment of quantification in Section 6.2.

Thu Nov 24 18:39:44 MET 1994