Next: BUG: a Directed Up: Problems with existing Previous: A major problem
Bottom up generators
The only bottom up generator I currently know of is the one
proposed in Shieber 1988.
In Shieber's generator rules are applied in a bottom up
fashion. Results are kept on an Earley type chart. To make
this process goal driven there is a restriction that the
semantics of every subphrase that is found must subsume some
part of the original semantics (the input). This restriction
results in the
semantic monotonicity
requirement on grammars; this restriction requires that
the semantics of a part of a derivation must subsume part of the
semantics of the complete derivation.
An example will clarify the strategy. Assume we want to generate
a string for the semantic formula <4> with a
grammar comparable to sample grammar 3 of Shieber 1986
.
As the generator starts it will try to select rules (and lexical entries). First it can select lexical entries that subsume part of <4>. The lexical entries 'john', 'mary', 'kiss' will be put on the chart as they subsume part of <4>. A NP can be constructed dominating 'john' and another one dominating 'mary'. A VP dominating 'kiss' will be constructed as well. Now a rule similar to <2> can apply, resulting in a VP with the semantics as in <5>.
At last a rule applies that combines the NP dominating 'john' and the VP dominating 'kiss' and 'mary' resulting in the sentence 'john kisses mary' (ignoring inflection for the moment) with semantics <4>. Note that no other rules can apply if their resulting semantics does not subsume part of the original semantics. In the foregoing example it is e.g. not possible to apply a rule to construct a PP 'to mary' or anything similar to that.
The requirement that every rule application yields a semantics 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."For the moment I will assume that semantic monotonicity is too strong. In the following section I will introduce an alternative generator, BUG, that uses a different constraint on grammars. In section 3 I will discuss some analyses of prepositional verbs and idioms that are not semantically monotonic but can be handled by BUG. Furthermore I will give some evidence that suggests that BUG "allows efficient programming".
Next: BUG: a Directed Up: Problems with existing Previous: A major problem
Gertjan van Noord
Fri Nov 25 13:48:52 MET 1994