Grammars for Exhaustive Parsing II
We have shown that exhaustive search parsing is a finite process, provided that
there are no productions of the form A
or AB in the grammar.
Chapter 6 of your textbook (which we will not cover in this course) describes
methods for removing such productions from a grammar without altering the language
recognized by the grammar. There is, however, one special case we need to consider.
belongs to the language, we need to keep the production S.
This creates a problem if S occurs on the right hand side of some production,
because then we have a way of decreasing the length of a sentential form. All
we need to do in this case is to add a new start symbol, say S0,
and to replace the production S
with the pair of productions
Copyright © 1996 by David Matuszek
Last modified Mar 2, 1996