Next: Other strategies Up: Constraint-Based Categorial Grammar Previous: The distribution and
Processing
The introduction of recursive lexical rules has repercussions for processing as they lead to an infinite number of lexical categories for a given lexical item or, if one considers lexical rules as unary syntactic rules, to non-branching derivations of unbounded length. In both cases, a parser may not terminate. One of the main advantages of modeling lexical rules by means of constraints is that it suggests a solution for this problem. A control strategy which delays the evaluation of constraints until certain crucial bits of information are filled in avoids non-termination and in practice leads to grammars in which all constraints are fully evaluated at the end of the parse-process.
Consider a grammar in which the only recursive constraint is add_adjuncts, as defined in section 2.2. The introduction of
recursive constraints in itself does not solve the non-termination problem. If
all solutions for 
are simply enumerated during lexical
look-up an infinite number of categories for any given verb will result.
During processing, however, it is not necessarily the case that we need to consider all solutions. Syntactic processing can lead to a (partial) instantiation of the arguments of a constraint. If the right pieces of information are instantiated, the constraint will only have a finite number of solutions.
Consider, for instance, a parse for the following string.
Even if the category of the verb is left completely open initially, there is only one derivation for this string that reduces to S (remember that the syntax uses application only). This derivation provides the information that the variable Verb must be a transitive verb selecting one additional adjunct, and with this information it is easy to check whether the following constraint is satisfied:
This suggests that recursive constraints should not be evaluated during lexical look-up, but that their evaluation should be delayed until the arguments are sufficiently instantiated.
To implement this delayed evaluation strategy, we used the block facility of Sicstus Prolog. For each recursive constraint, a block declaration defines what the conditions are under which it may be evaluated. The definition of add_adjuncts (with semantics omitted for readability), for instance, now becomes:
We use add_adjuncts/2 to extract the information that determines when
add_adjuncts/3 is to be evaluated. The block declaration states
that add_adjuncts
may only be evaluated if the third argument (i.e.
the argument of the `output' category) is not a variable. During lexical
look-up, this argument is uninstantiated, and thus, no evaluation takes place.
As soon as a verb combines with an argument, the argument category of the verb
is instantiated and add_adjuncts will be evaluated. Note, however,
that calls to add_adjuncts are recursive, and thus one evaluation
step may lead to another call to add_adjuncts, which in its turn will
be blocked until the argument has been instantiated sufficiently. Thus, the
recursive constraint is evaluated incrementally, with each syntactic application
step leading to a new evaluation step of the blocked constraint. The recursion
will stop if an atomic category S is found.
Delayed evaluation leads to a processing model in which the evaluation of lexical constraints and the construction of derivational structure is completely intertwined.
Next: Other strategies Up: Constraint-Based Categorial Grammar Previous: The distribution and
Gertjan van Noord
Fri Nov 25 16:22:41 MET 1994