4.3 Generating LL(1) Parsing Tables

Constructing LL(1) parsing tables is relatively easy (compared to constructing the tables for lexical analysis). The table is constructed using the following algorithm:

Algorithm

LL(1) Table Generation

For every production A in the grammar:

1. If can derive a string starting with a (i.e., for all a in FIRST( ) ,

Table [A, a] = A

2. If can derive the empty string, , then, for all b that can follow a string derived from A (i.e., for all b in FOLLOW (A) ,

Table [A,b] = A

Undefined entries are set to error, and, if any entry is defined more than once, then the grammar is not LL(1).

EXAMPLE 5 Constructing an LL(1) parse table entry using rule 1

Consider the production E TE' from the non-left-recursive, left-factored expression grammar in Example 4. FIRST(TE') = { (, Id }, so Table[E,(] = E TE' and Table[E,Id] = E TE'.

---

EXAMPLE 6 Constructing an LL(1) parse table entry using rule 2

Consider the production E' from the same grammar of Example 4. Since ";", ")" and "$" are in FOLLOW (E'), this production occurs in the table in the row labeled E', and under the columns labeled ";", ")", and "$".

---

LL(1) parsing tables may be generated automatically by writing procedures for FIRST () and FOLLOW(A). Then, when the grammar is input, A and are identified for each production and the two steps above followed to create the table.