[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 is in the language.

Suppose we make the following restrictions on the grammar:

Every variable expands to at least one terminal. We can enforce this by disallowing productions of the form A.
Every production either has at least one terminal on its right hand side (thus directly increasing the number of terminals), or it has at least two variables (thus indirectly increasing the number of terminals). In other words, we disallow productions of the form AB, where A and B are both variables.

With these restrictions,

A sentential form of length n yields a sentence of length at least n.
Every derivation step increases either the length of the sentential form or the number of terminals in it.
Hence, any string w L can be generated in at most 2|w|-1 derivation steps.