next up previous contents
Next: Implementation Up: Incremental Interleaving of Parsing Previous: Check ambiguity

Using Shared Items during Incremental Monitoring

The main advantage of the incremental method using the uniform algorithm described so far is that we benefit from the use of the chart during the monitored generation strategy, because also in that case we can reuse previously made computations. Since revision is automatically performed by the agenda mechanism of the uniform algorithm (by not creating items for those structures where an ambiguity as been detected), the main effort we have to spend to realize monitoring is the parsing operation performed on extended strings. (The determination of the contextual string is not a time critical operation.) We now show how the incremental monitoring method can be made more efficient by making use of the item sharing approach described in 4.15.

Recall that in the item sharing approach passive items that have been computed in one direction can directly be used in the other. Following the method described in 4.15 the uniform tabular algorithm maintains different agendas, item sets and active items for the parsing and generation mode, but passive items are shared during both directions. The object-oriented realization of the item sharing approach allows the parser (i.e. the parsing mode of the uniform algorithm) to be chart-based even when it is called inside the generator. Thus, if the parser is called via monitoring it can reuse previously self-made results at any stage.

By use of the item sharing approach partial results (i.e., passive items) are continually made available for the other direction. However, this means that for both directions it is the case that one direction can reuse results from the other directions. For example, for the interleaved parsing mode this means that it can reuse results computed through generation when making the ambiguity check. During this job, however, it can provide results for the generator of which the generator can make use. This means, that parsing results are used through generation and generation results are used through parsing in an interleaved mode.


next up previous contents
Next: Implementation Up: Incremental Interleaving of Parsing Previous: Check ambiguity

Guenter Neumann
Mon Oct 5 14:01:36 MET DST 1998