Chapter 4, Problem 15RQ

Explanation of Solution

Top-down Parser:

A grammar which has the following characteristics cannot be used as the basis for a top-down parser:

  1) A grammar with direct or indirect left recursion.

  2) A grammar which fails in pairwise disjointness test.

1) A grammar with direct or indirect left recursion:

• Example for grammar with direct left recursion: AA+B, where in a rule for a particular non terminal, the non-terminal on the LHS comes on the leftmost symbol on its RHS too.
• Example for grammar with indirect left recursion: - ABaA, AAb, where in a rule for a particular non terminal, the non-terminal comes as the leftmost symbol on its RHS can be expanded to get a string which in turn can be expanded (using rule for the left most symbol) to get that particular non terminal itself on the left most part.

In a grammar with left recursion, the first non-terminal when expanded from RHS we get the same non terminal of LHS in the grammar rule directly or indirectly. In a top down parsing since the next sentential form is obtained by expanding the left most non terminal, presence of left recursion results in indefinite recursive calls...