Shieber's chart-based generator

[83] proposes a chart-based generator where rules are applied in a bottom up fashion. Results are kept on an Earley type chart [19]. To make this process goal-driven, there is only one restriction: the logical form of every sub-phrase that is found, must subsume some part of the input logical form. This restriction results in the semantic monotonicity requirement on grammars. This restriction requires that the logical form of each daughter of a rule subsumes part of the logical form of the mother node of that rule. Note that this requirement also implements the coherence condition on the generation problem discussed in chapter 2: it is never possible that the generator comes up with an extension of the input semantic structure.

An example will clarify the strategy. Assume we want to generate a string for the logical form

$$\mbox{\rm omdat(vertelt(arie,leugens))}$$
with the Dutch example grammar, where I leave the empty verb, to analyze verb second constructions, out of consideration for the moment. When the generator starts, it will try to select rules without any daughters (i.e. lexical entries), because the chart is still empty. The logical form of these entries should subsume some part of the input logical form.

First it can apply the rules arie, leugens, vertelt and omdat. Next, a verb phrase dominating vertelt and leugens will be constructed as well, with the semantic structure

$$\mbox{\rm vertelt($\mbox{\rm Subj}$,leugens)}$$
A rule applies that combines the NP arie and the preceding verb phrase, resulting in the verb phrase arie leugens vertelt, with the logical form.

$$\mbox{\rm vertelt(arie,leugens)}$$

This verb phrase can be the input for the complementizer rule, together with the complementizer omdat, resulting in the subordinate clause omdat arie leugens vertelt. This complementizer phrase has the appropriate logical form. Note that no other rules can apply, because their resulting logical form does not subsume part of the input logical form (remember we did not take into account the empty verb).

The requirement that every rule application yields a logical form that subsumes part of the input only results in a complete generation algorithm only if the grammar is semantically monotonic. Shieber admits that this requirement is too strong (op. cit. section 7):

"Perhaps the most immediate problem raised by the methodology for generation introduced in this paper is the strong requirement of semantic monotonicity. (...) Finding a weaker constraint on grammars that still allows efficient processing is thus an important research objective."

In fact the grammar of the previous section is not semantically monotonic, because it analyses the Dutch idiomatic phrase `een dutje doen' as a predicate without any internal structure, although in the derivation the logical form `dutje' will be assigned to the noun phrase `een dutje'.

Another example of an analysis that does not obey the semantically monotonicity requirement may be encountered with particle verbs. As an example consider the case where a sentence like

has a logical form $$\mbox{\rm doorberekenen(jan,kosten)}$$
Other examples where semantic monotonicity is not obeyed are cases where semantically empty words such as `there' and `it' are syntactically necessary, and prepositional verbs such as `count on', as in the following examples.

Another disadvantage of Shieber's generator is the nondeterministic style of processing. The requirement, that only rules can be applied, of which the logical form subsumes some part of the input logical form, does not direct the generation process very much. Furthermore, the necessary subsumption checks (for example to check whether a result already is present in the chart) lead to much processing overhead.

Summarizing section 3.3, the principal problem of top-down generators is left-recursion. This problem is solved in a chart-based bottom-up generator at the cost of severe restrictions on possible grammars, and rather inefficient processing. These considerations led to the head driven bottom-up family of generators to be discussed in the next section.