The first and most prominent attempt to specify a uniform
architecture for parsing and generation has been made in
[Shieber1988]. In particular, Shieber proposed an architecture
inspired by the Earley deduction work of [Pereira and Warren1983]
(which we will describe in section 4.1 in more detail)
but which generalized that work allowing for its use in both a parsing
and generation mode by instantiating only a small set of parameters.
As shown in his work, the two basic inference rules of Earley
deduction, namely prediction and completion can be used in the same way
for parsing and generation. The advantage of using this kind of
computational logic specifically for generation is that generation from
grammars with recursions whose well-foundness relies on lexical
information will terminate (e.g., lexicalized grammars like
[Pollard and Sag1987], where only the
verbal lexical entries carry subcategorization information). This is
actually an improvement of simple top-down generation regimes like the
one described in [Wedekind1988] or [Dymetman and
Isabelle1988] which
do not terminate in such cases. For these approaches the following
rule will cause recursion problems, because the rule forces the
subcategorization list SC to be expanded as long as a lexical entry
that restricts the length of this list cannot be found,
but the lexical entry will never be found as
long as the recursion occurs:
The problem is that the rule
does not specify any finite length of the subcategorization list.
Thus, this rule causes the
same termination problem for generation as the well-known
left-recursion problem for parsing. Using an Earley style strategy, this
problem can be solved, because lexical information is available
immediately. However, the Earley style uniform approach described in
[Shieber1988] has the following two major problems for generation:
The first issue is a consequence of the fact that Shieber defines the
inference rules and the meaning of items strictly based on Earley's
original work on parsing algorithms [Earley1970].
This means that in Shieber's approach,
the inference rules - prediction and completion - follow a leftmost
selection strategy and items are defined according to the position of
the endpoints of the string of a completed sub-phrase.
Clearly, at least in the case of a context-free backbone, parsing benefits from this characterization, but adapting this ``parsing view'' also for the case of generation causes at least the following two problems. Firstly, the left-to-right selection strategy is inherently more appropriate for parsing than for generation, because in the latter case this can cause a large amount of redundancies. For example, if a rule specifies that a noun phrase occurs to the left of a verb phrase then many nondeterministic possibilities for generation a noun phrase have to be explored (e.g., different cases) before the verb is generated that would restrict some of the alternatives.
The second, more important problem with a strict left-to-right
selection is that
generation cannot take advantage of the indexing based on string
position, because the string is the output of a generator, not the
input, of course. Shieber's conclusion to this problem is just to ``remove the
feature of tabular parsing methods such as Earley's algorithm that
makes parsing reasonably efficient.'' ([Shieber1988], page 617).
However, to entertain a goal-directed strategy for generation
he expresses the following restriction, which directly
turns our attention to the second major problem of
Shieber's uniform approach: The meaning
associated with an item must subsume some portion of the goal meaning.
This restriction results in the semantic monotonicity
requirement on grammars. This restriction requires that for every phrase
admitted by the grammar the semantic structure of each immediate
sub-phrase must subsume some portion of the semantic structure of the
entire phrase.
But then, any item which does not subsume some part of the goal meaning can
safely be ignored. For example suppose we start generation from the
logical form
`passionately(love(sonny,kait))'. Furthermore, assume that the lexicon
contains entries with meaning `passionately', `love',
`sonny' and `kait' then a grammar is semantic monotonic if phrases with
meaning `sonny', `kait', `love(sonny,kait)' and
`passionately(love(sonny,kait))' will be constructed during the
generation process.
Hence, for grammars that exhibit the semantic monotonicity property, Shieber's algorithm results in a complete generator. However, as stated by Shieber himself, this requirement is too strong because it does not allow generation of idiomatic expressions like `Peter macht ein Nickerchen' with logical form 'nickerchenmachen(peter)' or expressions involving particle verbs like `das Treffen findet morgen im DFKI statt' with logical form `morgen(stattfinden(treffen, DFKI))'.