An Introduction to Formal Languages and Automata, 7th Edition

16.4 LL(k) PARSING

As we saw earlier in Section 7.4, not all context-free grammars are LL(1), and some context-free grammars are not LL(k) for any k. We can build the LL(1) Parse Table for any context-free grammar. However, if there is a conflict in the table, meaning at least one entry in the table has more than one right-hand side, then the grammar is not LL(1).

EXAMPLE 16.5

Build the LL(1) Parse Table for the following grammar.

G = (V, T, S, P), where V = {S}, T = {a, b}, and P consists of

$$S\to aSb\mid ab.\text{ n}$$

First calculate the FIRST and FOLLOW sets.

	FIRST	FOLLOW
S	a	b, $

Build the LL(1) Parse Table.

In this case there are right-hand ...