It turns out that performing revision during generation of an utterance using the uniform algorithm is not that difficult as it might be at a first glance.
Recall that the uniform algorithm keeps track of partial (complete or incomplete) results using an agenda and a chart. The agenda is used to maintain all newly created items before they are added to the chart. The selection strategy used by the agenda determines in which order the items are added to the chart. Following a depth-first strategy, for instance, then only those items are considered that eventually can contribute to the complete generation of the first possible utterance. All remaining alternative items are only added to the chart in the case that additional paraphrases are requested, e.g., when all possible strings of a given semantic expression shall be computed.
If an item has been added to the chart, the different inference rules are applied which eventually creates new items which are then added to the agenda. But note that only those created items which have been added to the agenda will be considered during further computation. By means of this ``built-in'' mechanism revision can be performed as follows: Suppose that we have deduced a new passive item p. This means that we have computed a new partial string. If p is added to the chart, by means of passive completion it is checked whether p can reduce an active item a. Then, before a is actually be reduced using p it is checked whether p causes an ambiguity using an appropriate context.
Only if no ambiguity can be determined, the reduction of a is performed and the resulting new item is added to the agenda. On the other side, if an ambiguity is recognized, then reduction will not be performed, and as a consequence no new item is created. This implies for a, that reduction of its selected element will only be performed if there is another alternative for p available on the agenda (or items which lead to the computation of the alternative). However, this alternative item will automatically be added to the chart by the agenda at some later point. In some sense, this kind of processing means that the selected element has implicitly been marked, and the agenda will choose an alternative item which corresponds to a selection of an alternative rule.
If no alternative for p can be deduced (i.e., either no further alternative exists, or no unambiguous alternatives exist), then a will never be completed. However, this means that the agenda automatically will add an alternative item of a (if present) to the chart, which then might be combined with p. Note that this reduction would be performed by active-completion, and hence, would reuse results of previously made computations. If this is the case, the marker of p implicitly has been pushed one level up. Since, the whole process is performed recursively, it might be the case that markers are pushed implicitly up to the initial root node. However, in all cases, we can benefit from the results of previously made computations.
We will use our pp-attachment example at that place to clarify the strategy. We are assuming the following simple grammar:
We assume that these rules are added to the agenda according to the order in which they are specified in the grammar. Using a depth-first selection strategy for the agenda, rule 2. is processed before 3. At some point the pp is produced, and will be used by passive completion to reduce an instance of rule 2. However, before the pp of vp is reduced, the string of the np is used as context for checking whether the pp causes ambiguity. Therefore, we parse the string of np-pp, and actually detect an ambiguity. For the pp, however, we have no further alternatives available on the agenda, so rule 2. cannot be reduced completely, i.e, for that rule the inference rules cannot create items to put on the agenda. However, the agenda mechanism guarantees that rule 3. will be selected. Reducing rule 3. by means of active-completion will first use the pp for reduction, assumed without ambiguity problems. Next the np should be used for reduction. Before that, however, the string of pp-np is monitored, which however cannot be parsed, and hence no revision is necessary. Thus, rule 3. will be reduced by the np to give a completely reduced vp, which then is used for reduction of rule 1.
Based on the observations made above, we can adapt the uniform algorithm for performing revision in the following way, assuming that we already know how to detect ambiguities in the incremental mode (how this is actually be performed is given in the next section): Revision should only take place if there exists a passive item which can be used for reducing an active one. Thus, we only have to consider revision for the inference rules ACTIVE-COMPLETION, SCANNING, and PASSIVE-COMPLETION, whose indexed versions can be found in section 4.10 of chapter 4.
In all three cases we add a further conditional statement around the body of the for all loop, namely that the body should only be evaluated if revision is not requested. For example, the PASSIVE-COMPLETION rule is changed as follows (only the relevant parts are expressed explicitly):
In the relevant part of the new code we have added a new line (4),
which says that the next operations (i.e., putting a just reduced active
item on the agenda) will only be performed if the monitor mode is switched on
(which is done by using a global variable MONITOR?, whose boolean
value indicates whether processing should be performed with or without
incremental monitoring) and if no revision has taken place, which is
determine by the predicate REVISION_P.
In the same manner ACTIVE-COMPLETION and SCANNING are modified. The definition of REVISION_P is as follows:
revision_p(AL,PL):
extended-string := get_context(AL,PL,n);
if extended-string
then
parsed_result := parse(extended-string)
if and(parsed_result,ambiguous(AL,parsed_result))
then TRUE
else FALSE
fi
else FALSE
fi.
The contextual information is determined by means of the function GET_CONTEXT. If so, the parser is called with the extended-string, built inside GET_CONTEXT, using a look-back of n, which value is set globally. To be more precise, first a new string is computed on the basis of the context and the passive item's string, and then the parser is called. Only if the parser successfully obtained one or more readings and if the result is ambiguous should revision take place.
Note that the way the uniform algorithm maintains the agenda and the chart, the incremental method ``simulates'' marking and revision of generated derivation trees as is done explicitly by the non-incremental method. However, marking is done implicitly -- it is just a side effect of the uniform algorithm by not creating items which could cause ambiguity problems. Furthermore, because monitoring is applied on intermediate results, it is actually performed incrementally.