next up previous contents
Next: Use of a restrictor Up: Overview of Earley Deduction Previous: Overview of Earley Deduction

Blocking new lemmas

As already suggested, a new lemma is only added to the state set if no subsuming clause exists in the table (i.e., one which is more general than the newly derived clause). If a new lemma cannot be added to the state set because a more general one already exists, then the lemma is said to be blocked.

The subsumption check is necessary, because we are dealing with instantiations of clauses, not with the clauses directly (as it is the case for context free versions,where it suffices to check whether the same grammar rule has already been predicted). Hence, to avoid the repeated prediction of the same program clause, we have to check whether a more general prediction has already been made. In this case a newly predicted more specific one can just be ignored. In a similar way, we can take advantage of the subsumption check to avoid redundant re-computation of completed lemmas during the completion step. This means, for instance, that once a passive lemma has been derived it can be used for further completion of different active lemmas, without redundant re-computation (in section 4.8, we will show how we can combine this technique with a clever indexing mechanism that is used for parsing and generation).



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