LEFT FACTORING
REAL LIFE EXAMPLE INPUT STRING
Trichy- Cuddalore
T VC | VS | VP
Eg 1
Eg 2
Eg 3
Eg 4
KEY POINTS
When the choice between two alternative A-productions is not clear, we may be
able to rewrite the productions to defer the decision until enough of the input has
been seen that we can make the right choice.
FIRST AND FOLLOW
My enemy is left
Recursion
Steps:
HOW TO FIND FIRST? 1. Identify terminal and non-terminals.
2. Eliminate left recursion if any.
3. Find First
Case X First (X)
1 X - > Terminal
2 X - > Non-Terminal
X -> Y1
Y1 -> c
3 X - > Non-Terminal Non-Terminal
X -> Y1Y2
Y1 -> c | ϵ
Y2 -> d | e
Rule First(X)
HOW TO FIND FIRST? 1. X -> a a
Real Life Example 2. X -> Y1 First(X) = First(Y1)
S -> DE 3. X -> Y1Y2 First(X) = First(Y1),
First(Y2) if epsilon
D -> o | f | ϵ in First(Y1)
E -> b | c | ϵ
Variables Subject,
Department,Elective
Terminals os,fds,big,cloud,epsilon
HOW TO FIND FIRST?
Eg2
S -> DE
D -> o | f
E -> b | c | ϵ
Variables Subject,
Department,Elective
Terminals os,fds,big,cloud,epsilon
Variables
Terminals
FIRST AND FOLLOW
My enemy is left
Recursion
FOLLOW
Rule Production Follow
1 Start Symbol $
2 A -> xBM Follow(B) = First(M)
3 A -> xB Follow(B) = Follow(A)
4 Follow will never ever have epsilon
5 See RHS only
6 See for every variable
FIRST AND FOLLOW
Practise Questions
Solved Q.1
Solved Q.1
Solved Q.2
Solved Q.2
Practise Question NO 1
Practise Question NO 2
Practise Question NO 3
