We now present an interpreter for definite clauses that performs according to Earley deduction. Instead of collecting all grammar rules and lexical entries in one data structure, we will use two separate data structures G, which keeps all grammar rules and Lex, which holds all lexical entries.
PREDICTION is used to predict instantiations of grammar rules. Completion will be performed by three inference rules, namely PASSIVE-COMPLETION, ACTIVE-COMPLETION, and SCANNING. In all three cases, unit clauses will be used to reduce appropriate non-unit clauses, where the scanning rule can be seen as a special active-completion rule in the sense, that is looks for unit clauses of the lexicon which it uses to reduce the non-unit clause in question.
We will use S to denote the state set, to which new lemmas are dynamically added. However, instead of directly storing lemmas into the table, new lemmas are stored in an agenda where the lemmas are sorted according to a given priority. Thus lemmas are added to the table according to their priority. However, since the inference rules can generate new lemmas which are inserted to the agenda before they are added to the table, we can use the agenda mechanism to model depth-first, breadth-first and even best-first strategies. Another advantage of using an agenda mechanism, is that the subsumption test to see whether an item is already in the table, is needed only when the item should be added to the table. In the case, where we only want to yield one result instead of all possibilities, the subsumption test has to be performed only for those items which are actually added to the table. Thus, if we follow a depth-first strategy the number of items to be inserted into the table is less than those which had been inserted to the agenda (if we are only interested in one result).