next up previous
Next: Minimality. Up: Discussion and Extensions Previous: Discussion and Extensions

Sound and Complete.

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