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:
Systematic approaches are easy to find.
Almost any exhaustive search technique will do.
- A systematic approach, so that we know we haven't
overlooked any strings, and
- 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.
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