Next: Important Properties of Up: The New Algorithm Previous: A DCG Implementation
An Example
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.
Next: Important Properties of Up: The New Algorithm Previous: A DCG Implementation
Gertjan van Noord
Thu Nov 24 18:39:44 MET 1994