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 A

B 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.

If 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 S₀, and to replace the production S with the pair of productions

S₀