If we construct a GNF version of a grammar using the algorithm developed in Exercise 19, the resulting grammar is free of left-recursion. However, the resulting grammar can still have common prefixes that prevent it from being LL(1). If we apply the algorithm presented in Figure 5.13 of Section 5.5.1, the resulting grammar will be free of left-recursion and common prefixes. Show that the absence of common prefixes and left-recursion in an unambiguous grammar does not necessarily make a grammar LL(1).

Exercise 19

As discussed in Section 5.5, a grammar is in Greibach Normal Form (GNF) if all productions are of the form A→aα, where a is a terminal symbol and α is a string of zero or more grammar (i.e., terminal or nonterminal) symbols. Let G be a grammar that does not generate λ. Design an algorithm to transform G into GNF.

Figure 5.13