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:
With these restrictions,
- 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.
- 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.
Copyright © 1996 by David Matuszek
Last modified Mar 3, 1996