Peter Linz Edition 4 Exercise 7.4 Question 8 (Page No. 204)

Question

Let G be a context-free grammar in Greibach normal form. Describe an algorithm which, for any
given k, determines whether or not G is an LL (k) grammar.

Answer 1

An LL(k) grammar is a context-free grammar that can be parsed by an LL(k) parser, which reads input from left to right, performs leftmost derivations, and uses k tokens of lookahead to make parsing decisions.

To determine whether a given context-free grammar G is an LL(k) grammar, you can use the following algorithm:

1. First, determine the leftmost derivation of G for a given input string. A leftmost derivation is a parse tree in which the leftmost non-terminal is expanded at each step.

2. Next, construct the predictive parse table for G, which specifies the production rule to be used for each non-terminal based on the next k tokens of input.

3. Check if the predictive parse table for G is consistent with the leftmost derivation of G. This means that the production rule chosen by the parse table at each step of the leftmost derivation must be the same as the one actually used in the leftmost derivation.

4. If the predictive parse table is consistent with the leftmost derivation, then G is an LL(k) grammar. Otherwise, it is not.

Note that this algorithm only works for context-free grammars in Greibach normal form, as the predictive parse table can only be constructed for this type of grammar.