The Algorithm

Semantic-head-driven generation makes use of the notion of a semantic head of a rule, a daughter whose semantics is shared with the mother. In semantic-head-driven generation, there are two kinds of rules: chain rules, which have a semantic head, and non-chain rules, which lack such a head. These two subsets are processed differently during the generation process.

Given a feature structure, called the root goal, to generate a string for, the generator builds a new feature structure that shares its semantic information (using the user-defined semantics predicate with the second argument instantiated) and finds a pivot that unifies with it. The pivot is the lowest node in a derivation tree that has the same semantics as the root. The pivot may be either a lexical entry or empty category (the base cases), or the mother category of a non-chain rule. Once a pivot is identified, one can recursively generate top-down from the pivot using non-chain rules. Since the pivot must be the lowest, there can be no lower semantic heads, and thus no lower chain-rule applications. Just as in parsing, the daughters of non-chain rules are processed from left to right.

Once top-down generation from the pivot is complete, the pivot is linked to the root bottom-up by chain rules. At each step, the current chain node (beginning with the pivot) is unified with the semantic head of a chain-rule, its non-head sisters are generated recursively, and the mother becomes the new chain node. The non-head daughters of chain rules are also processed from left to right. The base case is where the current chain node unifies with the root.

The following example illustrates this better. Suppose that the generator is given the goal description:

  (sentence,
   sem:(pred:decl,
        args:[(pred:call_up,
               args:[pred:mary,pred:john])]))

Figure 11.1: The initial root.

Figure 11.2: The semantics template.

Figure 11.1 shows the initial root (the most general satisfier of the input description); and Figure 11.2 shows the template that ALE uses to find a pivot. Next (Figure 11.3), a pivot is selected, in this case by unifying the template with the mother category of the non-chain rule, sentence1:

Figure 11.3: The first pivot is found.

sentence1 rule
  (sentence,sem:(pred:decl,
                 args:[S]))
  ===>
  cat> (s,form:finite,
          sem:S).

We can tell that sentence1 is a non-chain rule because it lacks a sem_head> daughter, unlike, for example, the chain rule s:

  s rule
  (s,form:Form,
     sem:S)
  ===>
  cat> Subj,
  sem_head>
    (vp,form:Form,
        subcat:[SUBJ],
               sem:S).

The only daughter of sentence1 becomes the new root.

The pivot chosen for that root is the lexical entry for calls, which is obtained by applying the lexical rule, sg3, to the first entry for call in the grammar. That pivot has no daughters, so it must now be connected by chain rules to the new root in Figure 11.3. The chain rule, vp1, is chosen, its semantic head is unified with the entry for calls, its one non-head daughter is recursively generated (which simply succeeds by unifying with the lexical entry for john), and its mother becomes the new chain node (Figure 11.4).

Figure 11.4: First chain rule application.

Again (Figure 11.5), chain rule vp1 is chosen, its semantic head is unified with the new pivot, its non-head daughter is recursively generated by unifying with the lexical entry for up, and its mother becomes the next chain node.

Figure 11.5: Second chain rule application.

Finally, the chain rule, s is chosen. Its non-head daughter is recursively generated by unifying with the lexical entry for mary, and its mother, the new chain node, unifies with the new root (Figure 11.6).

Figure 11.6: Third chain rule application and unification.

With generation below the pivot of Figure 11.3 having been completed, it is linked to its root directly by unification, yielding the solution, mary calls john up.