[Overview] [Previous] [Next]

Grammars for Exhaustive Parsing

The idea of exhaustive search parsing for a string w is to generate all strings of length not greater than |w|, and see whether w is among them. To ensure that the search is finite, we need to make sure that we can't get into an infinite loop applying productions that don't increase the length of the generated string.

Note: for the time being, we will ignore the possibility that empty string is in the language.

Suppose we make the following restrictions on the grammar:

With these restrictions,

Copyright 1996 by David Matuszek
Last modified Mar 3, 1996