Rules for First Sets
- If x is a terminal then First(x) is just x!
- If there is a Production A → ε then add ε to first(A)
- If there is a Production X → a1a2..ak then add first(a1a2..ak) to first(X)
- First(a1a2..ak) is either
- First(a1) (if First(a1) doesn't contain ε)
- OR (if First(a1) does contain ε) then First (a1a2..ak) is everything in First(a1) <except for ε > as well as everything in First(a2..ak)
- If First(a1) First(a2)..First(ak) all contain ε then add ε to First(a1a2..ak ) as well
Rules for Follow Sets
- First put $ (the end of input marker) in Follow(S) (S is the start symbol)
- If there is a production A → αBβ, (where α can be a whole string) then everything in FIRST(β) except for ε is placed in FOLLOW(B).
- If there is a production A → αB, then everything in FOLLOW(A) is in FOLLOW(B)
- If there is a production A → αBβ, where FIRST(β) contains ε, then everything in FOLLOW(A) is in FOLLOW(B).
Variable |
First |
Follow |
E |
{ (,id } |
{ $,) } |
E' |
{ +,∈ } |
{ $ ,)} |
T |
{ (,id } |
{ +, $ ,) } |
T' |
{* , ∈} |
{ + ,$ ,) } |
F |
{ (,id } |
{ + ,* ,$ , ) } |
Now coming to question
1.First(E)=First(T)=First(F)
2.Follow(F)={*, + ,$ ,) }
3.Firstk (∊)={∊ }
and If production A→w in the grammar then Firstk (A) contains Firstk(w).