As already noted in 4.1, completion will be split into three separate rules, namely passive-completion, active-completion, and scanning.
Passive-completion (see figure 4.2)
will be applied on passive items PL. For all active
items AL in S which selected element (AL) unifies with the head
of the passive item, the new lemma Red is [AL-(AL)], i.e., the
unified item AL minus its selected element (line (4)). The new item
NewItem (line (5)) is added to agenda Agenda (line (6)).
Since passive-completion reduces the body of
an active lemma it will transform it to a passive lemma by repeated
application. Furthermore, it performs the completion step bottom-up.
Figure 4.3: The procedure for active-completion.
Active-completion (see figure 4.3) is very similar to passive-completion. The basic difference is that active-completion will receive an active lemma AL and will search S for passive-lemmas PL that can reduce AL. Thus, active-completion performs the completion step in a top-down manner. Again, active-completion can transform an active lemma to a passive lemma by repeated applications.
Figure 4.4: The procedure for scanning.
Scanning has mainly been described from a parsing perspective in the sense, that it is limited to only scanning words that match the initial portion of the input. However, when the scanner should also be usable for generation it must be generalized such that it should be allowed to consider any lexical entry that will unify with the selected element of an active item. In a constraint-based approach the input is specified as part of the constraints. This allows us to describe scanning as a specific active-completion rule, namely the completion of an active item with possible matching unit clauses from the lexicon.
The scanning rule (see figure 4.4)
operates on a given active item AL and returns the boolean value
of Candidates?. The scanner searches through the lexicon to look for
lexical entries LE whose HEAD(LE) unifies with the selected
element of the active item, denoted as (AL) (line (3)).
For all successful instantiations, the new lemma Red is
[AL-(AL)], i.e., the unified item AL minus its selected
element is constructed (line (4) and (5)), and is then added as a new
task to the agenda. Thus, scanning also reduces an active item. Since,
the selected element has been determined on the basis of the value of
the essential feature, this also means that the scanner will consume portions
of the input on the basis of available and consistent lexical information.
We have not explicitly required that scanning should only be performed on terminal elements, i.e., active items, whose selected element belongs to a terminal category. The reason is, that in general constraint-based grammars are under-specified in this respect. For instance, in our example grammar some of the lexical and phrasal signs belong to the same category (e.g., vp, np) and they are only distinguished by the boolean feature LEX. However, most of the rules are under-specified with respect to this information. In that case we have to apply scanning and prediction on the same active item. Of course, if a grammar explicitly distinguishes between nonterminal and terminal elements (as it is the case for instance in ), we can easily restrict the application of the scanning rule to terminal elements and the prediction rule to nonterminal elements.