In order to overcome the restriction of semantic monotonicity and to achieve a goal-directed generation strategy [Shieber et al. 1989] proposed a new generation algorithm, called the semantic head-driven generation algorithm (, for short) which has later been extended to parsing by [VanNoord1993]. A similar head-driven algorithm has been developed by [Calder et al. 1989], however, restricted to use in unification-based categorial grammatical frameworks (cf. [Uszkoreit1986a], [Zeevat et al.1987]).
The basic motivation behind is that generation from some semantic expression can only by directed properly if the semantic information in itself is used to direct the traversal of possible derivations. But then, a strict left-to-right processing regime cannot be used because the semantic head element (i.e., that element of the body of a rule that shares the semantics with the head) need not necessarily be the leftmost one. Consider for instance the subcategorization rule introduced in the previous paragraph. In this rule, the second element of the right-hand-side (the VP element) shares its semantics with the left-hand-side. Thus, for generation it would be more appropriate to choose and complete this element first before the first element of the right-hand-side is processed, because the head element provides important information for its `argument'. To be able to get this kind of goal-directedness [Shieber et al. 1989] proposes a semantic-head-first selection rule in the case of generation.
For the identification of possible semantic heads, a
subset of the rules of a grammar is distinguished, called the
chain rules, in which the semantics of some right-hand-side element is
identical to the semantics of the left-hand-side. This right-hand-side
element is called the semantic head element.
All remaining rules are called non-chain rules. The separation of the rules of a grammar is motivated by the notion of the pivot node. The pivot node is defined to be the lowest node in the derivation tree such that it and all higher nodes up to the root have the same semantics. Intuitively, the pivot serves as the semantic head. Note that the pivot itself does not have a semantic head, since otherwise, it would not fit the definition. Typically, pivots will be lexical items, but in principle any un-headed phrase can serve as a pivot (e.g., idioms or conjunctions).
Using this characterization, the traversal realized by will proceed both top-down (when processing non-chain rules) and bottom-up (when processing chain-rules) from the pivot. The algorithm then can be summarized as follows: Starting from the goal semantic expression (called the root), a rule is selected whose left-hand-side unifies with the semantics of the root. If a chain rule has been applied, the semantics is passed unchanged to the corresponding semantic head element, this latter non-terminal becomes the new root and the algorithm is applied recursively. If on the other hand a non-chain rule has been chosen, the algorithm is applied recursively on each element of the right-hand-side in a left-to-right scheduling. After a non-chain rule has been completed (i.e., a pivot has been identified) a bottom-up step is applied that connects the pivot to the initial root along with all intermediate nodes using a series of appropriate chain-rules. After a chain rule is chosen to move up one node in the tree being constructed, the remaining elements of the right-hand-side of this rule must be generated recursively, which is done by using a leftmost scheduling.
To clarify the strategy by means of an example, suppose that we start generation from the semantic expression `loves(john, mary)' using the following set of rules (using Shieber et al.'s framework):
Starting with `sentence/decl(loves(john, mary))' rule (1) is the only possible candidate to choose. To complete this rule, rule (2) has to be chosen. The body of this rule contains two elements, so there is a choice point. However, because only the second element shares its semantics with the left-hand-side this element has to be chosen and to be completed, before the first element is processed. The next possible rules to choose are (3) and (4). If (4) is considered first, further expansion of this rule will fail, because there is no lexical entry in the grammar that can unify the body of (4). In this case backtracks to the choice point of (4) and chooses (3). Note that rule (3) extends the subcategorization list of the head element. However, applying this rule causes a recursion involving the rules (3) and (4). Now, (4) can be chosen which application will select the lexical entry (5). Now, the bottom-up step can be applied, which tries to connect the lexical entry with the initial root. During the application of this step, firstly, the semantic expression `mary' will be realized as an object np and secondly, `john' will be realized as the subject. The last step then will connect instantiated rule (2) with (1). The resulting string is `john loves mary'.
The algorithm as it is described in [Shieber et al. 1989] and [VanNoord1993] is specified as a meta-interpreter for Prolog, where Prolog's backtracking mechanism is used for maintaining alternatives. Potential nondeterminism exists in two places (see also [Gerdemann1991]), namely when the choice of a pivot is not determined (e.g., in the case of lexical choice) or in the case of the selection of non-chain rules for phrasal pivots. This latter case is crucial because for non-chain rules the order of processing the elements of the right-hand side of a non-chain rule is not determined so that applies itself recursively in a simple left-to-right order.
The most serious problem of , however, is that the top-down
processing of non-chain rules can lead to non-termination (see also
[Gerdemann1991]). For example consider the following
rule:
nbar/N 
nbar/N, sbar/N
This rule can effect nontermination, if the generator chooses the
second element
of the body first. Clearly, if we could define a head-driven
Earley style algorithm, these problems would easily be avoided, and in
fact, this has been done by [Gerdemann1991], which we will discuss
in the next paragraph.
However, before we move to Gerdemann's approach we have some remarks on head-driven parsing, preliminary to discussing issues of uniformity underlying .
For parsing, algorithms have also been developed, that favour a head-driven processing regime, most notably [Kay1989, VanNoord1993]. Both approaches are modifications of left-corner parsers [Matsumoto et al. 1983], such that instead of choosing the leftmost element of the body of a rule the parser selects the lexical head first (actually, the parser selects a lexical entry and continues to prove that this lexical entry indeed is the head of the goal, by selecting a rule of which this lexical entry can be the head). The other rules are then parsed recursively, and the result constitutes a slightly larger head. This process can be applied iteratively, until the head dominates all words of a string. Because the bottom-up approach is head-oriented, these algorithms are also denoted as head-corner parsers.
The algorithm described by [VanNoord1993] is closely related to , so that both approaches can be seen as a uniform framework for reversible grammars. Although both algorithms are very similar, Van Noord does not try to combine both, in order to obtain one uniform parameterized approach. Furthermore, it is not clear whether one and the same grammar can be used efficiently in both directions without the need of compilation. In fact, [Martinovic and Strzalkowski1992] give an example of a grammar that can be used efficiently for parsing, but which causes a nondeterministic overhead when directly processed by . The problem they focused on is that the left-to-right selection strategy might in the case of non-head elements select an element which is not ``ready'', i.e., whose semantics is still un-instantiated. The only way to avoid such problems for would be to rewrite the underlying grammar, so that the choice of the most instantiated literal on the right-hand-side of a rule is forced. However, this can cause a ``ping-pong'' effect, because now, it is not guaranteed that the parsing mode will handle this grammar in the same efficient manner as before.