LL(1) Table Construction

In this class, We discuss LL(1) Table Construction.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of predictive parsing. Click Here.

LL(1) is a predictive parsing technique using the non-recursive method.

LL(1) uses a table to avoid the disadvantages of the recursive method.

In our next classes, we discuss the acceptance of input strings using the LL(1) parsing table.

LL(1) is a top-down approach.

LL(1) starts expanding grammar from the start non-terminal and identifies the input string.

The first L in LL(1) says scanning input from left to right.

The second L in LL(1) says producing left most derivation.

The number 1 in LL(1) says lookahead one input symbol.

Example:

The below grammar is an expression grammar to identify arithmetic expressions.

The below table shows the expression grammar First and Follow Symbols.

After constructing First and Follow to the grammar, we follow conditions to construct LL(1) Table.

For each production A – α, do the following conditions.

1) For each terminal ‘a’ in First(α), add A – α to M[A, a].

2) if epsilon is in First(α), add A – ε production to all the Follow symbols.

With examples, we can understand the conditions better.

Take the first production, E – TE’.

First(E) = {id, (}

In the LL(1) table at E row, we add the production E- TE’ in the ‘id,’ and ‘(‘columns.

In LL(1) Table, terminals are taken in columns and Non-terminals in rows.

Take the second production E’ – +TE’ | ε

First(E’) = {+, ε}

The first symbols have epsilon production.

The second condition says to add the production E’ – ε to all E’s ‘follow’ symbols.’

The first condition says to add the production E’ – +TE’ at the first symbol ‘+.’

Similarly, we do the remaining productions.

Important to understand:

The last production, F – id | (E), has two productions.

1) F – id

2) F – (E)

The First symbols of F are {id, (}

The first symbol id came from the first production, F – id. We add this production at the ‘id’ column.

The First symbol ‘(‘comes from the production F – (E). so we add this production at ‘(‘column.

The first condition of LL(1) says to find the First(α) from A – α.