Next: Minimality.
Up: Discussion and Extensions
Previous: Discussion and Extensions
The algorithm as it is defined is sound and complete in
the usual depth-first, backtrack search sense. Clearly the parser may
enter an infinite loop (in case non branching rules are defined that
may feed themselves or in case a grammar makes a heavy use of empty
categories). However, in case the parser does terminate one can
be sure that it has found all solutions.
Noord G.J.M. van
1998-09-30