Construct LL(1) Parsing Table For The Following Grammar: E -> E+T | T T -> T*F | F F -> (E) | a

Construct LL(1) Parsing Table For The Following Grammar: 

E -> E+T | T  

T -> T*F | F  

F -> (E) | a

LL(1) Grammar :

• LL(1) is non recursive top down parser.
• It is also called as predictive parser.
• First L indicates input is scanned from left to right.
• The second L means it uses leftmost derivation for input string.
• 1 means it uses only input symbol to predict the parsing process.

Steps to construct LL(1) parser :

1. Remove left recursion / perform left factoring (if any).

2. Compute FIRST and FOLLOW of non terminals.

3. Construct predictive parsing table.

4. Parse the input string using parsing table.

Step 1 : Remove left recursion

                E  -> TE'

                E' -> +TE' | ε

                T  -> FT'

                T' -> *FT' | ε

                F  -> (E) | a

Step 2 : Compute first and follow

NT	FIRST	FOLLOW
E	{ (,a }	{ $,) }
E’	{ +,ε }	{ $,) }
T	{ (,a }	{ +,$,) }
T’	{ *,ε }	{ +,$,) }
F	{ (,a }	{ *,+,$,) }

Step 3 : Construct predictive parsing table

NT	INPUT SYMBOL
	a	+	*	(	)	$
E	E -> TE’			E -> TE’
E’		E’ -> +TE’			E’ -> ε	E’ -> ε
T	T -> FT’			T -> FT’
T’		T’ -> ε	T’ -> *FT’		T’ -> ε	T’ -> ε
F	F -> a			F -> (E)