An Introduction to Formal Languages and Automata, 7th Edition

16.2 LL(1) PARSE TABLE

To simplify the parsing process, information from the npda combined with lookaheads can be stored in a table called the LL(k) Parse Table. For now we focus on k = 1, and show how to build an LL(1) Parse Table.

LL(1) Parse Table

For a context-free grammar G = (V, T, S, P), the rows of the table are labeled with A ∈ V and the columns of the table are labeled with a ∈ T∪{$}, the symbols that could be a lookahead.

To construct the LL(1) Parse Table. Let A ∈ V, and w ∈ (V ∪ T)^*.

1. For each production A → w.
   1. For each a in FIRST(w), add w to LL[A, a].
   2. If λ ∈ FIRST(w), add w to LL[A, b] for each b in FOLLOW(A).
2. Each undefined entry is error.

EXAMPLE 16.3

Build the LL(1) Parse Table for the grammar in Example 16.1, and also ...