How To Construct LL(1) Parsing Table

                  In this post, we will see how to construct LL(1) parsing table for the given grammar.
                   LL(1) is Top Down Parsing algorithm.

What is meaning of name LL(1)???
L: Left To Right Scanning of String
L: Left Most Derivation

(1): Size of Look ahead i.e. number of symbols under consideration is 1.

Method:
1. Find the FIRST and FOLLOW of the given grammar.
2. Create a Table where Row fields are all Non-Terminals and Column fields are all terminals including $.
3. Productions are added into Table as entries.
The way to fill entries is as follows:
    For a production X->Y,
       i.  if Y is not ϵ, then add production X->Y into a row of X and column of FIRST(Y). 
       ii. If Y is ϵ, then add production X->Y into a row of X and column of FOLLOW(X).
                  Go through the following example:

Grammar:

E->TE'
E'->+TE'/ϵ
T->FT'
T'->*FT'/ϵ
F->id/(E)

FIRST(E)={id,(} 
FIRST(E')={+,ϵ} 
FIRST(T)={id,(}  
FIRST(T')={*,ϵ} 
FIRST(F)={id,(} 

FOLLOW(E)={$,)} 
FOLLOW(E')={$,)} 
FOLLOW(T)={+,),$}  
FOLLOW(T')={+,),$} 
FOLLOW(F)={*,+,),$} 

LL(1) Parsing Table:

	id	+	*	(	)	$
E	E->TE'			E->TE'
E'		E'->+TE'			E'->ϵ	E'->ϵ
T	T->FT'			T->FT'
T'		T'->ϵ	T'->*FT'		T'->ϵ	T'->ϵ
F	F->id			F->(E)

Note: In each cell, there should be at max one entry. If there are more than one entry, then the grammar is not LL(1).

Check Other Posts on Compiler

Next: How To Construct LR(0) Parsing Table

Previous: How to find FIRST and FOLLOW of a grammar with examples