Next: Head driven bottom-up Up: Problems with early Previous: Top-down generators and
Shieber's chart-based generator
In [21] Shieber proposes a chart-based generator where rules are applied in a bottom up fashion. Results are kept on an Earley type chart. To make this process goal driven there is only one restriction: the logical form of every subphrase 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. An example will clarify the strategy. Assume we want to generate a string for the logical form
with grammar 2.1. As the generator starts it will try to select rules without any daughters (as the chart is still empty) whose logical form subsume part the input logical form.
First it can apply the rules 
, 
, 
and 
. After
entering these entries on the chart the noun phrases and
can be built. Now
a VP dominating and will be constructed as well,
resulting in a VP with the logical form
Finally a rule applies that combines the NP dominating and
the VP dominating resulting in the sentence
with the required logical form.
Note that no other rules can apply, because their resulting logical form
does not subsume part of the original logical form.
The requirement that every rule application yields a logical form that subsumes part of the input only results in a complete generator if the grammar is semantically monotonic. Shieber himself 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 2.1 is not semantically monotonic, because it can assign the logical form
to the sentence 
. Note that the logical form
of the particle does not subsume any part of the resulting logical form
(
is an identifier without any internal structure).
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'. Furthermore
analyses of idioms usually will be semantically non-monotonic. As an example
consider the case where a sentence like john kicks the bucket has
a logical form 
.
Another disadvantage of this 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 subsumption checks (for example to check whether a result already is present in the chart) lead to much processing overhead. These efficiency considerations also led to the head driven bottom-up family of generators to be discussed in the next section.
Summarizing, 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.
Next: Head driven bottom-up Up: Problems with early Previous: Top-down generators and
Gertjan van Noord
Fri Nov 25 13:07:08 MET 1994