[Overview] [Previous] [Next]

Exhaustive Search Parsing

The basic idea of exhaustive search parsing is this: to parse a string w, generate all strings in L and see if w is among them.

Problem: L may be an infinite language.

We need two things:

  1. A systematic approach, so that we know we haven't overlooked any strings, and
  2. A way to stop after generating only a finite number of strings -- knowing that, if we haven't generated w by now, we never will.
Systematic approaches are easy to find. Almost any exhaustive search technique will do.

We can (almost) make the search finite by terminating every search path at the point that it generates a sentential form containing more than |w| terminals.

Copyright © 1996 by David Matuszek
Last modified Mar 2, 1996