Question

Consider following note that are terminals. E rightarrow e + t | t t rightarrow ID | j x rightarrow e, E | E Eliminate left Then perform left factoring for the grammar Compute the first set for all symbols in the grammar Compute the follow set for non-terminal in the grammar. Can you please explain how to get first follow set? Thanks.

Answer 1

Removed Left Recursive and Left-Factoring from the grammer:-

New Non-Terminals Added are E', T' & X'

Note: e₀ used as null production.

Eleminating Left Recursion

E->T+E'

E'->T+E' | e₀

Eliminating Left Factoring:-

T->idT'

T'->[X'] | e₀

X'->X| e₀

X->E , E | E

Symbol	First	Follow
E	id	, id $
E'	id e0	, id $
T	id	+
T'	[ e0	+
X	id	]
X'	id e0	]

Compute First:-

1. If X is a terminal then First(X) is just X!
2. If there is a Production X → ε then add ε to first(X)
3. If there is a Production X → Y1Y2..Yk then add first(Y1Y2..Yk) to first(X)
4. First(Y1Y2..Yk) is either
   1. First(Y1) (if First(Y1) doesn't contain ε)
   2. OR (if First(Y1) does contain ε) then First (Y1Y2..Yk) is everything in First(Y1) <except for ε > as well as everything in First(Y2..Yk)
   3. If First(Y1) First(Y2)..First(Yk) all contain ε then add ε to First(Y1Y2..Yk) as well.F

Follow

1. First put $ (the end of input marker) in Follow(S) (S is the start symbol)
2. If there is a production A → aBb, (where a can be a whole string) then everything in FIRST(b) except for ε is placed in FOLLOW(B).
3. If there is a production A → aB, then everything in FOLLOW(A) is in FOLLOW(B)
4. If there is a production A → aBb, where FIRST(b) contains ε, then everything in FOLLOW(A) is in FOLLOW(B)