Although the tabular version described above already avoids redundant
recomputation because phrases just analysed (i.e., parsed or generated)
are stored in a table, the search for derived lemmas to resolve is not as
efficient as it could be. The problem is that all lemmas are kept
in one state set only. For the completor, this causes an
enormous overhead, since the whole state set has to be searched
through to look for active lemmas which can be reduced. In general,
this causes a large number of nonproductive (nonunifying) attempts at
applying the completion rule. Furthermore, for each added item the
blocking rule has to be performed on the whole set of items already in
S.
In order to overcome these disadvantages, the items in S should be ordered according to the structure of the actual problemsize (either string or semantics) such that the inference rules (and the blocking rule) need only be applied to an identifiable subset of the states in each state of the process. The different states of the process can then be defined relative to subsets of items. In this sense, the progressing process decomposes the state set into a set of internal item sets, which stand in a relationship according to the structure of the problem size.
For parsing, particular data structures have been developed for achieving such an efficient behaviour, most notably the chart developed by [Kay1986] and the item set notation developed by [Earley1970]. In both approaches the endpoints of a derived string are explicitly used for indexing stored phrases. Unfortunately, we cannot use these well-known approaches for generation directly, because the string is the output of a generator, not the input, of course. For generation, once a phrase has been constructed, we want be able to use it at various places.
We now present an indexing mechanism that can be used in the same manner for both parsing and generation. However, since we use the value of the essential feature for determining the ``content'' of internal item sets, the item sets are ordered according to the actual structure of the input. Note that only the selection function and this indexing mechanism have to be parameterized. However, since the only parameter is a certain feature and its value we had achieved a maximal degree of uniformity for parsing and generation under a task-orentied view.